Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Rotate Array

MEDIUMProblemSolveExternal Links

Description

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

Rotating right by one step means the last element of the array moves to the front, and every other element shifts one position to the right. You need to perform this operation k times (or achieve the equivalent result).

The rotation must be done in-place, meaning you should modify the original array directly rather than returning a new one.

Examples

Example 1

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

Output: [5, 6, 7, 1, 2, 3, 4]

Explanation: After rotating right by 3 steps:

  • Step 1: [7, 1, 2, 3, 4, 5, 6] — the last element 7 moves to the front
  • Step 2: [6, 7, 1, 2, 3, 4, 5] — the last element 6 moves to the front
  • Step 3: [5, 6, 7, 1, 2, 3, 4] — the last element 5 moves to the front

The last 3 elements (5, 6, 7) now appear at the beginning, and the first 4 elements (1, 2, 3, 4) appear at the end.

Example 2

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

Output: [3, 99, -1, -100]

Explanation: After rotating right by 2 steps:

  • Step 1: [99, -1, -100, 3] — the last element 99 moves to the front
  • Step 2: [3, 99, -1, -100] — the last element 3 moves to the front

The last 2 elements (3, 99) now appear at the beginning.

Example 3

Input: nums = [1, 2, 3], k = 4

Output: [3, 1, 2]

Explanation: Since k=4 is larger than the array length 3, the effective rotation is k % 3 = 1 step. After one right rotation, the last element moves to the front: [3, 1, 2].

Constraints

  • 1 ≤ nums.length ≤ 10^5
  • -2^31 ≤ nums[i] ≤ 2^31 - 1
  • 0 ≤ k ≤ 10^5

Editorial

Brute Force

Intuition

The most literal interpretation of the problem: perform one right rotation at a time, and repeat it k times.

A single right rotation means:

  1. Save the last element of the array.
  2. Shift every element one position to the right (starting from the end, moving backward).
  3. Place the saved last element at position 0.

Imagine a line of people standing in a row. To rotate right by one, the person at the very end walks around and stands at the very front, and everyone else takes one step to the right. To rotate by k, you repeat this process k times.

An important optimization: since rotating by the array length n brings us back to the original arrangement, we only need to perform k % n rotations. For example, rotating an array of length 7 by 7 steps returns the same array, so rotating by 10 is the same as rotating by 3.

Step-by-Step Explanation

Let's trace through with nums = [1, 2, 3, 4, 5, 6, 7], k = 3:

Step 1: First rotation. Save last element: temp = 7. Shift all elements right by 1: [_, 1, 2, 3, 4, 5, 6]. Place temp at front: [7, 1, 2, 3, 4, 5, 6].

Step 2: Second rotation. Save last element: temp = 6. Shift all elements right by 1: [_, 7, 1, 2, 3, 4, 5]. Place temp at front: [6, 7, 1, 2, 3, 4, 5].

Step 3: Third rotation. Save last element: temp = 5. Shift all elements right by 1: [_, 6, 7, 1, 2, 3, 4]. Place temp at front: [5, 6, 7, 1, 2, 3, 4].

Result: [5, 6, 7, 1, 2, 3, 4]

Brute Force — Rotate One Step at a Time — Watch how each rotation moves the last element to the front while shifting everything else one position to the right. We repeat this k=3 times.

Algorithm

  1. Compute effective rotations: k = k % n (rotations beyond array length are redundant)
  2. Repeat k times:
    • Save the last element in a temporary variable
    • Shift every element one position to the right (from index n-2 down to 0)
    • Place the saved element at index 0
  3. The array is now rotated right by k steps

Code

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k %= n;
        
        for (int r = 0; r < k; r++) {
            int last = nums[n - 1];
            for (int i = n - 1; i > 0; i--) {
                nums[i] = nums[i - 1];
            }
            nums[0] = last;
        }
    }
};
class Solution:
    def rotate(self, nums: list[int], k: int) -> None:
        n = len(nums)
        k %= n
        
        for _ in range(k):
            last = nums[-1]
            for i in range(n - 1, 0, -1):
                nums[i] = nums[i - 1]
            nums[0] = last
