Rotate Array

Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.

First, Reduce k

Click to zoom

Approach 1: Brute Force (Rotate One Step at a Time)

Rotating right by one step means:

1. Save the last element.
2. Shift every other element one position to the right.
3. Put the saved element at index 0.

Repeat this k times.

This is the most direct simulation, but it is slow. With n and k both up to 10^5, it can exceed the time limit on LeetCode.

class Solution {
    public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k %= n;

        for (int step = 0; step < k; step++) {
            int last = nums[n - 1];

            for (int i = n - 1; i > 0; i--) {
                nums[i] = nums[i - 1];
            }

            nums[0] = last;
        }
    }
};

Time: O(n × k)

Space: O(1)

Approach 2: Extra Array

Instead of moving elements one step at a time, place each element directly at its final position.

After rotating right by k, the element at index i moves to index (i + k) % n.

1nums = [1,2,3,4,5,6,7], k = 3
2 
3index 0 (1) → (0 + 3) % 7 = 3
4index 4 (5) → (4 + 3) % 7 = 0
5index 6 (7) → (6 + 3) % 7 = 2

We write every element into a new array at its correct position, then copy the new array back into nums.

class Solution {
    public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k %= n;

        vector<int> temp(n);

        for (int i = 0; i < n; i++) {
            temp[(i + k) % n] = nums[i];
        }

        for (int i = 0; i < n; i++) {
            nums[i] = temp[i];
        }
    }
};

Time: O(n)

Space: O(n)

This is fast, but the follow-up asks for O(1) extra space. The next two approaches achieve that.

Approach 3: Reverse the Array (Optimal)

A right rotation by k moves the last k elements to the front, while keeping the order inside each part.

We can do this with three reversals:

1. Reverse the whole array.
2. Reverse the first k elements.
3. Reverse the remaining n - k elements.

1nums = [1,2,3,4,5,6,7], k = 3
2 
3Reverse all:          [7,6,5,4,3,2,1]
4Reverse first 3:      [5,6,7,4,3,2,1]
5Reverse last 4:       [5,6,7,1,2,3,4]  ✓

class Solution {
    public:
    void reverse(vector<int>& nums, int left, int right) {
        while (left < right) {
            swap(nums[left], nums[right]);
            left++;
            right--;
        }
    }

    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k %= n;

        reverse(nums, 0, n - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, n - 1);
    }
};

Time: O(n)

Space: O(1)

Why Do Three Reversals Work?

Split the array into two parts: A is the first n - k elements, and B is the last k elements.

1Original:   [ A | B ]  =  [1,2,3,4 | 5,6,7]
2Goal:       [ B | A ]  =  [5,6,7 | 1,2,3,4]

Reversing the whole array puts B in front of A, but both parts come out backwards:

1Reverse all:  [ B reversed | A reversed ]  =  [7,6,5 | 4,3,2,1]

Reversing each part again restores its original order:

1Fix B:   [5,6,7 | 4,3,2,1]
2Fix A:   [5,6,7 | 1,2,3,4]  ✓

The first reversal gets the parts into the right place. The next two reversals fix the order inside each part.

Approach 4: Cyclic Replacements

This approach also works in place. Instead of reversing, it moves each element directly to its final position, like Approach 2, but without a second array.

Start at index 0. Pick up its value and place it at (0 + k) % n. The value that was sitting there gets picked up and placed at its own correct position. Keep going until you come back to the starting index.

1nums = [1,2,3,4,5,6], k = 2
2 
3Start at 0:  0 → 2 → 4 → 0   (moves 1, 3, 5)
4Start at 1:  1 → 3 → 5 → 1   (moves 2, 4, 6)
5 
6Result: [5,6,1,2,3,4]

Sometimes one cycle does not visit every index, like in this example. So we start a new cycle from the next index, and we stop once we have moved exactly n elements in total.

class Solution {
    public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k %= n;

        int count = 0;

        for (int start = 0; count < n; start++) {
            int current = start;
            int prev = nums[start];

            do {
                int next = (current + k) % n;
                int temp = nums[next];
                nums[next] = prev;
                prev = temp;
                current = next;
                count++;
            } while (current != start);
        }
    }
};

Time: O(n)

Space: O(1)

Click to zoom

This is correct and optimal, but harder to get right in an interview than the reversal approach. Most people prefer Approach 3.

Comparing All Approaches

Complexity