Rotate Array

Problem

Given an integer array nums, rotate it to the right by k steps, in place. Rotating right by one step moves the last element to the front; rotating by k does that k times. k can be larger than the array length.

The function returns nothing — mutate nums directly.

Examples

Example 1

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

The last three elements wrap around to the front.

Example 2

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

Two right rotations: [99, -1, -100, 3] then [3, 99, -1, -100].

Example 3

Input:  nums = [1, 2], k = 5
Output: nums = [2, 1]

k = 5 on length 2 is the same as k = 5 % 2 = 1.

Constraints

• 1 <= nums.length <= 10^5
• -2^31 <= nums[i] <= 2^31 - 1
• 0 <= k <= 10^5
• Follow-up: O(1) extra space, and there are at least three different ways to do it.

Think about it first

TL;DR

Triple reversal — reverse all, reverse the first k, reverse the rest — O(n) time, O(1) space.

Approach 1 — Brute force (rotate one step, k times)

Do literally what the statement says: pop the last element and push it onto the front, k times.

from typing import List

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        n = len(nums)
        k %= n
        for _ in range(k):
            last = nums.pop()
            nums.insert(0, last)

Complexity: O(n * k) time (each insert(0, ...) shifts the whole array), O(1) space. With n and k both up to 10^5 that’s ~10^10 element moves — hopelessly slow.

Approach 2 — Extra array with index arithmetic

The insight: rotation is a permutation with a closed form — the element at index i ends at index (i + k) % n. Build the result directly, then copy it back.

from typing import List

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        n = len(nums)
        k %= n
        rotated = [0] * n
        for i in range(n):
            rotated[(i + k) % n] = nums[i]
        nums[:] = rotated

Walkthrough on nums = [1, 2, 3, 4, 5, 6, 7], k = 3 (n = 7):

• 1 (i=0) → index 3, 2 → 4, 3 → 5, 4 → 6, 5 (i=4) → (4+3) % 7 = 0, 6 → 1, 7 → 2.
• rotated = [5, 6, 7, 1, 2, 3, 4]. ✓

Complexity: O(n) time, O(n) space — fails only the O(1)-space follow-up.

Approach 3 — Triple reversal (two pointers, in place)

The insight: a right-rotation by k swaps the order of two blocks: [first n-k | last k] becomes [last k | first n-k]. Reversing the entire array puts the blocks in the right order but each block internally backwards; reversing each block individually fixes that. Every reversal is a classic two-pointer swap from both ends.

from typing import List

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

        def rev(lo: int, hi: int) -> None:
            while lo < hi:
                nums[lo], nums[hi] = nums[hi], nums[lo]
                lo += 1
                hi -= 1

        rev(0, n - 1)      # whole array
        rev(0, k - 1)      # first k
        rev(k, n - 1)      # remaining n - k

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

1. Reverse all: [7, 6, 5, 4, 3, 2, 1]
2. Reverse first 3: [5, 6, 7, 4, 3, 2, 1]
3. Reverse last 4: [5, 6, 7, 1, 2, 3, 4] ✓

Complexity: O(n) time (each element swapped at most twice), O(1) space.

Approach 4 — Cyclic replacements (the juggling algorithm)

The insight: repeatedly placing each element directly at its destination (i + k) % n traces out cycles of the permutation. Following one cycle displaces every element on it correctly; the cycles partition the array into gcd(n, k) groups, so start a new cycle from the next index whenever the count of placed elements hasn’t reached n. This is the classical juggling algorithm for array rotation — walking the permutation’s cycles while carrying one displaced value in hand.

from typing import List

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        n = len(nums)
        k %= n
        if k == 0:
            return
        placed = 0
        start = 0
        while placed < n:
            current = start
            carry = nums[start]
            while True:
                nxt = (current + k) % n
                nums[nxt], carry = carry, nums[nxt]
                current = nxt
                placed += 1
                if current == start:
                    break
            start += 1

Walkthrough on nums = [-1, -100, 3, 99], k = 2 (n = 4, gcd = 2 → two cycles):

• Cycle from 0: carry -1 → place at 2 (pick up 3) → place 3 at 0. Array: [3, -100, -1, 99], placed = 2.
• Cycle from 1: carry -100 → place at 3 (pick up 99) → place 99 at 1. Array: [3, 99, -1, -100], placed = 4. ✓

Complexity: O(n) time (each element placed exactly once), O(1) space.

Common pitfalls

• Forgetting k %= n: k may exceed the length; without the modulo, index math breaks or the brute force loops far longer than needed.
• Reversing blocks in the wrong order or wrong sizes: for a right rotation it’s whole → first k → last n - k. (A left rotation flips which block is first.)
• Cycle counting in the juggling method: stopping after one cycle silently leaves gcd(n, k) - 1 cycles untouched — the placed counter (or iterating gcd start points) is mandatory.
• Rebinding instead of mutating: nums = rotated inside the method changes the local name only; the judge sees the original list. Use nums[:] = rotated.

Pattern takeaway

The reversal identity — reverse the whole, then reverse each block — converts any “swap two adjacent blocks in place” problem into three two-pointer reversals, each trivially O(1) space. When a rearrangement is a clean permutation formula, you have two in-place options: algebraic (follow the permutation’s cycles) or structural (decompose into reversals); the reversal route is almost always the easier one to write correctly under interview pressure.