Rotate Array

Intuition

Rotating an array right by k means every element moves k steps to the right (wrapping around). Doing this by shifting one step at a time is O(nk)—too slow. Instead, notice that reversing segments rearranges positions efficiently.

Approach

1. Normalize k = k % n (rotating by n does nothing).
2. Reverse the whole array.
3. Reverse the first k elements.
4. Reverse the remaining n - k elements.

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

• Reverse all → [7,6,5,4,3,2,1]
• Reverse first 3 → [5,6,7,4,3,2,1]
• Reverse last 4 → [5,6,7,1,2,3,4]

Edge cases

• k % n == 0 → no-op.
• n == 0 or 1 → no-op.

Proof of Correctness

Let R be reverse. After step 2, element originally at index i moves to n-1-i. The desired final position for original index i is (i + k) mod n. Applying R to the prefix [0..k-1] and suffix [k..n-1] restores the relative order within the two groups corresponding to the rotated partition, placing each element exactly at (i + k) mod n. Thus the sequence equals the array rotated right by k.

Complexity

• Time: O(n) (each element is reversed at most twice).
• Space: O(1) extra space.

Code

export function rotate(nums: number[], k: number): void {
  const n = nums.length;
  if (n <= 1) return;
  k = k % n;
  if (k === 0) return;

  const reverse = (l: number, r: number) => {
    while (l < r) {
      [nums[l], nums[r]] = [nums[r], nums[l]];
      l++; r--;
    }
  };

  reverse(0, n - 1);
  reverse(0, k - 1);
  reverse(k, n - 1);
}

class Solution(object):
    def rotate(self, nums, k):
        n = len(nums)
        if n <= 1:
            return
        k %= n
        if k == 0:
            return

        def reverse(l, r):
            while l < r:
                nums[l], nums[r] = nums[r], nums[l]
                l += 1
                r -= 1

        reverse(0, n - 1)
        reverse(0, k - 1)
        reverse(k, n - 1)