Rotate Array
Rotate an array to the right by k steps, in place.
- 1 <= nums.length <= 10⁵
- -2³¹ <= nums[i] <= 2³¹ - 1
- 0 <= k <= 10⁵
Intuition
Rotate array leetcode problem 189 shifts every element right by k positions, wrapping around. The follow-up asks for an in-place solution with O(1) extra space, which is where it gets interesting.
The simple version copies into a new array, placing each element at (i + k) % n. Correct, O(n) time, but O(n) space.
The in-place solution uses a sequence of three reversals, and the trick is worth seeing rather than deriving:
- Reverse the whole array, then reverse the first k elements, then reverse the remaining n − k.
Reversing everything puts the last k elements at the front, but backwards. The two smaller reversals then restore each section's internal order, leaving exactly the rotation.
The step that breaks solutions is normalising k. k can exceed n, so k %= n is required first — rotating by n is a no-op, and without the modulo the reversal boundaries land out of range.
After that modulo, k = 0 means no rotation, and the three reversals correctly do nothing.
The cyclic replacement approach is the third option: move each element directly to its final position, following cycles until every element is placed. It touches each element once, but the number of cycles is gcd(n, k), and tracking the count of moved elements is fiddly. The reversal method achieves the same bounds with far simpler code.
The direction matters — this is a right rotation. Reversing the sections in the wrong order produces a left rotation, which passes some symmetric test cases and fails the rest.
Three reversals give O(n) time and O(1) space.
Three reversals rotate in place with O(1) space. Reversing the whole array puts the tail at the front but backwards; reversing each of the two resulting segments straightens them out. The identity reverse(reverse(A) + reverse(B)) = B + A is the trick worth memorising.
Approach
Before reading on: price up what the direct approach costs here, then ask what you would need to remember from the left to avoid re-scanning. Aim for O(n) time and O(1) space.
Normalise k first
k can exceed n, so apply k %= n. Rotating by n is a no-op, and without this the reversal boundaries fall out of range.
Reverse the whole array
This brings the last k elements to the front, though in reversed order. The two following steps fix that.
Reverse the first k elements
Restores the internal order of the block that moved to the front, which is now correct in both position and sequence.
Reverse the remaining elements
Restores the order of the rest. The three reversals together produce exactly the rotation with no extra memory.
Mind the rotation direction
This is a right rotation. Reversing the sections in the wrong order gives a left rotation, which passes symmetric test cases and fails the rest.
Know the cyclic alternative
Moving each element straight to its destination also works, but the cycle count is gcd(n, k) and tracking placement is fiddly for the same bounds.
Cost of the approach
Three reversals touch each element a constant number of times, giving O(n) time and O(1) space.
Solution & live demo
Common pitfalls
Not reducing k modulo n
rev(0, k - 1)
k %= n
k may exceed the array length, and rotating by n is a no-op. Without the reduction the segment boundaries fall outside the array and the reversals corrupt or throw.
Reversing the segments in the wrong order
rev(0, n - k - 1) rev(n - k, n - 1)
rev(0, k - 1) rev(k, n - 1)
After the full reversal the last k elements now occupy the first k slots, so the split is at k, not n - k. Using the pre-reversal boundary rotates by the wrong amount.
Building a new array with slicing
nums[:] = nums[-k:] + nums[:-k]
rev(0, n - 1); rev(0, k - 1); rev(k, n - 1)
Correct and readable, but allocates O(n) extra space — the problem asks for an in-place O(1) solution. The three reversals touch each element at most twice with no allocation.
Edge cases
Nothing changes — worth an early return.
The modulus reduces it; forgetting it causes an out-of-bounds slice.
The modulus makes it 0, so the array is unchanged.
Any rotation is a no-op.