Start learning free

LESSON 257 OF 437 · TWO POINTERS

Rotate Array in C++: O(n) Time, O(1) Space with Cycles

Practice O(n) Read the full explanation

Given a vector of integers nums, rotate it k times to its right, in place, using O(1) extra memory.

One rotation to the right moves every number one position to the right, and the last number moves to the front.

Your function rearranges the numbers inside nums itself, without building a new vector: the output in the examples is nums after the call. (In Rust the function takes nums by value, so it returns that same vector, rotated.)

Example 1:

Input: nums = [1, 2, 3, 4, 5], k = 2
Output: [4, 5, 1, 2, 3]
Explanation: After 1 rotation: [5, 1, 2, 3, 4]. After 2 rotations: [4, 5, 1, 2, 3].

Example 2:

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

Constraints:

  • 1 <= nums.length <= 3 * 104
  • 1 <= nums[i] <= 231 - 1
  • 1 <= k <= nums.length
Note:

Your algorithm should run in O(n) time and use O(1) extra space.

STEP 1 OF 6
    Ctrl + Enter to check

    C++ · TWO POINTERS

    Rotate Array in C++, explained

    Problem overview

    The method rotate receives a vector<int>& nums and an integer k. It must rotate the vector k times to the right, in place. One rotation to the right moves every number one position to the right, and the last number wraps around to the front. The method returns nothing: the caller's vector is the result. The constraints give 1 <= k <= nums.length.

    For nums = [1, 2, 3, 4, 5] and k = 2, one rotation gives [5, 1, 2, 3, 4] and a second gives [4, 5, 1, 2, 3]. For eight numbers and k = 3, the last three numbers move to the front: [6, 7, 8, 1, 2, 3, 4, 5].

    The lesson asks for O(n) time and O(1) extra space, so copying the vector into a second one isn't allowed.

    Approach: follow each element to its final slot

    Rotating k times to the right sends the element at position i to position (i + k) % n, where n is the length. The remainder operator handles the wrap-around past the end.

    The simple methods fall short of the budget. Rotating one step at a time k times costs O(n * k), and a copy into a new vector costs O(n) extra space. The cycle method moves each element straight to its destination using one swap per element.

    Start at position 0 and carry its value to position k % n. Swapping puts the carried value into its final place and brings the value that was there back to position 0. That displaced value must go to its own destination, k places further on, so the next swap sends it there, and so on. Position 0 always holds the value currently being carried.

    Here it is on [1, 2, 3, 4, 5] with k = 2. Each row shows the vector after one swap:

    c=0, swap with position 2: 3 2 1 4 5
c=1, swap with position 4: 5 2 1 4 3
c=2, swap with position 1: 2 5 1 4 3
c=3, swap with position 3: 4 5 1 2 3
c=4, swap with position 0: 4 5 1 2 3

    The positions visited are 0, 2, 4, 1, 3 and back to 0. That path is a cycle. The last swap is position 0 with itself: the value carried back to the start is already the right one, and the cycle is closed.

    A cycle doesn't always cover the whole vector. With n = 6 and k = 2, the path 0, 2, 4, 0 only touches the even positions. The odd positions form a second cycle, and the method must start it separately from position 1. In general there are gcd(n, k) cycles, each of length n / gcd(n, k). The self-swap that closes a cycle is the signal to move the start to the next position.

    Each iteration, including the closing self-swap, settles exactly one position, so n iterations settle all n positions.

    Step by step

    1. Set up three int variables: n, the length; index, the position where the last carried value was dropped; and startIndex, the first position of the current cycle. Both positions start at 0.
    2. Loop exactly n times. The counter c is only a tally, because one position is settled per iteration.
    3. Compute nextIndex as (index + k) % n. This is the destination of the value being carried, with wrap-around.
    4. Swap nums[nextIndex] with nums[startIndex]. The carried value, which lives at startIndex, lands in its final slot. The old occupant of that slot becomes the new carried value.
    5. Move index to nextIndex. The next destination is computed from where the last value landed.
    6. Detect a closed cycle. If index == startIndex, the cycle has come back to its first position. Increment both startIndex and index to begin the next cycle there. When gcd(n, k) is 1 this fires only once, on the final iteration.

    The solution in C++

    class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size(), index = 0, startIndex = 0;
        for (int c = 0; c < n; c++) {
            int nextIndex = (index + k) % n;
            swap(nums[nextIndex], nums[startIndex]);
            index = nextIndex;
            if (index == startIndex) {
                startIndex++; index++;
            }
        }
    }
};

    C++ details worth a closer look:

    • Reference parameter. vector<int>& nums is a reference, so the method changes the caller's vector. That is why it can return void. Taking the vector by value would rotate a copy and leave the caller's data untouched.
    • size() is unsigned. nums.size() returns an unsigned type, and the lesson converts it to int on the first line. That keeps the arithmetic below, including %, in plain int. If n stayed unsigned, an expression like n - 1 on an empty vector would wrap to a huge number. The constraints guarantee at least one element, so n is never 0 here and % n is safe.
    • swap on elements. swap(nums[nextIndex], nums[startIndex]) exchanges two int values through references to the elements. Swapping an element with itself, which happens when a cycle closes, is harmless.
    • One-line declaration. int n = nums.size(), index = 0, startIndex = 0; declares three separate int variables, each with its own initializer.
    • index + k can't overflow here. Both values are at most 30,000, so the sum is far from the limit of int. Signed overflow would be undefined behaviour in C++, which is why it is worth a thought when sizes get large.

    Complexity

    Time: O(n). The loop runs exactly n times and each iteration does a remainder, a swap and a comparison, all constant work.

    Space: O(1). The method uses a handful of int variables and swaps elements within the vector.

    Edge cases and common mistakes

    • One element. With nums = [7] and k = 1, the only iteration swaps position 0 with itself and the vector stays [7].
    • k equal to the length. A full turn leaves the vector unchanged. Here (index + k) % n equals index, so every iteration is a self-swap that closes a cycle of length 1, and startIndex steps through the vector.
    • Several cycles. When gcd(n, k) is greater than 1, for example n = 6 and k = 2, a single cycle is not enough. Without the startIndex step the loop would keep re-walking the first cycle and leave the other positions unmoved.
    • Rotating the wrong way. Using (index - k) would rotate left. The destination of a rightward rotation is index + k.
    • Looping until index returns to 0. That stops after one cycle. Counting n iterations is what guarantees every position is settled.
    • Forgetting the reference. Without the & on the parameter, the rotation happens on a copy and the caller sees no change.

    Testing

    • nums = [1, 2, 3, 4, 5], k = 2 gives [4, 5, 1, 2, 3].
    • nums = [1, 2, 3, 4, 5, 6, 7, 8], k = 3 gives [6, 7, 8, 1, 2, 3, 4, 5].
    • nums = [1, 2, 3, 4, 5, 6], k = 2 gives [5, 6, 1, 2, 3, 4], using two cycles.
    • nums = [1, 2, 3], k = 3 gives [1, 2, 3].
    • nums = [7], k = 1 gives [7].
    Keep going with C++About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free