Why does a minimum-tracking stack break when its auxiliary stack records only strictly smaller values?
answer
- think about two identical prices
- how many records for two equal minima
- the comparison at push decides the outcome
- one record cannot cover two occurrences
- strict versus non-strict comparison
basics
~20 sTwo equal minima produce only one auxiliary entry, so removing the first occurrence discards the record while an equally small value is still stored. The structure then reports a minimum that is too large. Record on less-than-or-equal, or store counts.
solid answer
~50 sThe auxiliary stack maintains one invariant: its top is the minimum of everything currently in the main stack. A strict `<` at push time silently violates it whenever a value ties the current minimum, because the tie contributes no auxiliary entry. Now pop that value: it equals the auxiliary top, so the auxiliary entry is discarded too — and the *other* occurrence, still sitting in the main stack, has no record left. The query returns the previous, larger minimum. Picture an undo-able pricing tool where two line items are priced identically at the floor: undo one, and the tool reports a floor that no longer matches its own data. Three fixes work: push on `<=`, store `(value, count)` and decrement, or carry the running minimum alongside every entry so no comparison is needed at pop time.
code
pseudocode · 13 linespush(x):
push(main, x)
if isEmpty(aux) or x < top(aux):
push(aux, x)
pop():
x = pop(main)
if x == top(aux):
pop(aux)
return x
minimum():
return top(aux)go deeper
Recall that a stack reporting its smallest value needs a history, not one variable, because a removal can take the current minimum and the previous one has to come back.
State the invariant the auxiliary structure maintains and trace equal minima through a push and a pop to show why a strict comparison at push time loses one of them.
Show you would deliberately test ties, equal-to-minimum removals and popping to empty, and name the fix options: a non-strict comparison, stored counts, or a minimum carried with every entry.
Own the correctness argument as a written invariant the team reviews against, and decide whether a subtle two-structure design earns its maintenance cost over an obvious one.
## The structure and its invariant A minimum-tracking stack supports the usual push and pop plus a constant-time query for the smallest value currently stored. The classic construction pairs the main stack with an **auxiliary stack of minima**, and its correctness rests on one invariant: > The top of the auxiliary stack equals the minimum of all values currently in the main stack. Everything else follows. The query reads the auxiliary top. Push must restore the invariant when the new value changes the minimum. Pop must restore it when the removed value *was* the minimum. ## The bug The natural first implementation pushes onto the auxiliary stack only when the new value is **strictly** smaller than the current minimum, and pops the auxiliary stack when the removed value equals its top. Trace it on a tie. Push `4`: auxiliary is empty, so record it. Auxiliary: `[4]`. Push `2`: `2 < 4`, so record it. Auxiliary: `[4, 2]`. Push `2` again: `2 < 2` is false, so record nothing. Auxiliary: still `[4, 2]`. Pop: the removed value is `2`, which equals the auxiliary top, so discard that entry. Auxiliary: `[4]`. The main stack still holds `4` and a `2`. The query now answers `4`. It is wrong, and it is wrong *silently* — no exception, no crash, just a plausible number. ## Why this is the interesting failure Ties are not exotic. In a money or pricing domain they are the normal case: an undo-able pricing tool where each stack entry is a candidate price, several line items priced at exactly the promotional floor, an undo that removes one of them. The tool now quotes a floor higher than a price it is still holding. The bug survives every test written with distinct values, which is precisely the test suite a hurried author writes, and it also survives a strictly decreasing test sequence — the case where the auxiliary stack is at its most exercised. It reproduces only when equal values meet the current minimum and one of them is removed. The second-order lesson is about *where* the check goes. The push side and the pop side must agree on the comparison. A strict comparison at push and an equality comparison at pop are individually reasonable and jointly wrong; the invariant is a property of the pair, not of either line. ## Three correct designs **1. Non-strict push.** Record on `<=` rather than `<`. Every value that ties the minimum gets its own auxiliary entry, so removing one occurrence removes exactly one record and the remaining occurrence is still covered. Smallest change, easiest to review, and worst-case auxiliary space is one entry per stored element (a strictly non-increasing input records everything). **2. Counted entries.** Store `(value, count)` on the auxiliary stack. A push that ties the top increments its count; a pop that matches decrements it and discards the entry only at zero. Extra space becomes proportional to the number of *distinct* minima rather than to their multiplicity, which is a large win when the minimum repeats thousands of times. The cost is more moving parts and two places to get the arithmetic wrong. **3. Minimum carried with every entry.** Store `(value, minimum-so-far)` in a single stack: on push, the recorded minimum is the smaller of the new value and the previous top's recorded minimum; on pop, nothing special happens at all. There is no comparison at pop time, no second structure, and no tie case to reason about — ties simply carry the same minimum forward. It is the design that makes the whole bug class impossible, at the price of a constant amount of extra memory per element regardless of the data. ## Why a single variable cannot work The tempting simplification is one field holding the current minimum, updated on push. It handles push fine and collapses on pop: once the minimum is removed, the previous minimum has to come back, and a single field never stored it. The structure needs *history* of minima, not a running value — and that is the reason a stack, rather than a variable, is the right shape. The same argument explains why this technique adapts to a maximum, or to both simultaneously, by keeping the corresponding history; it does not adapt to a median or an average, because those are not recoverable from a stack of past extremes. ## What to test Deliberate cases: equal values at the minimum, a value equal to the minimum pushed and popped repeatedly, popping down to empty and querying, a strictly decreasing sequence, a strictly increasing one, and a query on an empty structure. Those six catch every variant of this bug.
- How would you keep the auxiliary stack small when the minimum repeats thousands of times?Store (value, count) instead of bare values: a push that ties the top increments the count, a matching pop decrements it, and the entry is discarded only when the count reaches zero. Extra space then scales with the number of distinct minima rather than their multiplicity, at the cost of two arithmetic paths that both need tests.
- Does the same technique extend to tracking a maximum, or both at once?Yes, symmetrically — invert the comparison for a maximum, and keep two histories, or one entry holding both extremes, to track both. What does not extend is a median or an average: those cannot be recovered from a history of past extremes, so removing an element leaves no way to restore the previous answer in constant time.
- Which test cases would have caught this bug before it shipped?Anything with ties at the minimum: push two equal smallest values and pop one, then query. Also worth having are pop-to-empty followed by a query, a strictly decreasing sequence, and a strictly increasing one. Test suites built from distinct values pass happily while the defect is present, which is why the bug reaches production.
Two customers hold vouchers for the same lowest price, but only one voucher was written into the ledger. When one customer leaves, the clerk crosses out the entry — and the discount the other customer is still entitled to has vanished from the books.
saying these in an interview costs you the question
- Assumes duplicate values will not occur in real data
- Keeps a single minimum variable and calls it finished
- Discards the auxiliary top without comparing to the removed value
- Claims the defect appears only with negative values
- Cannot state the invariant the auxiliary stack maintains