Problem 2.5 · ArraysMedium

Rotate Array

What it teaches: The reversal trick: three in-place reverses rotate an array with O(1) extra space.

Practise it on judges as “Rotate Array”.

The problem

Rotate the array nums to the right by k steps, in place. Each step moves the last element to the front.

Example 1

Input: nums = [1, 2, 3, 4, 5, 6, 7], k = 3
Output: [5, 6, 7, 1, 2, 3, 4]

Example 2

Input: nums = [-1, -100, 3, 99], k = 2
Output: [3, 99, -1, -100]

Constraints

1 ≤ nums.length ≤ 10⁵
0 ≤ k ≤ 10⁵ (k may be larger than n)

Pattern clues in the wording

→ "In place" with O(1) extra space
→ Blocks of the array swap positions
→ k larger than n: only k mod n matters

These clues point to Two Pointers: Opposite Ends: Start one pointer at each end and move them towards each other, using a rule to decide which one moves.

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public void rotate(int[] nums, int k) {
        k %= nums.length;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	nums = [1,2,3,4,5,6,7] k = 3	[5,6,7,1,2,3,4]
2	nums = [-1,-100,3,99] k = 2	[3,99,-1,-100]
3	nums = [1,2] k = 5 k larger than n	[2,1]

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Extra array · O(n)2. Optimal: reverse three times · O(n)

Extra array

Time O(n) Space O(n)

Element i moves to (i + k) % n. Write each one into a new array, then copy back.

Approach 1

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        int[] out = new int[n];
        for (int i = 0; i < n; i++) out[(i + k) % n] = nums[i];
        System.arraycopy(out, 0, nums, 0, n);
    }
}

Verdict: Simple, but the follow-up asks for O(1) space.

Optimal: reverse three times

Time O(n) Space O(1)

Rotating right by k moves the last k elements to the front, keeping each block's internal order. Reversing the whole array puts the last k elements at the front, but backwards. Reversing the first k and the remaining n − k elements fixes each block's order.

▶ Dry run: Three reversesnums = [1, 2, 3, 4, 5, 6, 7], k = 3

Step 1/4Goal: the last 3 elements (5, 6, 7) should come first, in order.

Approach 2

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 left, int right) {
        while (left < right) {
            int tmp = a[left]; a[left] = a[right]; a[right] = tmp;
            left++;
            right--;
        }
    }
}

Verdict: Each element is swapped about twice. This is the answer.

Before you submit

Edge cases and common mistakes

Test these inputs

k = 0
k = n (no change)
k > n
One element

Mistakes people make

Forgetting k %= n, so k ≥ n causes index errors.
Rotating one step at a time k times: O(n·k), too slow for large k.

Interview

Follow-up questions

How would you rotate left by k?

Is there another O(1)-space method?

Command Palette