Rotate Array

Practice Link

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

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]

Brute Force#

Rotate the array one step at a time, k times. Each single rotation moves the last element to the front by shifting everything right by one. After k such rotations the array is in the desired state.

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

        for (int i = 0; i < k; i++) {
            int last = nums[n - 1];
            for (int j = n - 1; j > 0; j--)
                nums[j] = nums[j - 1];
            nums[0] = last;
        }
    }
};

Time Complexity: O(n × k)

Space Complexity: O(1)

Better Approach — Extra Array#

Copy the last k elements to the front of a temporary array, then copy the first n-k elements after them. Write the result back into nums.

An element at index i ends up at index (i + k) % n — use this directly to fill the temp array in one pass.

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

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

        nums = temp;
    }
};

Time Complexity: O(n)

Space Complexity: O(n)

Optimal Approach — Three Reverses#

Rotating right by k is equivalent to:

1. Reverse the first n-k elements.
2. Reverse the last k elements.
3. Reverse the entire array.

Why it works:

Right-rotating by k moves the last k elements to the front. Reversing the two parts and then the whole array achieves exactly this rearrangement in-place.

Original:          [1, 2, 3 | 4, 5, 6, 7]   (n=7, k=3, split at n-k=4)
Reverse [0, n-k):  [3, 2, 1 | 4, 5, 6, 7]
Reverse [n-k, n):  [3, 2, 1 | 7, 6, 5, 4]
Reverse all:       [4, 5, 6, 7 | 1, 2, 3]   ✓

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

        reverse(nums.begin(), nums.begin() + (n - k));
        reverse(nums.begin() + (n - k), nums.end());
        reverse(nums.begin(), nums.end());
    }
};

⚠️ Edge case: Always reduce k with k % n first. If k == n, a full rotation returns the original array and skipping it avoids unnecessary work. Without the mod, k > n would also produce a wrong split index.

Time Complexity: O(n)

Space Complexity: O(1)