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
kelements — restores the original order of the block that should lead. - Reverse the last
n - kelements — 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 backWatch 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].
nums — one array, rotated in place
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
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].
nums — one array, rotated in place
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
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.