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 exactly what the statement describes: pop the last element and insert it at the front, k times.

from typing import List

def rotate(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, far too slow for the constraints.

Approach 2 — Extra array with index arithmetic

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

def rotate(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)

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 leaves each block internally reversed; reversing each block individually fixes that. Every reversal is a two-pointer swap from both ends.

from typing import List

def rotate(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)

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 has not reached n. This is the classical juggling algorithm for array rotation: walk the permutation’s cycles, carrying one displaced value at a time.

from typing import List

def rotate(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 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 easier to write correctly.