DSA Reversing an Array in Place

The problem

Reversing a list in place flips the order of its values. The same list holds the result. No second list is built.

The first value trades places with the last value. The second value trades with the second last value. The pattern continues inward.

cases = [
    [1, 2, 3, 4, 5],
    ['Ana', 'Bo', 'Cy', 'Dee'],
    [1, 2, 3],
    [7],
]
for values in cases:
    print(values, '->', values[::-1])

Intuition

The first idea is often to build a new list. Read the old list from the back. Append each value to the new list.

That idea gives the right order. It also spends a second list of the same size. The problem asks for the flip inside the same list, so the extra list is the cost to remove.

values = [1, 2, 3, 4, 5]
flipped = []
for index in range(len(values) - 1, -1, -1):
    flipped.append(values[index])
print('new list:', flipped)
print('original:', values)
print('extra cells used:', len(flipped))

Brute force

A slow in-place method uses pop and insert. The last value belongs at the front after a reversal. The next last value belongs in the second cell, and so on.

Each pop and insert shifts the values between the two ends. The shifts repeat work that a single swap would finish.

values = [1, 2, 3, 4, 5]
moves = 0
for front in range(len(values) - 1):
    value = values.pop()
    moves += 1
    for index in range(front, len(values)):
        moves += 1
    values.insert(front, value)
print('result:', values)
print('pops, inserts and shifted cells counted as moves:', moves)

The method works. Its cost grows fast, because later shifts move over ground that earlier shifts already crossed. One swap per pair avoids the shifting entirely.

The optimal solution: swap pairs from the ends

The key idea is one swap per pair. Two indices start at the ends and walk toward each other, swapping the values they point at.

def reverse_in_place(values):
    left = 0
    right = len(values) - 1
    while left < right:
        values[left], values[right] = values[right], values[left]
        left += 1
        right -= 1
    return values

cases = [
    [1, 2, 3, 4, 5],
    ['Ana', 'Bo', 'Cy', 'Dee'],
    [1, 2, 3],
    [7],
]
for values in cases:
    print(values, '->', reverse_in_place(list(values)))

Walkthrough

Take the list [1, 2, 3, 4, 5]. The left index starts at 0. The right index starts at 4.

values = [1, 2, 3, 4, 5]
left = 0
right = len(values) - 1
while left < right:
    values[left], values[right] = values[right], values[left]
    print('swapped positions', left, 'and', right, ':', values)
    left += 1
    right -= 1
print('indices meet at value:', values[left])

The first swap settles 5 and 1. The second swap settles 4 and 2. The indices then meet at 3, and the middle value stays put.

Complexity

Time is O(n). Each swap settles two values, and a list of n values needs n // 2 swaps.

Space is O(1). Two indices and one swap are the only extra storage.

def swaps_needed(n):
    values = list(range(n))
    left = 0
    right = n - 1
    swaps = 0
    while left < right:
        values[left], values[right] = values[right], values[left]
        swaps += 1
        left += 1
        right -= 1
    return swaps

for n in [4, 8, 16]:
    print('n =', n, 'swaps:', swaps_needed(n))

Edge cases and pitfalls

An empty list has no pair to swap. A single value is already reversed. The loop condition left < right handles both cases without a special branch.

The common mistake is stepping only one index. The pair then swaps the wrong cells, and one end is visited twice. Both indices must step after every swap.

def reverse_in_place(values):
    left = 0
    right = len(values) - 1
    while left < right:
        values[left], values[right] = values[right], values[left]
        left += 1
        right -= 1
    return values

print('empty:', reverse_in_place([]))
print('single:', reverse_in_place([7]))
print('even:', reverse_in_place([1, 2, 3, 4]))
print('odd:', reverse_in_place([1, 2, 3]))
print('duplicates:', reverse_in_place([2, 2, 1]))