Which minimum-tracking stack design would you standardise on for a memory-capped device fleet, and why?

## The candidates A stack that answers "what is the smallest value currently stored?" in constant time can be built at least three ways. All three keep push, pop and the query at constant time, so **the comparison is not about asymptotic speed at all** — a fact worth saying out loud early, because a candidate who spends the answer comparing time complexities has missed the question. **A. Minimum carried with every entry.** Each stack entry stores `(value, minimum-so-far)`. Push computes the smaller of the new value and the previous top's recorded minimum. Pop does nothing special. Query reads the top's second field. **B. Separate stack of minima.** The main stack holds values; a second stack holds the history of minima, with a record added whenever a value is less than *or equal to* the current minimum, and the top record removed when a matching value is popped. Optionally the records are `(value, count)` pairs so repeated minima collapse into one entry. **C. Encoded differences.** A single field holds the current minimum; the stack stores a transformed value from which both the original value and the previous minimum can be reconstructed by arithmetic. Extra space is `Θ(1)` — one field, regardless of depth. ## Space, stated honestly | Design | Extra space, typical | Extra space, worst case | |---|---|---| | A. Paired values | one word per element | one word per element | | B. Stack of minima | often far less | one entry per element (non-increasing input) | | B'. Counted minima | proportional to distinct minima | one entry per distinct minimum | | C. Encoded differences | one field | one field | The row that decides fleet arguments is B's worst case. "In practice the minima stack stays short" is a statement about typical data, and **a hard memory cap is not sized from typical data** — it is sized from the input that maximises usage, which here is any non-increasing sequence. On a device that must never exhaust memory, an unbounded-in-theory structure needs either the worst-case budget or an enforced bound on depth. If you cannot state the worst case, you have not sized it. ## The hidden cost of the clever option Design C is the one that gets proposed when the cap bites, and it carries three risks that do not appear in a complexity table: 1. **Arithmetic overflow.** The encoding relies on differences of stored values fitting the machine's fixed-width arithmetic. A legitimate input pairing a very large value with a very small minimum can exceed the range, and the failure is silent — a wrong number, not a crash. Accepting this design means auditing the *value domain*, not just the code, and re-auditing whenever the domain widens. 2. **Reviewability.** The correctness argument is an algebraic identity that a reviewer cannot check by reading. In a fleet context, where a defect ships to devices you cannot easily patch, "nobody on the team can spot a sign error in review" is a real operational cost. 3. **Debuggability.** A crash dump from the field shows encoded values that mean nothing without replaying the whole history. Designs A and B dump readable state. ## How I would actually decide **First, bound the depth.** In most real uses of a minimum-tracking stack the depth is capped by something outside the data structure — an undo history that keeps the last `N` steps, a batch size, a protocol window. Bounding depth converts every design's space from "proportional to input" into a fixed number you can compare directly against the cap. This step ends most of these arguments, because at a bounded depth the extra word per element in design A is a small fixed number. **Second, measure against the cap with the worst case.** If design A fits, standardise on A. It has no data-dependent behaviour, no comparison at pop time, no tie handling, and no second structure to keep in sync — the class of bug where a tie at the minimum silently loses a record simply cannot occur. **Third, if A does not fit, try B with counts** before reaching for C. Counted minima usually collapse the space dramatically for real value distributions while remaining ordinary code that a reviewer can follow. **Fourth, if only C fits**, treat it as a deliberate exception rather than a default: write the invariant and the range assumption in the code, add property-based tests over the extreme value range, and add an assertion or a range check at the boundary where values enter. Then record *why* the exception exists, so that the next person who widens the value range knows what they are about to break. ## The standardisation angle The question says *standardise*, and that changes the answer. A single design across a fleet means one implementation to test, one to review, one for on-call to understand at three in the morning, and one to reason about when the cap changes. The value of picking the boring option is not that it is faster — it is not — but that its worst case equals its typical case, so capacity planning is a multiplication rather than a discussion. Reserve the clever encoding for the specific product whose measured ceiling forced it, and do not let it leak into the shared component library, where it becomes everybody's maintenance burden and nobody's measured requirement.