Rotate Array — Solution

Problem

Given an integer array and a non-negative integer k, shift every element k positions to the right, wrapping elements that fall off the end back to the beginning. The modification must happen in-place.

Example:

• Input: nums = [1, 2, 3, 4, 5, 6, 7], k = 3
• Output: [5, 6, 7, 1, 2, 3, 4]
• Explanation: The last 3 elements (5, 6, 7) wrap to the front; the first 4 elements shift right by 3 positions.

Counter-example: k = 7 on the same array gives back [1, 2, 3, 4, 5, 6, 7] — identical to the input — because rotating by the full length completes a cycle. Always reduce k modulo n first.

Intuition

Rotating right by k is exactly the same as moving the last k elements to the front. The three-reversal trick exploits a clean algebraic fact: reversing the whole array places those last k elements at the front but in reverse order, and then reversing each half independently restores their original relative order — yielding the correct rotation in O(n) time with no extra memory.

Approach 1 — Brute Force

Perform k individual one-step rotations, each time saving the last element and shifting everything else one position to the right.

Steps:

1. Reduce k with k = k % n to skip full-cycle rotations.
2. Repeat k times: save nums[n-1], shift every element right by one scanning right to left, place the saved value at nums[0].

1def rotate(nums: list[int], k: int) -> None:
2    n = len(nums)
3    k = k % n
4    for _ in range(k):
5        last = nums[-1]                    # element that wraps around to position 0
6        for i in range(n - 1, 0, -1):
7            nums[i] = nums[i - 1]
8        nums[0] = last

• Time: O(n × k) — each of k rotations shifts all n elements one position
• Space: O(1) — one temporary variable regardless of input size

Approach 2 — Extra Array

Place each element directly at its final position in a new array using the formula (i + k) % n, then copy back into nums.

Steps:

1. Compute k = k % n.
2. Allocate a result array of the same length.
3. Write nums[i] to result[(i + k) % n] for every index.
4. Copy result back into nums in-place.

1def rotate(nums: list[int], k: int) -> None:
2    n = len(nums)
3    k = k % n
4    rotated = [0] * n
5    for i in range(n):
6        rotated[(i + k) % n] = nums[i]    # jump each element k spots ahead, wrapping around
7    nums[:] = rotated                      # slice assignment mutates in-place; nums = rotated would not

• Time: O(n) — one pass to compute positions, one pass to copy back
• Space: O(n) — auxiliary array of length n

Approach 3 — Three Reversals

Reverse the entire array, then reverse the first k elements, then reverse the remaining n-k elements. After the global flip the last-k block is at the front but internally reversed; each sub-reversal restores its segment's original left-to-right order.

Steps:

1. Compute k = k % n.
2. Reverse the entire array (indices 0 to n-1).
3. Reverse the first k elements (indices 0 to k-1).
4. Reverse the remaining elements (indices k to n-1).

1def rotate(nums: list[int], k: int) -> None:
2    n = len(nums)
3    k = k % n
4
5    def reverse(left: int, right: int) -> None:
6        while left < right:
7            nums[left], nums[right] = nums[right], nums[left]
8            left, right = left + 1, right - 1
9
10    reverse(0, n - 1)   # flip everything so last k land at the front, reversed
11    reverse(0, k - 1)   # un-flip first k back to their original left-to-right order
12    reverse(k, n - 1)   # un-flip trailing n-k back to their original left-to-right order

• Time: O(n) — three reversal passes that together touch every element exactly twice
• Space: O(1) — all swaps are in-place with no auxiliary storage

Complexity Summary

Common Mistakes

• Forgetting k = k % n — when k equals n, rotating by the full length returns the original array unchanged; without the modulo, the brute-force runs n useless sweeps and the three-reversal approach passes k=n to its first sub-reversal, which silently produces the wrong result by treating the "second half" as empty.
• Reversing the two halves before the full array — the three-reversal technique requires the global flip first; reversing the halves before the whole array produces a different permutation that is not a rotation of the original input.
• Reassigning nums instead of mutating it in Python — writing nums = rotated rebinds the local variable but leaves the caller's list untouched; nums[:] = rotated performs an in-place copy that actually modifies the original object.
• Overwriting source values in Approach 2 without a separate array — applying nums[(i + k) % n] = nums[i] directly on nums corrupts values at destination indices before they've been read, because rotation offsets cause reads and writes to overlap whenever k is not a multiple of n.
• Confusing k and n-k as the split point — after the global flip, the block that needs to land at the front spans exactly k elements (indices 0 to k-1); using n-k as the boundary gives the correct structure but in the wrong half, rotating the array in the opposite direction.

Related Problems

• rotate-image — applies the same reversal-based rotation idea in two dimensions: transpose then reflect to rotate a matrix 90 degrees in-place
• reverse-string — the two-pointer reversal primitive that Approach 3 is built on
• next-permutation — in-place rearrangement whose final step reverses a suffix, the same operation as Approach 3's third reversal
• product-of-array-except-self — O(n) in-place transformation using a left-to-right pass followed by a right-to-left pass, mirroring the multi-sweep structure of Approach 3