Reverse an Array In Place: Swap the Ends, Step Inward

Reversing an array is the smallest useful two-pointer algorithm: swap the first and last elements, step both indexes toward the middle, and stop when they meet. It takes n / 2 swaps and no second array. It is also a building block: rotating an array, reversing words and the next-permutation trick all reverse a range of an array as one of their steps. This article covers the loop, its exact stopping rule, the range version, and which of Python's built-in spellings really work in place.

The problem it solves

reversed_copy = nums[::-1] is one line, and it allocates a second list as long as the first. When the task says "in place", "O(1) extra space", or "modify the input", that copy is not allowed. And when a bigger algorithm needs to reverse only nums[i..j] as one step, slicing and assigning back copies the range every time.

In-place reversal answers both: it rearranges the existing array with two indexes and one swap at a time. For linked lists the job is different, since there is no index to jump to; that version rewires pointers instead, as in reversing a linked list.

The intuition

Position 0 must end up holding what is at position n - 1, and vice versa. Swapping them settles both positions at once, permanently: neither is touched again. Then the same is true of positions 1 and n - 2, and so on inward.

• Each swap fixes two positions, so n positions need n // 2 swaps. With an odd length, the middle element is already where it belongs and never moves.
• The loop runs while left is less than right. When they meet (odd length) or cross (even length), every position is settled. Continue past the middle and each new swap would undo an earlier one: run the loop to the end and you get the original array back.
• Python's tuple swap nums[l], nums[r] = nums[r], nums[l] evaluates the right side first, so no temporary variable is needed.

Generalising from the whole array to nums[i..j] changes only the starting indexes, and that range version is what other algorithms call. The three-reversal rotation is three calls of it, and reversing words in a string is one call for the whole string and one per word.

Watch it run

The animation reverses [1, 2, 3, 4, 5, 6]. Reversal needs no second array: just trade the two ends and walk inward, with extra memory shown as O(1) the whole time. Swap nums[0] and nums[5]. Done: both ends are final. Step inward, left++, right--. Swap nums[1] and nums[4], and those two are final as well. Swap nums[2] and nums[3], and after one more step the indexes have crossed. The array is reversed after n / 2 = 3 swaps, with no copy of the array anywhere. The settled cells turn green two at a time, which is the whole argument for n / 2.

The code

The range version first, since the whole-array reversal is just the call with 0 and len(nums) - 1. It returns its swap count so the n // 2 claim can be checked:

import random
import tracemalloc

def reverse_range(nums, i, j):
    """Reverse nums[i..j] inclusive, in place. Returns the number of swaps."""
    swaps = 0
    while i < j:
        nums[i], nums[j] = nums[j], nums[i]   # both values move in one statement
        i, j = i + 1, j - 1
        swaps += 1
    return swaps

a = [1, 2, 3, 4, 5, 6]
print(reverse_range(a, 0, len(a) - 1), a)   # 3 [6, 5, 4, 3, 2, 1]
b = [1, 2, 3, 4, 5]
print(reverse_range(b, 0, len(b) - 1), b)   # 2 [5, 4, 3, 2, 1]  -> the middle never moves

def reverse_in_groups(nums, k):
    """Reverse every block of k, in place: the range version doing real work."""
    for start in range(0, len(nums), k):
        reverse_range(nums, start, min(start + k, len(nums)) - 1)
    return nums

print(reverse_in_groups([1, 2, 3, 4, 5, 6, 7, 8], 3))   # [3, 2, 1, 6, 5, 4, 8, 7]

# Python's four spellings, and which of them is really in place
a = [1, 2, 3]
same = a
print(a.reverse(), a, same is a)     # None [3, 2, 1] True   (in place, returns None)
c = a[::-1]
print(c, c is a)                     # [1, 2, 3] False       (a new list)
print(list(reversed(a)), a)          # [1, 2, 3] [3, 2, 1]   (an iterator over a)
a[:] = a[::-1]
print(a, same is a)                  # [1, 2, 3] True        (same list, but a temp copy)

s = "stressed"
chars = list(s)                      # str is immutable: reverse a list of its characters
reverse_range(chars, 0, len(chars) - 1)
print("".join(chars))                # desserts

a[:] = a[::-1] keeps the same list object, so other references see the change, but it still builds the reversed copy first. Only list.reverse() and the hand-written loop are truly in place. reversed() copies nothing until you consume it. The Python cheat sheet has the slicing rules. The memory difference, measured:

def peak_bytes(fn):
    tracemalloc.start()
    fn()
    peak = tracemalloc.get_traced_memory()[1]
    tracemalloc.stop()
    return peak

big = list(range(100_000))
in_place = peak_bytes(lambda: reverse_range(big, 0, len(big) - 1))
sliced = peak_bytes(lambda: big[::-1])
print(in_place < 1_000, sliced > 700_000)            # True True

A 100,000-element list costs about 800 KB of pointers to copy; the swap loop allocates almost nothing. The seeded check: 3,000 random arrays and random ranges, including empty ones, compared against slicing, with the swap count checked against half the range length, plus the grouped version against a slice-built answer:

rng = random.Random(39)
ok = True
for _ in range(3000):
    nums = [rng.randint(0, 99) for _ in range(rng.randint(0, 15))]
    i = rng.randint(0, len(nums))
    j = rng.randint(i - 1, len(nums) - 1)            # j = i - 1 is an empty range
    want = nums[:i] + nums[i:j + 1][::-1] + nums[j + 1:]   # brute force: slicing
    work = nums[:]
    swaps = reverse_range(work, i, j)
    ok &= work == want and swaps == max(0, (j - i + 1) // 2)
    k = rng.randint(1, 5)
    blocks = [nums[s:s + k][::-1] for s in range(0, len(nums), k)]
    ok &= reverse_in_groups(nums[:], k) == [x for blk in blocks for x in blk]
print(ok)                                            # True

The complexity

• Time: O(n): n // 2 swaps, each O(1). For a range of length L, L // 2 swaps.
• Extra space: O(1): two indexes. nums[::-1] and a[:] = a[::-1] use O(n).

Same big-O does not mean same speed. In CPython, list.reverse() runs the same swap loop in C (from memory), and it beats the Python loop by a wide constant factor. In an interview, write the loop to show you know it; in production code, call the built-in.

Where it goes wrong

• a = a.reverse(). reverse() returns None, so this throws the list away.
• Looping while left is at most right. Harmless for the middle element, which swaps with itself, but it hides the real stopping rule; looping to the end undoes everything.
• Expecting nums = nums[::-1] inside a function to change the caller's list. It rebinds the local name; the caller still sees the old order. Use nums.reverse() or nums[:] = ....
• Reversing a string in place. Python strings are immutable; convert to a list, reverse, join.
• Off-by-one on ranges. Pass the last index, j, not the slice end j + 1.

When it shows up in interviews

Directly as "reverse an array without extra space" or "reverse a string in place" (with a list of characters), and as a step inside rotate array, reverse words, next permutation, palindrome checks and reversing in groups. Interviewers often follow up with "how many swaps?" and "what about odd lengths?".

How to say it in an interview

"I use two indexes at the ends and swap, then step both inward while left is less than right. Each swap puts two elements in their final place, so it's n / 2 swaps, O(n) time and O(1) extra space; with an odd length the middle stays put. I write it for a range i to j because rotate and reverse-words reuse it. In Python, list.reverse() is the in-place built-in; slicing with [::-1] makes a copy."