Rotate Array

Problem Description

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

Examples

Constraints

• 1 <= nums.length <= 10⁵
• -2³¹ <= nums[i] <= 2³¹ - 1
• 0 <= k <= 10⁵

In-Place Reversal Trick

While allocating a new array and copying elements to their new indices (i + k) % n takes O(n) space, we can rotate the array in-place using a triple-reversal algorithm. First, compute k = k % n. Second, reverse the entire array. Third, reverse the first k elements. Fourth, reverse the remaining n - k elements. For example, rotating [1,2,3,4,5,6,7] by k = 3:

• Reverse all: [7,6,5,4,3,2,1]
• Reverse first 3: [5,6,7,4,3,2,1]
• Reverse remaining: [5,6,7,1,2,3,4] This rotates the array in-place using O(1) extra space.

Solution 1: Three Reversals

Reverse parts of the array in three separate phases to complete rotation in-place.

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k = k % n; // handle k larger than array size
        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--;
        }
    }
}

class Solution:
    def rotate(self, nums: list[int], k: int) -> None:
        n = len(nums)
        k = k % n  # handle k larger than array size
        
        def reverse(start: int, end: int):
            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)

#include <vector>
#include <algorithm>

class Solution {
private:
    void reverse(std::vector<int>& nums, int start, int end) {
        while (start < end) {
            std::swap(nums[start], nums[end]);
            start++;
            end--;
        }
    }

public:
    void rotate(std::vector<int>& nums, int k) {
        int n = nums.size();
        k = k % n; // handle k larger than array size
        reverse(nums, 0, n - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, n - 1);
    }
};

Complexity Analysis

• Time Complexity: O(n) since we visit each element at most twice during the reversals.
• Space Complexity: O(1) auxiliary space as all modifications are made in-place.

Where It Breaks

If the rotation count k is negative, this modulo formula must be adjusted using k = (k % n + n) % n.

Common Mistakes

• Incorrect Modulo Operator: Failing to run k = k % n, which leads to an index out of bounds exception when k exceeds the array size.
• Off-by-one errors on reverse limits: Setting bounds incorrectly, e.g. reversing 0 to k instead of k - 1.

Frequently Asked Questions

Why does three reversals rotate the array? Reversing the array moves the last k elements to the front (but in reverse order) and the first n-k elements to the back (in reverse order). Reversing each block separately restores their original order.

Can we solve this using cyclic replacements? Yes, but tracking the numbers of elements visited and identifying cyclic loops makes it harder to implement than the triple-reversal approach.

← All Problems