class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k %= n;
        
        for (int r = 0; r < k; r++) {
            int last = nums[n - 1];
            for (int i = n - 1; i > 0; i--) {
                nums[i] = nums[i - 1];
            }
            nums[0] = last;
        }
    }
}

Complexity Analysis

Time Complexity: O(n × k)

Each single rotation requires shifting all n elements one position, which takes O(n) time. We perform this k times (after taking k % n), so the total time is O(n × k). In the worst case, k can be close to n, making this O(n²).

Space Complexity: O(1)

We only use a single temporary variable to hold the last element during each rotation. No additional arrays or data structures are needed.

Why This Approach Is Not Efficient

The brute force performs k separate rotations, each costing O(n) for the element shifting. With n up to 10^5 and k up to 10^5, this means up to 10^10 operations in the worst case — far too slow for typical time limits.

The core problem is that we're doing redundant work. Each element ultimately needs to move to one specific final position, but we're moving it there one step at a time across k iterations. If we could compute each element's final destination directly, we could place it there in a single move.

Key insight: After rotating right by k positions, the element at index i ends up at index (i + k) % n. The last k elements wrap around to the front. We can achieve this in O(n) time by either using an extra array to store the rearranged elements, or by cleverly reversing segments of the array in-place.

Better Approach - Extra Array

Intuition

Instead of rotating one step at a time, we can compute where each element should go after k rotations and place it directly in a new array.

After a right rotation by k, element at index i moves to index (i + k) % n. So we create a temporary array, place each element at its final position, then copy everything back.

Think of it as reseating people at a circular dinner table. Instead of asking everyone to stand up and shift one seat at a time (k times!), you simply tell each person: "Your new seat number is your current seat plus k, wrapping around if needed." Everyone moves to their correct seat in one go.

Step-by-Step Explanation

Let's trace through with nums = [1, 2, 3, 4, 5, 6, 7], k = 3:

Step 1: n = 7, k = 3. Create a temporary array of size 7: temp = [_, _, _, _, _, _, _].

Step 2: Place nums[0]=1 at position (0+3)%7 = 3: temp = [_, _, _, 1, _, _, _].

Step 3: Place nums[1]=2 at position (1+3)%7 = 4: temp = [_, _, _, 1, 2, _, _].

Step 4: Place nums[2]=3 at position (2+3)%7 = 5: temp = [_, _, _, 1, 2, 3, _].

Step 5: Place nums[3]=4 at position (3+3)%7 = 6: temp = [_, _, _, 1, 2, 3, 4].

Step 6: Place nums[4]=5 at position (4+3)%7 = 0: temp = [5, _, _, 1, 2, 3, 4].

Step 7: Place nums[5]=6 at position (5+3)%7 = 1: temp = [5, 6, _, 1, 2, 3, 4].

Step 8: Place nums[6]=7 at position (6+3)%7 = 2: temp = [5, 6, 7, 1, 2, 3, 4].

Step 9: Copy temp back to nums. Final array: [5, 6, 7, 1, 2, 3, 4].

Extra Array — Direct Placement of Each Element — Watch how each element is placed directly at its final position (i+k)%n in a temporary array, completing the rotation in a single pass.

Algorithm

  1. Compute effective rotations: k = k % n
  2. Create a temporary array of size n
  3. For each index i from 0 to n-1:
    • Compute new position: newPos = (i + k) % n
    • Place nums[i] at temp[newPos]
  4. Copy all elements from temp back to nums

Code

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];
        }
    }
};
class Solution:
    def rotate(self, nums: list[int], k: int) -> None:
        n = len(nums)
        k %= n
        
        temp = [0] * n
        for i in range(n):
            temp[(i + k) % n] = nums[i]
        
        for i in range(n):
            nums[i] = temp[i]
class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k %= n;
        
        int[] temp = new int[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];
        }
    }
}

Complexity Analysis

Time Complexity: O(n)

We iterate through the array twice — once to place elements in the temp array, and once to copy them back. Each pass is O(n), so total is O(2n) = O(n).

Space Complexity: O(n)

We allocate a temporary array of the same size as the input to hold the rearranged elements. This extra space is proportional to the input size.

Why This Approach Is Not Efficient

