In-place techniques: reverse, rotate, partition

An in-place technique rearranges an array inside the array itself, using only a few index variables: O(1) extra memory, no second array. Three building blocks cover most of what you need. Two indices moving towards each other reverse an array in n/2 swaps. Three reversals rotate it: to move every item k places to the right, reverse the whole array, then the first k items, then the rest. Read and write indices filter it: the read index visits every item, the write index marks where the next kept item goes, so removing duplicates, dropping a value or moving items below a pivot to the front all take one pass. Each runs in O(n) time. The price of working in place is that the input is gone once the work is done, and that some methods, partitioning in particular, do not keep the order of equal items.

Reversing with two indices

Put one index at each end, swap the two items, and move both inwards until they meet. Every swap fixes two positions for good, so an array of n items needs ⌊n/2⌋ swaps and two index variables, whatever n is. Python’s list.reverse() works this way; items[::-1] instead builds a second list of n references, which is why it is not in place.

Rotating by three reversals

Rotating right by k moves every item k places to the right and wraps the last k round to the front. Rotating by n changes nothing, so first reduce k to k mod n: rotating 7 items by 10 is the same as rotating them by 3. Then:

1. Reverse the whole array: the last k items arrive at the front, but backwards.
2. Reverse the first k items, which puts them in order.
3. Reverse the remaining n − k items, which puts them in order too.

The program below traces both rotations of [1..7], by 3 and by 10, with the same three steps:

"""Four in-place techniques on Python lists: each uses a few index variables and never builds a second list."""


def reverse(a, lo=0, hi=None):
    """Reverses a[lo:hi] in place with two indices that move towards each other."""
    i, j = lo, (len(a) if hi is None else hi) - 1
    while i < j:
        a[i], a[j] = a[j], a[i]
        i += 1
        j -= 1


def rotate_right(a, k):
    """Moves every item k places to the right, wrapping around: three reversals."""
    n = len(a)
    if n == 0:
        return
    k %= n  # rotating by n changes nothing, so only k mod n counts
    reverse(a)
    reverse(a, 0, k)
    reverse(a, k, n)


def remove_duplicates(a):
    """Keeps the first copy of each value of a sorted list, in order; returns how many items are kept."""
    write = 0
    for read in range(len(a)):
        # Invariant: a[0:write] holds the distinct values of a[0:read], in order.
        if write == 0 or a[read] != a[write - 1]:
            a[write] = a[read]
            write += 1
    return write


def partition(a, pivot):
    """Moves every item below pivot to the front; returns where the rest begins. The order is not kept."""
    write = 0
    for read in range(len(a)):
        if a[read] < pivot:
            a[write], a[read] = a[read], a[write]
            write += 1
    return write


for k in (3, 10):
    a = list(range(1, 8))
    m = k % len(a)
    print(f"rotate [1..7] right by {k} (k mod 7 = {m}):")
    reverse(a)
    print("  reverse all          ", a)
    reverse(a, 0, m)
    print(f"  reverse the first {m}  ", a)
    reverse(a, m, 7)
    print(f"  reverse the last {7 - m}   ", a)
    b = list(range(1, 8))
    rotate_right(b, k)
    assert a == b

marks = [40, 40, 55, 55, 55, 61, 78, 78, 90]
kept = remove_duplicates(marks)
print(f"remove_duplicates kept {kept}: {marks[:kept]}  (the rest of the list: {marks[kept:]})")

scores = [72, 35, 90, 18, 64, 41, 77, 29]
start = partition(scores, 50)
print(f"partition around 50: below {scores[:start]}, the rest {scores[start:]}")

rotate [1..7] right by 3 (k mod 7 = 3):
  reverse all           [7, 6, 5, 4, 3, 2, 1]
  reverse the first 3   [5, 6, 7, 4, 3, 2, 1]
  reverse the last 4    [5, 6, 7, 1, 2, 3, 4]
rotate [1..7] right by 10 (k mod 7 = 3):
  reverse all           [7, 6, 5, 4, 3, 2, 1]
  reverse the first 3   [5, 6, 7, 4, 3, 2, 1]
  reverse the last 4    [5, 6, 7, 1, 2, 3, 4]
remove_duplicates kept 5: [40, 55, 61, 78, 90]  (the rest of the list: [61, 78, 78, 90])
partition around 50: below [35, 18, 41, 29], the rest [64, 90, 77, 72]

Each step reverses part of the array in place, so the rotation needs no extra memory and about n swaps in all. Copying into a new array would take one write per item but n extra slots. A third way, the juggling or cycle method, moves every item straight to its final place, one cycle of positions at a time.

Keeping what you need: read and write indices

The read index looks at every item once; the write index marks where the next item worth keeping goes. Whatever is kept is copied to the write position, and the write index moves on. For remove_duplicates on a sorted list an item is kept when it differs from the last kept one, and the method rests on one invariant: a[0:write] holds the distinct values of a[0:read], in order.

