Lightest bag in the tower

A hostel porter stacks guest bags in a narrow alcove: bags go on top and come off the top. The desk still wants the lightest weight in the alcove instantly.

The problem

Build the porter's log. Bags arrive and leave in strict last-in-first-out order, and four instructions come in one at a time:

• ("drop", weight) — a bag of that weight goes on top of the tower.
• ("collect",) — the top bag leaves; report its weight.
• ("peek",) — report the weight of the top bag, which stays put.
• ("lightest",) — report the smallest weight anywhere in the tower.

Every instruction has to be answered in constant time; the queue at the desk will not wait for someone to lift the tower and weigh it again.

Input. ops — a list of instruction tuples in the shapes above.

Output. A list of the answers, in order, one for each collect, peek and lightest. A drop answers nothing.

Example.

[("drop", 14), ("drop", 9), ("drop", 22), ("lightest",),
 ("collect",), ("peek",), ("lightest",), ("collect",), ("lightest",)]
  ->  [9, 22, 9, 9, 9, 14]

The 9 stays the lightest while it is buried. Collecting the 22 exposes the 9, and only when the 9 itself leaves does the answer rise to 14.

A second example, with the lightest weight stored twice:

[("drop", 8), ("drop", 3), ("drop", 3), ("lightest",),
 ("collect",), ("lightest",), ("collect",), ("lightest",)]
  ->  [3, 3, 3, 3, 8]

Collecting one 3 must leave the answer at 3, because the other 3 is still there.

Constraints.

• 1 <= len(ops) <= 10^5
• 1 <= weight <= 10^4
• collect, peek and lightest are only ever sent to a non-empty tower.

Hints

Approach

Brute force

Store the weights in a list and scan it on every lightest. Drops and collections are O(1), but a run of 10⁵ queries over a tower of 10⁵ bags is 10¹⁰ comparisons.

The insight

A bag can record the lightest weight at or below itself the moment it lands, and that number is still correct whenever the bag is on top.

Last-in-first-out is what makes this legal: everything beneath a bag is frozen for that bag's whole stay, because a collection can only remove something above it. So the record can never go stale — the only bag that changes is the one on top, and when it leaves, the record of the bag now exposed answers the question.

Algorithm

1. Keep one list of pairs: the bag's own weight, and the smallest weight at or below it.
2. On drop, compute that second field as the new weight, or the smaller of the new weight and the current top's second field when the tower is not empty.
3. On collect, pop the pair and report its first field.
4. On peek, report the top pair's first field.
5. On lightest, report the top pair's second field.

Complexity

Time O(1) per instruction, so O(n) overall. Space O(n) — one extra integer per bag in the tower.

Solution

"""Lightest bag in the tower — a stack that carries its own running minimum."""


def solve(ops):
    # Each entry is (weight of this bag, lightest weight in the tower up to here).
    # The second field is the whole trick: it is decided once, when the bag lands,
    # and it is still correct after any number of collections above it.
    tower = []
    answers = []

    for op in ops:
        move = op[0]
        if move == "drop":
            weight = op[1]
            lightest = weight if not tower else min(weight, tower[-1][1])
            tower.append((weight, lightest))
        elif move == "collect":
            answers.append(tower.pop()[0])
        elif move == "peek":
            answers.append(tower[-1][0])
        else:                      # "lightest"
            answers.append(tower[-1][1])

    return answers

TESTS = [
    (
        (
            [
                ("drop", 14), ("drop", 9), ("drop", 22),
                ("lightest",), ("collect",), ("peek",), ("lightest",),
                ("collect",), ("lightest",),
            ],
        ),
        [9, 22, 9, 9, 9, 14],
    ),
    # Duplicate lightest bags: collecting one must not lose the other.
    (
        (
            [
                ("drop", 8), ("drop", 3), ("drop", 3), ("lightest",),
                ("collect",), ("lightest",), ("collect",), ("lightest",),
            ],
        ),
        [3, 3, 3, 3, 8],
    ),
    (
        ([("drop", 5), ("drop", 5), ("lightest",), ("collect",), ("lightest",)],),
        [5, 5, 5],
    ),
    # A tower that empties and refills.
    (
        ([("drop", 30), ("lightest",), ("peek",), ("collect",), ("drop", 12), ("lightest",)],),
        [30, 30, 30, 12],
    ),
    # The lightest bag is at the bottom, so it survives every collection.
    (
        ([("drop", 1), ("drop", 100), ("drop", 50), ("lightest",), ("collect",), ("lightest",)],),
        [1, 50, 1],
    ),
]

Pitfalls

• Tracking one lightest variable. It handles drops fine and breaks on collections: once the lightest bag leaves, nothing remembers the runner-up and the answer stays too low forever.
• Pushing onto a side stack only when a weight is strictly smaller. The second example then has one 3 recorded for two 3s in the tower, and the first collection leaves the porter reporting 8 while a 3 is still on the shelf.
• Reading the current top before the tower has anything in it. The first drop has no pair beneath it, so its record is its own weight.

Variants

• The front display — another O(1) structure built from a second view of the same items, ordered by recency instead of by a running minimum.