DSA Rotating an Array

The problem

Rotating a list right by k shifts every value k places to the right. Values that fall off the right end reappear at the front. The order of the values does not change.

A rotation by k uses k after a wrap. A list of five values rotated by seven behaves the same as a rotation by two.

cases = [
    ([1, 2, 3, 4, 5], 2, [4, 5, 1, 2, 3]),
    ([1, 2, 3, 4, 5, 6, 7], 3, [5, 6, 7, 1, 2, 3, 4]),
    ([1, 2, 3], 0, [1, 2, 3]),
    ([1, 2, 3, 4, 5], 7, [4, 5, 1, 2, 3]),
]
for values, k, expected in cases:
    print(values, 'right by', k, '->', expected)

Intuition

The first idea is a rotation by one. Pop the last value. Insert it at the front.

Repeating that step k times gives the answer. The trap is cost and wrap. A large k repeats whole turns of the list that change nothing.

values = [1, 2, 3, 4, 5]
for step in range(2):
    last = values.pop()
    values.insert(0, last)
    print('after step', step + 1, ':', values)

Brute force

The repeated single rotation is the brute force. Each step moves every value in the list. Inserting at the front shifts the other values right.

def rotate_brute(values, k):
    moves = 0
    n = len(values)
    for _ in range(k % n):
        last = values.pop()
        moves += n
        values.insert(0, last)
    return values, moves

for n, k in [(5, 2), (10, 4), (20, 8)]:
    result, moves = rotate_brute(list(range(1, n + 1)), k)
    print('n =', n, 'k =', k, 'moves:', moves, 'first values:', result[:3])

The count grows with both n and k. A rotation method should touch each value a fixed number of times. It should not depend on k in this way.

The optimal solution: three reversals

The key idea is three reversals. Reverse the whole list, then reverse the first k values, then reverse the rest.

def reverse_part(values, left, right):
    while left < right:
        values[left], values[right] = values[right], values[left]
        left += 1
        right -= 1

def rotate(values, k):
    n = len(values)
    if n == 0:
        return values
    k = k % n
    reverse_part(values, 0, n - 1)
    reverse_part(values, 0, k - 1)
    reverse_part(values, k, n - 1)
    return values

cases = [
    ([1, 2, 3, 4, 5], 2),
    ([1, 2, 3, 4, 5, 6, 7], 3),
    ([1, 2, 3], 0),
    ([1, 2, 3, 4, 5], 7),
]
for values, k in cases:
    print(values, 'right by', k, '->', rotate(list(values), k))

Walkthrough

Take [1, 2, 3, 4, 5] with k = 2. The last two values must reach the front. The three stages below move them there.

def reverse_part(values, left, right):
    while left < right:
        values[left], values[right] = values[right], values[left]
        left += 1
        right -= 1

values = [1, 2, 3, 4, 5]
print('start:', values)
reverse_part(values, 0, 4)
print('reversed all:', values)
reverse_part(values, 0, 1)
print('reversed first 2:', values)
reverse_part(values, 2, 4)
print('reversed rest:', values)

The first reversal lands 4 and 5 at the front in reverse order. The second reversal fixes the front pair. The third reversal restores the order of the back part.

Complexity

Time is O(n). The three reversals together swap each pair at most once per stage, and the stages are fixed at three.

Space is O(1). The reversals swap inside the same list and build no copy.

def rotate_swaps(n, k):
    values = list(range(n))
    swaps = 0
    def rev(left, right):
        nonlocal swaps
        while left < right:
            values[left], values[right] = values[right], values[left]
            swaps += 1
            left += 1
            right -= 1
    k = k % n
    rev(0, n - 1)
    rev(0, k - 1)
    rev(k, n - 1)
    return swaps

for n in [5, 10, 20]:
    print('n =', n, 'k = 2 swaps:', rotate_swaps(n, 2))

Edge cases and pitfalls

An empty list has no rotation. The code returns at once, before k % n can divide by zero.

A k of 0 still runs the reversal steps in a plain version. The first and third stages cancel out, and the middle stage reverses an empty stretch. The result is the original list, as the run below shows.

def reverse_part(values, left, right):
    while left < right:
        values[left], values[right] = values[right], values[left]
        left += 1
        right -= 1

def rotate(values, k):
    n = len(values)
    if n == 0:
        return values
    k = k % n
    reverse_part(values, 0, n - 1)
    reverse_part(values, 0, k - 1)
    reverse_part(values, k, n - 1)
    return values

print('empty:', rotate([], 3))
print('single:', rotate([9], 5))
print('k = 0:', rotate([1, 2, 3], 0))
print('k = n:', rotate([1, 2, 3], 3))
print('k > n:', rotate([1, 2, 3, 4, 5], 7))