How do you rotate an array to the right by k steps in place?
Reverse the whole array, then reverse the first k elements, then reverse the rest. Take k modulo the length first. It runs in O(n) time with O(1) extra space.
Explain it simply
Think of a row of seats where the last k people must move to the front. Instead of shifting everyone k times, use a trick with mirrors: flip the entire row, then flip the first k seats and the remaining seats separately, and each group ends up facing the right way.
For [1,2,3,4,5,6,7] and k = 3: whole reverse gives [7,6,5,4,3,2,1], reversing the first three gives [5,6,7,...], reversing the last four gives [1,2,3,4].
Example
function reverse(a, i, j) {
while (i < j) {
[a[i], a[j]] = [a[j], a[i]];
i++;
j--;
}
}
function rotate(a, k) {
k = k % a.length;
reverse(a, 0, a.length - 1);
reverse(a, 0, k - 1);
reverse(a, k, a.length - 1);
return a;
}
console.log(rotate([1, 2, 3, 4, 5, 6, 7], 3)); // Output: [5,6,7,1,2,3,4]
console.log(rotate([1, 2, 3], 4)); // Output: [3,1,2]Complexity
Time O(n), space O(1).
What to say in the interview
"I reduce k with modulo, reverse the whole array, then reverse the first k elements and the remaining ones. Three reversals give the rotation in O(n) time and O(1) space. A slice-and-concat version is simpler but uses O(n) extra memory."
Common mistakes
- Skipping k % length, which breaks when k is larger than the array.
- Rotating left when the question says right.