Practice: Closing the Gaps in a Row of Parked Cars

Empty spaces in a row move to the end while the cars keep their order; then say what the same pass needs to drop repeated plates.

Moving every unwanted value to the end of an array while the rest keep their order takes a read pointer and a write pointer, in place. A row of eight parking spaces holds 0 4 0 0 7 2 0 5, where 0 is an empty space and every other number is a car. Move the cars to the front, in the order they were parked, and the empty spaces to the end, without a second array. Then a second task: the same row of plates must drop repeated plate numbers in one pass, keeping the first of each. Say what the input must look like for one pass to be enough.

Show the row and a solution

The row becomes 4 7 2 5 0 0 0 0. The read pointer visits every space and the write pointer marks the next free space at the front. Each car is copied to the write pointer's space, which keeps the cars in order, and once the read pointer has finished, every space from the write pointer to the end is set to 0.

Read and write pointers on 0 4 0 0 7 2 0 5

Inputrow 0 4 0 0 7 2 0 5, where 0 is an empty space

Read 0
1. 0readwrite
2. 4
3. 0
4. 0
5. 7
6. 2
7. 0
8. 5
empty space skipped, write stays at 0
Read 1
1. 4
2. 4readwrite
3. 0
4. 0
5. 7
6. 2
7. 0
8. 5
car 4 moved up to space 0, write moves to 1
Read 2
1. 4
2. 4write
3. 0read
4. 0
5. 7
6. 2
7. 0
8. 5
empty space skipped, write stays at 1
Read 3
1. 4
2. 4write
3. 0
4. 0read
5. 7
6. 2
7. 0
8. 5
empty space skipped, write stays at 1
Read 4
1. 4
2. 7
3. 0write
4. 0
5. 7read
6. 2
7. 0
8. 5
car 7 moved up to space 1, write moves to 2
Read 5
1. 4
2. 7
3. 2
4. 0write
5. 7
6. 2read
7. 0
8. 5
car 2 moved up to space 2, write moves to 3
Read 6
1. 4
2. 7
3. 2
4. 0write
5. 7
6. 2
7. 0read
8. 5
empty space skipped, write stays at 3
Read 7
1. 4
2. 7
3. 2
4. 5
5. 7write
6. 2
7. 0
8. 5read
car 5 moved up to space 3, write moves to 4
Fill
1. 4
2. 7
3. 2
4. 5
5. 0write
6. 0
7. 0
8. 0
spaces 4 to 7 set to empty

ResultThe row is 4 7 2 5 0 0 0 0.

Dropping repeated plates in one pass needs every repeat to sit next to the plate it repeats, which sorted input guarantees. The read pointer then compares each plate with the last one written and keeps it only if it differs. On unsorted plates the comparison misses a repeat that is not next to its first copy.

closing_gaps.pypy

def close_gaps(row: list[int]) -> list[int]:
    write = 0
    for read in range(len(row)):
        if row[read] != 0:
            row[write] = row[read]
            write += 1
    for i in range(write, len(row)):
        row[i] = 0
    return row


def drop_repeats(plates: list[int]) -> int:
    write = 0
    for read in range(len(plates)):
        if write == 0 or plates[read] != plates[write - 1]:
            plates[write] = plates[read]
            write += 1
    return write


print("gaps closed:", *close_gaps([0, 4, 0, 0, 7, 2, 0, 5]))
sorted_plates = [101, 101, 205, 205, 205, 310]
print("sorted plates:", *sorted_plates[:drop_repeats(sorted_plates)])
unsorted_plates = [101, 205, 101]
print("unsorted plates:", *unsorted_plates[:drop_repeats(unsorted_plates)])

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

gaps closed: 4 7 2 5 0 0 0 0
sorted plates: 101 205 310
unsorted plates: 101 205 101

Both passes are O(n) time and O(1) extra space for n spaces. The unsorted plates keep 101 twice, because the second 101 is compared with 205, not with the first 101.

Two Pointer

← → move through sections and cards