Rotate Array

Given an integer array nums and a non-negative integer k, rotate the array to the right by k positions. One rotation step moves the last element to the front and shifts every other element one place to the right.

Modify nums in place; your function does not return anything. Note that k may be larger than the length of the array.

Can you do it with O(1) extra space?

Example 1

Example 2

Example 3

Constraints

• 1 <= nums.length <= 105
• -231 <= nums[i] <= 231 - 1
• 0 <= k <= 105

Pattern Path · Two Pointers · problem 24 of 169

Start simple

Rotate one step at a time, k times, shifting every element each time: O(n·k) time, O(1) space.

The key idea

First reduce k with k %= n, since every n rotations bring the array back to where it started.

Split the array into two blocks: A, the first n - k elements, and B, the last k. Rotating right by k turns A B into B A with each block's internal order unchanged. Reversing the whole array gives rev(B) rev(A): the blocks are in the right places, but each is backwards. Reversing each block again fixes that, leaving B A.

So the algorithm is three in-place reversals: the whole array, then the first k elements, then the remaining n - k. Each reversal is a two-pointer swap loop, so every element is moved a constant number of times and only a couple of index variables are needed. (Cycle replacement, following i → (i + k) % n around each cycle, is another O(1)-space method but is easier to get wrong.)

Complexity

• Time: O(n)
• Space: O(1)

Python

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        n = len(nums)
        k %= n

        def reverse(lo, hi):
            while lo < hi:
                nums[lo], nums[hi] = nums[hi], nums[lo]
                lo += 1
                hi -= 1

        reverse(0, n - 1)  # A B   ->  rev(B) rev(A)
        reverse(0, k - 1)  # fix B
        reverse(k, n - 1)  # fix A

JavaScript

var rotate = function(nums, k) {
  const n = nums.length;
  k %= n;

  const reverse = (lo, hi) => {
    while (lo < hi) {
      [nums[lo], nums[hi]] = [nums[hi], nums[lo]];
      lo++;
      hi--;
    }
  };

  reverse(0, n - 1); // A B  ->  rev(B) rev(A)
  reverse(0, k - 1); // fix B
  reverse(k, n - 1); // fix A
};

What the interviewer is checking

Beyond the easy extra-array version, the interviewer wants the O(1)-space reversal trick and a clear argument for why three reversals produce a rotation; handling k ≥ n is the classic check.

Mistakes to avoid

• Not reducing k modulo n, which breaks the block split or indexes out of range.
• Rotating left instead of right (reversing the blocks in the wrong order).
• Reassigning the variable (nums = ...) instead of writing into the original array, so the caller sees no change.

Follow-ups to expect

• Rotate to the left by k. (Reverse the blocks the other way.)
• Rotate a linked list by k. (Find new tail, relink once.)
• Rotate a string with only swaps. (Same three reversals.)

In real software

Circular buffers, image and audio shifting, and text editors moving a block of lines (the classic "swap two adjacent ranges" operation used by std::rotate) all rely on in-place rotation.

Practice next