Rotate Array — Editorial

Opening the reading…

Intuitionwhy reversing the whole array exposes the rotation

A right rotation by k moves the final k values to the front and keeps the other values after them. For example, [1,2,3,4,5,6,7] rotated by 3 becomes [5,6,7,1,2,3,4]. The two groups keep their internal order, so the task is to swap the groups without allocating a second array.

Reverse the entire array first. The two groups are now in the correct group order but each group is backwards: [7,6,5,4,3,2,1]. Reversing the first k values restores the moved group, and reversing the remaining values restores the original group. These three reversals perform the rotation using only swaps.

Approach

Let n be the array length and replace k with k % n, because rotating by n steps returns every value to its starting index and larger rotations repeat the same pattern.

Return immediately when k is zero, because all three reversals would otherwise do unnecessary work and the two range boundaries would describe empty or unchanged parts.

Reverse the entire array, because this moves the group that belongs at the front into the front while reversing both groups internally.

Reverse the first k positions, because those positions contain the values originally taken from the end and they need their original left-to-right order restored.

Reverse the range from index k through index n - 1, because the values that stay after the rotation are also backwards after the whole-array reversal.

Modify the existing array through range reversals and return nothing, because the problem requires an in-place transformation rather than a newly allocated result.

Complexityconstant working memory even for the largest input

MEASURE	BOUND	WHY
Time	O(n)	The three reversals touch together n + k + (n - k) positions, which is 2n element swaps up to constant factors. Each position belongs to the stated ranges and no reversal scans outside its range, so the total remains linear.
Space	O(1) extra	The reversals use only a constant number of indices and one temporary value for swaps. The input array is modified in place and no output storage is counted; this bound stays constant even for the worst input shape.

Here n is the array length; k is the effective rotation count after replacing the input k with k % n.

Annotated solutionC++ · three reversals · the in-place version to remember

CPPThree range reversals rotate the array in place without returning a value.

#include <algorithm>
#include <vector>
using namespace std;

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

        k %= n;
        if (k == 0) return;

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

The order of the three reverse calls is the insight. The first call changes the position of the two groups, while the next two calls repair their internal order. The iterator nums.begin() + k marks the first element of the suffix, so the second and third reversals cover exactly the two groups created by the rotation.

The cycle-replacement alternativea different O(1)-space arrangement, useful when you want to follow indices

You can also move each value directly to its destination index. A value at index i moves to (i + k) % n, and repeatedly applying that rule traces a cycle. When a cycle returns to its starting index, another cycle must begin at the next still-unvisited index. The greatest common divisor of n and k determines how many cycles exist, but an explicit count avoids a visited array.

CPPCycle replacement moves every value directly to its rotated index using one temporary value.

#include <numeric>
#include <vector>
using namespace std;

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

        k %= n;
        if (k == 0) return;

        int moved = 0;
        int start = 0;

        while (moved < n) {
            int current = start;
            int previous = nums[start];

            do {
                int next = (current + k) % n;
                int temporary = nums[next];
                nums[next] = previous;
                previous = temporary;
                current = next;
                ++moved;
            } while (current != start);

            ++start;
        }
    }
};

This alternative has the same O(n) time and O(1) extra space as the reversal method, so it is not an asymptotic optimisation. It buys a direct view of the permutation: every element moves once, and the temporary value carries the displaced element around its cycle. The reversal version is usually easier to verify because its three ranges are visible, while the cycle version is useful when index mapping is the main idea.