Rotate Array
Given an integer array numsk
Example 1
Input: nums = [1, 2, 3, 4, 5, 6, 7], k = 3
Output: [5, 6, 7, 1, 2, 3, 4]
Output: [5, 6, 7, 1, 2, 3, 4]
Example 2
Input: nums = [-1, -100, 3, 99], k = 2
Output: [3, 99, -1, -100]
Output: [3, 99, -1, -100]
How to Think About It
Step 1: Simple ways
- Move every element one step, k times: O(n × k).
- Copy into a new array at index
: O(n) time but O(n) extra space.(i + k) % n
Step 2: k larger than n
Rotating by n puts every element back where it started, so only k % n
Step 3: Three reversals
Rotating right by k moves the last k elements to the front, keeping each part's order. Reversals do this in place:
- Reverse the whole array: the last k elements are now at the front, but backwards.
- Reverse the first k elements: they are now in the right order.
- Reverse the remaining n - k elements: they are in the right order too.
Walkthrough
nums = [1, 2, 3, 4, 5, 6, 7]k = 3
| Step | Array after |
|---|---|
| reverse all | [7, 6, 5, 4, 3, 2, 1] |
| reverse the first 3 | [5, 6, 7, 4, 3, 2, 1] |
| reverse the last 4 | [5, 6, 7, 1, 2, 3, 4] |
Java Solution
The reverse
Java
import java.util.Arrays;
public class RotateArray {
public static void rotate(int[] nums, int k) {
int n = nums.length;
k %= n; // rotating by n changes nothing
reverse(nums, 0, n - 1); // 1. reverse everything
reverse(nums, 0, k - 1); // 2. reverse the first k
reverse(nums, k, n - 1); // 3. reverse the rest
}
private static void reverse(int[] a, int lo, int hi) {
while (lo < hi) {
int tmp = a[lo];
a[lo++] = a[hi];
a[hi--] = tmp;
}
}
public static void main(String[] args) {
int[] a = {1, 2, 3, 4, 5, 6, 7};
rotate(a, 3);
System.out.println(Arrays.toString(a)); // [5, 6, 7, 1, 2, 3, 4]
int[] b = {-1, -100, 3, 99};
rotate(b, 2);
System.out.println(Arrays.toString(b)); // [3, 99, -1, -100]
}
}
The original implementation,
Complexity
- Time: O(n): each element is swapped about twice.
- Space: O(1).
The same reversal trick rotates a string or a list of words.