In the run, the nine marks keep their five distinct values at the front, and the slots behind the write index still hold leftovers, which the caller ignores or removes. The same two indices remove every copy of one value, move the zeros to the end, or keep only the items that pass any test, always in one pass and always in order. When the order does not matter, a removed item’s slot can instead be filled with the last item.

Partitioning around a pivot

Partitioning moves the items below a pivot to the front: when the read index finds a small item, it swaps it with the item at the write index. In the run, 35, 18, 41 and 29 arrive at the front in their original order, while 72, 90, 64 and 77 are shuffled to 64, 90, 77 and 72. That is the general rule: an in-place partition is not stable, so equal items, or items on the same side, may not keep their order. A three-way partition, also called the Dutch national flag method, splits an array into items below, equal to and above a pivot in one pass with three indices. Quicksort is built on partitioning, and the three-way version keeps it fast on inputs with many equal keys.

Exercise

Move every 0 to the end of a list in place, keeping the order of the other numbers: one read index, one write index.

def move_zeros(counts):
    """Moves every 0 in counts to the end, in place, keeping the order of the other numbers."""
    # Replace this line with your code.
    raise NotImplementedError("write move_zeros")

import tracemalloc

from move_zeros import move_zeros


def moved(values):
    counts = list(values)
    assert move_zeros(counts) is None
    return counts


def test_example():
    """[0, 3, 0, 1, 4] becomes [3, 1, 4, 0, 0]"""
    assert moved([0, 3, 0, 1, 4]) == [3, 1, 4, 0, 0]


def test_order_kept():
    """the other numbers keep their order, repeated values included"""
    assert moved([5, 0, 5, 2, 0, 0, 2, 9]) == [5, 5, 2, 2, 9, 0, 0, 0]


def test_edge_cases():
    """an empty list, no zeros and only zeros all work"""
    assert moved([]) == []
    assert moved([1, 2, 3]) == [1, 2, 3]
    assert moved([0, 0, 0]) == [0, 0, 0]
    assert moved([0]) == [0]


def test_same_list_changed():
    """the function changes the list it was given"""
    counts = [0, 1]
    alias = counts
    move_zeros(counts)
    assert alias == [1, 0] and alias is counts


def test_no_second_list():
    """on 100,000 numbers the extra memory peak stays under 20,000 bytes"""
    counts = [k % 7 for k in range(100_000)]
    expected = [k % 7 for k in range(100_000) if k % 7] + [0] * (100_000 // 7 + 1)
    tracemalloc.start()
    try:
        move_zeros(counts)
        peak = tracemalloc.get_traced_memory()[1]
    finally:
        tracemalloc.stop()
    assert counts == expected
    assert peak < 20_000, f"peak extra memory was {peak:,} bytes"

/** Moves every 0 in counts to the end, in place, keeping the order of the other numbers. */
export function moveZeros(counts) {
  // Replace this line with your code.
  throw new Error('write moveZeros');
}

import { test, assert } from 'mysmartcopilot:test';
import { moveZeros } from './move_zeros.mjs';

function moved(values) {
  const counts = [...values];
  assert.equal(moveZeros(counts), undefined);
  return counts;
}

test('[0, 3, 0, 1, 4] becomes [3, 1, 4, 0, 0]', () => assert.deepEqual(moved([0, 3, 0, 1, 4]), [3, 1, 4, 0, 0]));

test('the other numbers keep their order, repeated values included', () =>
  assert.deepEqual(moved([5, 0, 5, 2, 0, 0, 2, 9]), [5, 5, 2, 2, 9, 0, 0, 0]));

test('an empty list, no zeros and only zeros all work', () => {
  assert.deepEqual(moved([]), []);
  assert.deepEqual(moved([1, 2, 3]), [1, 2, 3]);
  assert.deepEqual(moved([0, 0, 0]), [0, 0, 0]);
  assert.deepEqual(moved([0]), [0]);
});

test('the function changes the array it was given', () => {
  const counts = [0, 1];
  const alias = counts;
  moveZeros(counts);
  assert.ok(alias === counts);
  assert.deepEqual(alias, [1, 0]);
});

test('100,000 numbers come out right', () => {
  const counts = Array.from({ length: 100000 }, (_, k) => k % 7);
  const kept = counts.filter((x) => x !== 0);
  moveZeros(counts);
  assert.equal(counts.length, 100000);
  assert.deepEqual(counts.slice(0, kept.length), kept);
  assert.ok(counts.slice(kept.length).every((x) => x === 0));
});

Why each technique is correct: invariants, proofs and three bands Pro: opens with a Pro, Premium or Ultimate pass

Rotate and filter in five languages, and the modulo trap Pro: opens with a Pro, Premium or Ultimate pass

Variants with numbers: writes, cache behaviour and memory Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

Key takeaways

• In place means O(1) extra memory: a few indices, no second array.
• Reverse with two indices moving inwards; rotate right by k with three reversals, after reducing k modulo n.
• Read and write indices filter in one pass and keep order: a[0:write] is always the answer so far.
• An in-place partition is not stable; a three-way partition splits items into below, equal and above in one pass.