The extra array approach runs in O(n) time, which is optimal for this problem — we must visit every element at least once. However, it uses O(n) additional space for the temporary array.

The problem's follow-up challenge asks: can we achieve the same O(n) time complexity using only O(1) extra space? In other words, can we rotate the array in-place without allocating a second array?

The answer is yes, through a clever observation: rotating an array right by k is equivalent to performing three reversal operations. This reversal algorithm achieves O(n) time with O(1) space, making it the optimal solution in both dimensions.

Optimal Approach - Reversal Algorithm

Intuition

This approach uses a beautiful mathematical property of array reversal. The key observation is:

When we rotate an array right by k positions, the last k elements move to the front, and the first n-k elements shift to the back. If we reverse the right order of the original array and then reverse the two resulting halves individually, we get exactly the rotated array.

Here's the three-step reversal algorithm for right rotation by k:

  1. Reverse the entire array — this puts the last k elements at the front, but in reversed order
  2. Reverse the first k elements — this restores their original relative order
  3. Reverse the remaining n-k elements — this restores their original relative order too

Why does this work? Think of the array as two blocks:

  • Block A = first (n-k) elements
  • Block B = last k elements

We want: [B, A] (the rotation result). Starting from [A, B]:

  1. Reverse entire array: [A, B] → [B_rev, A_rev]
  2. Reverse first k: [B_rev, A_rev] → [B, A_rev]
  3. Reverse last n-k: [B, A_rev] → [B, A]

Each reversal is an in-place operation using two pointers (one at each end, swapping inward), so no extra space is needed.

Step-by-Step Explanation

Let's trace through with nums = [1, 2, 3, 4, 5, 6, 7], k = 3:

Step 1: k = k % n = 3 % 7 = 3. The last 3 elements [5, 6, 7] should move to the front.

Step 2: Reverse the entire array.

  • [1, 2, 3, 4, 5, 6, 7] → [7, 6, 5, 4, 3, 2, 1]
  • Swap indices (0,6), (1,5), (2,4). Middle element stays.

Step 3: Reverse the first k=3 elements (indices 0 to 2).

  • [7, 6, 5, 4, 3, 2, 1] → [5, 6, 7, 4, 3, 2, 1]
  • Swap indices (0,2). Middle element 6 stays.

Step 4: Reverse the remaining n-k=4 elements (indices 3 to 6).

  • [5, 6, 7, 4, 3, 2, 1] → [5, 6, 7, 1, 2, 3, 4]
  • Swap indices (3,6), (4,5).

Result: [5, 6, 7, 1, 2, 3, 4]. This matches the expected output.

Reversal Algorithm — Three Reversals to Rotate In-Place — Watch how three simple reversal operations transform the array into its rotated form without any extra space. Each reversal swaps elements using two converging pointers.

Algorithm

  1. Compute effective rotations: k = k % n
  2. If k is 0, the array is already in position — return
  3. Reverse the entire array (indices 0 to n-1)
  4. Reverse the first k elements (indices 0 to k-1)
  5. Reverse the remaining n-k elements (indices k to n-1)

Helper function reverse(arr, start, end) swaps elements at start and end, then moves inward until start >= end.

Code

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k %= n;
        
        reverse(nums.begin(), nums.end());
        reverse(nums.begin(), nums.begin() + k);
        reverse(nums.begin() + k, nums.end());
    }
};
class Solution:
    def rotate(self, nums: list[int], k: int) -> None:
        n = len(nums)
        k %= n
        
        def reverse(start: int, end: int) -> None:
            while start < end:
                nums[start], nums[end] = nums[end], nums[start]
                start += 1
                end -= 1
        
        reverse(0, n - 1)
        reverse(0, k - 1)
        reverse(k, n - 1)
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[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }
}

Complexity Analysis

Time Complexity: O(n)

Each of the three reversal operations processes a portion of the array. The first reversal touches all n elements. The second reversal touches k elements. The third reversal touches n-k elements. Total element operations: n + k + (n-k) = 2n. Each operation is a constant-time swap. So overall: O(2n) = O(n).

Space Complexity: O(1)

All reversals are done in-place using only a temporary variable for swapping. No additional arrays or data structures are allocated regardless of input size. This is the key advantage over the extra array approach.