Rotate Array Algorithm

Rotate an array to the right by k steps. In-place. O(1) extra space.

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

The naive approach — pop from the end and unshift to the front, k times — works but costs O(n*k). There's a much better trick.

The intuition: three reverses

Think of the array as two halves: the part that wraps around, and the part that shifts left. If you reverse the entire array, then reverse each half separately, the elements land exactly where they should.

For [1,2,3,4,5,6,7] with k=3:

1. Reverse all: [7,6,5,4,3,2,1]
2. Reverse first k: [5,6,7,4,3,2,1]
3. Reverse the rest: [5,6,7,1,2,3,4]

It feels like a magic trick the first time you see it. But it's just the math of reversal being its own inverse.

function reverse(nums, start, end) {
    while (start < end) {
        [nums[start], nums[end]] = [nums[end], nums[start]];
        start++;
        end--;
    }
}

var rotate = function(nums, k) {
    k = k % nums.length;
    reverse(nums, 0, nums.length - 1);
    reverse(nums, 0, k - 1);
    reverse(nums, k, nums.length - 1);
};

Complexity

• Time: O(n) — three passes, each linear.
• Space: O(1) — swaps in-place.

The detail people miss

k = k % nums.length. If k equals the array length, the array stays the same. If k is larger, you only care about the remainder. Skip that line and you'll reverse the wrong segments.