Rotate Array In Place: The Three-Reversal Trick

Rotate array is an easy question with a constraint that makes it interesting: do it in place. Rotating [1, 2, 3, 4, 5] right by 2 gives [4, 5, 1, 2, 3], and with a spare array that is one line of slicing. Without one, you need an idea, and the idea most people remember is three reversals. It is short, it is linear, and it is easy to get subtly wrong at the edges, which is where interviewers look.

The problem it solves

Given an array and a non-negative k, shift every element k places to the right, wrapping the last k elements round to the front. The array must be modified in place.

Three approaches, in the order people usually find them:

• Shift by one, k times. Save the last element, slide everything right, put it at the front. O(n · k) time, O(1) space. Too slow when k is close to n.
• Copy. Write each element to index (i + k) % n of a new array, then copy back. O(n) time, but O(n) extra space.
• Three reversals. O(n) time, O(1) extra space, and no index arithmetic beyond k % n.

The intuition

Rotating right by k means the last k values move to the front and keep their order, and the first n - k values move to the back and keep theirs. Think of the array as two blocks, A (the first n - k values) followed by B (the last k). The goal is B followed by A.

Reversing the whole array puts B in front of A, but reverses each block internally. For [1, 2, 3 | 4, 5] you get [5, 4 | 3, 2, 1]: the right values in the right places, each block backwards. Now reverse the first k positions and then the remaining n - k, and each block reads forwards again: [4, 5 | 1, 2, 3].

Before any of that, reduce k modulo n. Rotating by a full length changes nothing, so rotating by k is the same as rotating by k % n, and without the reduction k could exceed the array and the block boundaries would point past the end.

Rotating left by k is rotating right by n - k, or equivalently, the same three reversals with the blocks reversed first and the whole array last.

Watch it run

The animation rotates [1, 2, 3, 4, 5] right by k = 2: the last two values have to end up at the front, in order. It reverses [0..4] by swapping the ends and stepping both markers inward, twice, and the middle value stays put. The whole row is flipped, so the last two are at the front already, just backwards, and so is the rest. Reversing [0..1] takes one swap and puts the first block back in order. Then the same for everything after index 1: reversing [2..4] takes one more swap. Three reversals and four swaps, no second array, and a rotation by a full length would have been reduced to nothing by k % n.

The code

The lesson's version, with one reverse helper used three times:

def rotate(nums, k):
    if not nums:
        return nums
    k %= len(nums)

    def reverse(lo, hi):
        while lo < hi:
            nums[lo], nums[hi] = nums[hi], nums[lo]
            lo, hi = lo + 1, hi - 1

    reverse(0, len(nums) - 1)            # flip the whole row
    reverse(0, k - 1)                    # put the first block back in order
    reverse(k, len(nums) - 1)            # and the rest
    return nums

print(rotate([1, 2, 3, 4, 5], 2))        # [4, 5, 1, 2, 3]
print(rotate([1, 2, 3, 4, 5], 7))        # [4, 5, 1, 2, 3]   7 % 5 == 2
print(rotate([1, 2, 3], 3))              # [1, 2, 3]
print(rotate([], 4))                     # []

The array after each reversal, the three states the animation settles on:

nums, k = [1, 2, 3, 4, 5], 2
for lo, hi in [(0, 4), (0, k - 1), (k, 4)]:
    nums[lo:hi + 1] = nums[lo:hi + 1][::-1]
    print(nums)
# [5, 4, 3, 2, 1]
# [4, 5, 3, 2, 1]
# [4, 5, 1, 2, 3]

The other in-place answer is cyclic replacement: pick up a value, drop it k places ahead, pick up the one it displaced, and continue until you return to the start. The moves split into gcd(n, k) separate cycles, so run one cycle from each of the first gcd(n, k) positions:

from math import gcd

def rotate_cycles(nums, k):
    n = len(nums)
    if n == 0:
        return nums
    k %= n
    for start in range(gcd(n, k) if k else 0):
        i, carry = start, nums[start]
        while True:
            j = (i + k) % n
            nums[j], carry = carry, nums[j]   # drop the value, pick up the next
            i = j
            if i == start:
                break
    return nums

print(rotate_cycles([1, 2, 3, 4, 5, 6], 2))   # [5, 6, 1, 2, 3, 4]
print(gcd(6, 2))                             # 2   two cycles: evens and odds

Both against a brute force that shifts by one step k times, and against slicing, on 5,000 random arrays with k often larger than the length:

import random

def brute(nums, k):
    out = list(nums)
    for _ in range(k):
        if out:
            out = [out[-1]] + out[:-1]   # one step right
    return out

random.seed(20)
ok = True
for _ in range(5000):
    nums = [random.randint(0, 9) for _ in range(random.randint(0, 10))]
    k = random.randint(0, 25)
    want = brute(nums, k)
    ok &= rotate(list(nums), k) == want == rotate_cycles(list(nums), k)
    if nums:
        s = k % len(nums)
        ok &= want == nums[len(nums) - s:] + nums[:len(nums) - s]
print(ok)                                # True

The complexity

• Three reversals: O(n) time, since every element is swapped at most twice, roughly n swaps in total. O(1) extra space.
• Cyclic replacement: O(n) time with exactly n moves, one per element, and O(1) extra space. Fewer writes, harder to get right.
• Copy or slicing: O(n) time and O(n) extra space. Fine unless the question forbids it.
• Shift by one: O(n · k), which is O(n²) when k is near n.

Where it goes wrong

• Skipping k %= n. With k = 7 on five elements, reverse(0, 6) reaches past the end.
• Dividing by zero on an empty array. k % 0 raises; return early when there is nothing to rotate.
• Reversing the blocks in the wrong order for the direction. Whole-then-blocks rotates right; blocks-then-whole rotates left. Test both on a small array.
• Off-by-one block edges. The first block is 0..k-1 and the second is k..n-1; writing 0..k swaps one value too many.
• Running one cycle in the cyclic version. When gcd(n, k) is more than 1, a single cycle moves only part of the array.
• Assigning nums = nums[-k:] + nums[:-k] in a function. That rebinds a local name and leaves the caller's list unchanged; use nums[:] = ... if slicing is allowed.

When it shows up in interviews

It is a common easy question on arrays where the point is the follow-up: "now do it with O(1) extra space." The reversal trick uses the same inward-swapping two pointers as reversing a linked list and rotating a matrix in place, which is built from a transpose plus a reversal of each row. Rotation also underlies search in a rotated sorted array.

How to say it in an interview

"Rotating right by k moves the last k values to the front with their order kept. I first reduce k modulo n, since a full rotation changes nothing. Then I reverse the whole array, which puts the last k values at the front but backwards, and reverse the first k and the remaining n - k separately to fix each block's order. Each reversal is two pointers swapping inward, so the whole thing is O(n) time and O(1) extra space. An alternative with exactly one move per element is cyclic replacement, running gcd(n, k) cycles."