Empty pockets to the tail

A bottling line moves drinks to the capper in a carrier: one long row of pockets, some empty where a bottle was rejected upstream.

The problem

pockets[i] is the fill of the bottle in pocket i, in millilitres. A 0 is an empty pocket, where a reject was pulled out and the gap left behind.

The capper only accepts a carrier whose empty pockets are all at the tail, and it labels from a batch sheet listing the bottles in carrier order, so the filled bottles must keep their relative order exactly. There is one carrier, and the arm lifts a bottle from one pocket into another, so the rearrangement happens inside the row in a constant amount of extra room.

Report the carrier as the capper will see it.

Input. pockets — non-negative integers, millilitres per pocket, 0 for empty.

Output. The same list, rearranged in place: every non-zero fill first in its original order, then every empty pocket.

Example.

pockets = [0, 330, 0, 0, 500, 250, 0, 750]  ->  [330, 500, 250, 750, 0, 0, 0, 0]

Four bottles, four gaps. They arrive at the capper as 330, 500, 250, 750 — the order they already stood in.

A second example, which breaks the tempting shortcut:

pockets = [125, 0, 660, 0, 400]  ->  [125, 660, 400, 0, 0]

Filling each gap with the bottle nearest the tail gives [125, 400, 660, 0, 0]. Every bottle is on the carrier and the empties are at the end, and the batch sheet is now wrong for two of them.

Constraints.

• 0 <= len(pockets) <= 10^5, and an empty carrier stays empty
• 0 <= pockets[i] <= 1000
• Extra space O(1) — there is no second carrier

Hints

Approach

Brute force

Find the first empty pocket with a bottle behind it, slide everything after it one place forward, and repeat. Each slide touches up to n pockets and there can be n slides: about 10¹⁰ moves. Reading the bottles into a fresh row and padding with zeros is one pass, but needs a second carrier.

The insight

Carry an index for where the next bottle belongs, separate from the index you are reading, and the gap between them is exactly the number of empty pockets already passed.

The write index advances only when a bottle is placed, so everything to its left is the bottles seen so far in the order they were seen — stability comes free from reading forward. Everything between write and read is empty, which is what makes the swap safe: sending pockets[read] back to pockets[write] displaces a zero, and that zero lands in a pocket the reader has already passed.

Algorithm

1. Set write = 0.
2. For each read from 0 to n - 1: if pockets[read] is 0, move on.
3. Otherwise swap pockets[write] with pockets[read] and advance write.
4. Return the carrier; the empties were pushed past write on the way.

Complexity

Time O(n) — one look and at most one swap per pocket. Space O(1) — two indices and the bottle in the arm, whatever the carrier length.

Solution

"""Empty pockets to the tail — stable in-place compaction with two indices."""


def solve(pockets):
    write = 0
    for read in range(len(pockets)):
        # invariant: pockets[0:write] holds the bottles seen so far in their
        # original order, and pockets[write:read] is entirely empty — which is
        # why the swap below only ever displaces a zero.
        if pockets[read] != 0:
            pockets[write], pockets[read] = pockets[read], pockets[write]
            write += 1
    return pockets

TESTS = [
    (([0, 330, 0, 0, 500, 250, 0, 750],), [330, 500, 250, 750, 0, 0, 0, 0]),
    (([125, 0, 660, 0, 400],), [125, 660, 400, 0, 0]),
    (([0, 0, 0],), [0, 0, 0]),
    (([200, 200, 0, 0],), [200, 200, 0, 0]),
    (([500],), [500]),
    (([],), []),
    (([0, 0, 750],), [750, 0, 0]),
]

Pitfalls

• Filling gaps from the tail end. Swapping each empty pocket with the last bottle is O(n) and does put every empty at the back, but it reverses the batch order of the bottles it moves: [125, 0, 660, 0, 400] comes out as [125, 400, 660, 0, 0], and the labels go on the wrong drinks.
• Advancing write on every pocket rather than only on a bottle. Then write and read never separate, every swap is a pocket with itself, and the carrier reaches the capper untouched.
• Writing the bottles forward and forgetting to clear the tail. The first example becomes [330, 500, 250, 750, 500, 250, 0, 750] — four ghost bottles the capper tries to cap.

Variants

• The rotunda shift — the same ban on a second row, but every item survives and the whole order changes, so three reversals replace the write index.
• Glasshouse spread — a one-pass scan carrying a pair of values rather than a destination index.