How Do You Rotate an Array by K Positions?
Learn the O(1) space three-reversal trick to rotate an array by k positions and how to answer this classic coding interview question.
Expected Interview Answer
The optimal way to rotate an array of n elements right by k positions in place is the three-reversal trick: reverse the whole array, then reverse the first k elements, then reverse the remaining n-k elements, giving O(n) time and O(1) extra space.
A naive approach rotates one step at a time k times, costing O(n*k). A cleaner approach copies into a new array at index (i+k) mod n, which is O(n) time but O(n) extra space. The reversal trick achieves O(n) time and O(1) space by exploiting the fact that reversing the whole array flips both blocks into the right relative order, and reversing each block individually then un-flips each block internally. Always normalize k with k = k % n first, since rotating by n is a no-op and k can exceed n.
- O(n) time, O(1) extra space in place
- No modulo indexing bugs from a new array
- Generalizes to left rotation by reversing in the opposite order
- Simple to reason about and prove correct
AI Mentor Explanation
Rotating a batting order by k spots is like flipping the entire lineup card upside down first, then flipping just the last k names back to right-side-up, then flipping the remaining names back to right-side-up separately. After all three flips, the last k batters have moved to the front in their original relative order, and everyone else has shifted back, without needing a second lineup card. A naive coach who instead moves one batter at a time, k times, wastes far more effort re-shuffling for every single position shift. The three-flip method touches each name at most three times total, no matter how large k is.
Step-by-Step Explanation
Step 1
Normalize k
Compute k = k % n so rotations larger than the array length are handled correctly.
Step 2
Reverse the whole array
Reverse all n elements in place, flipping the overall order.
Step 3
Reverse the first k elements
Un-reverse just the first k elements, restoring their internal relative order.
Step 4
Reverse the remaining n-k elements
Un-reverse the rest of the array, completing the rotation in O(n) time and O(1) space.
What Interviewer Expects
- Recognize the naive O(n*k) approach and why it is suboptimal
- Explain the three-reversal trick and why it achieves O(1) extra space
- Handle k >= n via modulo normalization
- State the final time and space complexity clearly
Common Mistakes
- Forgetting to normalize k with k % n
- Reversing the two halves in the wrong order or wrong split point
- Using an extra array when the problem explicitly asks for in place
- Off-by-one errors in the reversal index boundaries
Best Answer (HR Friendly)
“To rotate an array by k positions without using extra memory, I reverse the whole array, then reverse the first k elements, then reverse the rest. It sounds counterintuitive, but those three reversals exactly produce the rotated array in place, in linear time.”
Code Example
def rotate(nums, k):
n = len(nums)
k = k % n
def reverse(lo, hi):
while lo < hi:
nums[lo], nums[hi] = nums[hi], nums[lo]
lo += 1
hi -= 1
reverse(0, n - 1)
reverse(0, k - 1)
reverse(k, n - 1)
return nums
print(rotate([1, 2, 3, 4, 5, 6, 7], 3)) # [5, 6, 7, 1, 2, 3, 4]Follow-up Questions
- How would you rotate the array to the left instead of the right?
- How would this approach change for a singly linked list instead of an array?
- What if k could be negative?
- How would you rotate a 2D matrix instead of a 1D array?
MCQ Practice
1. What is the time and space complexity of the three-reversal array rotation technique?
Each element is touched a constant number of times across the three reversals, giving O(n) time and O(1) extra space.
2. Why must k be normalized with k = k % n before rotating?
A full rotation of n positions is a no-op, so only k mod n represents meaningful, distinct rotation.
3. In the three-reversal method, what is reversed second?
After reversing the whole array, the first k elements are reversed back to restore their relative order.
Flash Cards
What are the three steps of the reversal rotation trick? — Reverse the whole array, reverse the first k elements, reverse the remaining n-k elements.
What is the space complexity of the reversal rotation technique? — O(1) extra space, since it rotates in place.
Why normalize k with k % n? — Because rotating by n or a multiple of n is equivalent to no rotation at all.
What is the naive rotation approach and its cost? — Shifting one element at a time, k times, costing O(n*k) time.