#189
Rotate Array
Medium Reversal trick
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Rotate an array to the right by k steps in place.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: shift every element k steps to the right, wrapping around.
Why this works: rotating = moving the last k elements to the front. Reversing everything, then reversing the two parts, achieves exactly that with no extra array.
Example: [1, 2, 3, 4, 5, 6, 7], k = 3
reverse all: 7 6 5 4 3 2 1reverse first 3: 5 6 7 4 3 2 1reverse rest: 5 6 7 1 2 3 4
✦Hints open one at a time
k can be larger than n — use k % n.
Rotating right by k = moving the last k elements to the front.
Reverse the whole array, then reverse the first k and the remaining n - k separately.
↗Approach
Three reversals: whole array, first k, rest. Each element ends at (i + k) % n with O(1) extra space.
</>Solution (Java)
class Solution {
public void rotate(int[] nums, int k) {
int n = nums.length;
k %= n;
reverse(nums, 0, n - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, n - 1);
}
private void reverse(int[] a, int l, int r) {
while (l < r) {
int t = a[l];
a[l++] = a[r];
a[r--] = t;
}
}
}!Common mistake
Shifting one step at a time k times — O(n·k), which times out.
Complexity
- Time: O(n).
- Space: O(1).
Topic: Arrays
