Rotate Array · DSA Prep

Rotating right by k moves the last k elements to the front while preserving order — imagine breaking the ring between positions n - k and n - k + 1 and rethreading it. The pattern insight is to avoid moving elements one at a time and instead lean on the fact that a reversal is its own inverse: reverse the whole array, and each block ends up exactly where it should start from, just backwards. Two more small reversals fix the direction inside each block. Because a segment of length m is flipped with only about m / 2 swaps, the three reversals together touch every element about once — a linear, in-place solution using no extra array.

Brute Force: Pop + Insert Front

Time O(n·k)Space O(1)

Model the rotation literally: to rotate right by one step, take the last element off the back and drop it at the front. Doing that k times yields the rotated array. Start by normalizing k with k %= n, because rotating by the array length exactly returns the original array — n extra full spins add nothing, so any k larger than n can be reduced to its remainder.

class Solution:
    def rotate(self, nums: list[int], k: int) -> None:
        n = len(nums)
        k %= n
        for _ in range(k):
            # Take the last element off the back and drop it at the front.
            nums.insert(0, nums.pop())

Why it is slow: grabbing the back with pop is O(1), but insert(0, ...) must shift every existing element one slot to the right to make room — an O(n) walk. Repeating that shift k times gives O(n·k) time in the worst case, which degrades to quadratic when k is close to n. The in-place swap means extra space stays O(1), but the re-shifting of the whole tape on every step makes it wasteful for large inputs.

Three Reversals

OptimalTime O(n)Space O(1)

A reversal is its own inverse, so a single array can be reorganized with pure in-place swaps. Normalize k %= n first. Then:

Reverse the entire array — the two target blocks swap sides, each arriving where it will end up, just backwards.
Reverse the first k elements — restores the original order of the block that should lead.
Reverse the last n - k elements — restores the original order of the block that should trail.

class Solution:
    def rotate(self, nums: list[int], k: int) -> None:
        def reverse(i: int, j: int) -> None:
            while i < j:
                nums[i], nums[j] = nums[j], nums[i]
                i += 1
                j -= 1

        n = len(nums)
        k %= n
        reverse(0, n - 1)   # whole array
        reverse(0, k - 1)   # block that should move to the front
        reverse(k, n - 1)   # block that should move to the back

Watch the whole trick on the file example, nums = [1,2,3,4,5,6,7], k = 3: reverse all, then [0..2], then [3..6] — the final tape is [5,6,7,1,2,3,4].

reverse all · swap nums[0] ⇄ nums[6]

nums — one array, rotated in place

◀ l

r ▶

reversing segment [0..6]keyed swap · nums[0] = 1 ⇄ nums[6] = 7

each reversal walks an inward pointer pair toward the center — one swap flips two cells — so reversing a segment of length m takes about m/2 swaps

1 / 9

currentcomparingresultseen

Rotating right is not a single move of one element. The three-reversal trick: reverse the whole array, then reverse the first k elements, then reverse the rest. First pass over segment [0..6]: the inward pointers start at the two ends. Swap 1 and 7 — the pair slides one step toward the center.

Then the shorter run nums = [-1,-100,3,99], k = 2: three reversals, fewer cells, same shape — the answer is [3,99,-1,-100].

reverse all · swap nums[0] ⇄ nums[3]

nums — one array, rotated in place

-10

◀ l

-1001

993

r ▶

reversing segment [0..3]keyed swap · nums[0] = -1 ⇄ nums[3] = 99

each reversal walks an inward pointer pair toward the center — one swap flips two cells — so reversing a segment of length m takes about m/2 swaps

1 / 7

currentcomparingresultseen

Second example with k = 2: n = 4, and k %= n leaves k = 2 unchanged. Same three reversals, fewer cells. First: reverse the whole array over segment [0..3] — swap -1 and 99.

Why it is linear and in-place: reversing a segment of length m performs floor(m / 2) swaps. The three reversals split the array into non-overlapping coverage, so the swap counts sum to (n / 2) + (k / 2) + ((n - k) / 2) = n — each element is swapped at most once per reversal it participates in, giving O(n) total time. No extra array is ever allocated, so space is O(1). The k %= n guard also handles the edge cases: k = 0 or k = n reverses nothing (the two halves of a full-length flip cancel), and a single element rotates onto itself.

Why three reversals work: the reversal is self-inverse, so the structure survives composition. Reversing everything puts the last k elements at the front; reversing the first k un-does the reversal only within that leading block; reversing the rest un-does it within the trailing block. Each block returns to its original relative order but on its new side of the cut — precisely a right rotation by k.