Push the empty parking slots to the end

Two pointers Junior Python 3.13+ Kotlin 2.4+ Reviewed By Best Latest Apps

Spot the bug

This version scrambles the order of the cars. Which line is wrong?

  1. def compact(a: list[int]) -> list[int]:
  2. lo, hi = 0, len(a) - 1
  3. while lo < hi:
  4. if a[lo] == 0:
  5. a[lo], a[hi] = a[hi], a[lo]
  6. hi -= 1
  7. else:
  8. lo += 1
  9. return a
  10. print(compact([0, 1, 2]))

Choose an answer, then open Show answer below to check it.

Show answer
  • Answer: line 5 a[lo], a[hi] = a[hi], a[lo]

Line 5 swaps an empty slot with whatever is at the far end, so cars from the back jump ahead of earlier cars. A read/write pointer pair moving in the same direction keeps order.

A write pointer trails a read pointer over [0, 1, 0, 3, 12]; cars move forward and empties collect at the end.

Steps come from running the Python solution.

Text version

Mixed row:

Cells: [0, 1, 0, 3, 12]

  1. Write 0, read 0: [0, 1, 0, 3, 12]. Zero: skip
  2. Write 0, read 1: [1, 0, 0, 3, 12]. Keep 1: write it at 0
  3. Write 1, read 2: [1, 0, 0, 3, 12]. Zero: skip
  4. Write 1, read 3: [1, 3, 0, 0, 12]. Keep 3: write it at 1
  5. Write 2, read 4: [1, 3, 12, 0, 0]. Keep 12: write it at 2

Result: [1, 3, 12, 0, 0]

Already packed:

Cells: [5, 6, 0]

  1. Write 0, read 0: [5, 6, 0]. Keep 5: write it at 0
  2. Write 1, read 1: [5, 6, 0]. Keep 6: write it at 1
  3. Write 2, read 2: [5, 6, 0]. Zero: skip

Result: [5, 6, 0]

30-second answer

Keep a write pointer for where the next car goes. Scan with a read pointer; each car swaps into the write position and the write pointer advances. Cars keep their order because they are written in the order they are read. One pass, O(n) time, O(1) extra space.

Practise saying it · 45 s. No recording, just a timer

Explain the read and write pointer technique.

Say your answer out loud, then check which of these points you covered:

  • Write pointer marks next kept slot
  • Order kept
  • O(n) time, O(1) space

Deep dive

Invariant: everything before write is a car, in original order; everything between write and read is empty.

Swapping (instead of overwriting and filling zeros later) keeps it a single pass and works for any 'kept vs dropped' rule.

Building a new list is simpler but uses O(n) extra memory and does not modify the caller's list.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
def empties_to_end(slots: list[int]) -> list[int]:
    write = 0
    for read in range(len(slots)):
        if slots[read] != 0:
            slots[write], slots[read] = slots[read], slots[write]
            write += 1
    return slots

Kotlin Ran on Kotlin 2.4.21 · JDK 21.0.12.1
Kotlin 2.4
fun emptiesToEnd(slots: List<Int>): List<Int> {
    val a = slots.toMutableList()
    var write = 0
    for (read in a.indices) {
        if (a[read] != 0) {
            val t = a[write]; a[write] = a[read]; a[read] = t
            write++
        }
    }
    return a
}

Common mistakes

  • Removing zeros with list.remove in a loop, which is O(n²).
  • Swapping when the slot is empty instead of when it holds a car.

Senior take & follow-ups

State the invariant out loud. It makes the code self-evident and shows you can reason about in-place edits.

Follow-up questions

Think of your answer first, then open the hint.

  1. How would you minimise writes?

    Show hint

    Copy cars forward, then fill the tail with zeros once; that skips swaps of a car with itself.

  2. What if order did not matter?

    Show hint

    Pointers from both ends: swap an empty slot on the left with a car on the right.

What each operation costs: Arrays · Array Operations

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.