In a next-smaller-element stack scan over a price list with ties, which pop comparison do you use?

## Two independent decisions, often conflated Adapting the next-greater scan to a procurement price list, where each entry is a supplier quote and you want the nearest cheaper quote further down the list, involves two decisions that people tend to merge into one: 1. **Direction.** Next greater or next smaller. This flips only the comparison operator in the pop test, from "top is less than current" to "top is greater than current". Consequently the invariant flips too: the stacked values become non-decreasing from bottom to top instead of non-increasing. Nothing else changes — same pushes, same result array, same bound. 2. **Tie handling.** Whether an *equal* value counts as an answer. This is the choice between a strict (`>`) and a weak (`>=`) pop test, and it is a specification question, not an implementation detail. A candidate who flips direction confidently but never mentions ties has answered half the question. ## What each tie rule actually produces Take quotes 40, 30, 30, 30, 20 and ask each index for its next cheaper quote to the right. **Strict, `pop while price[top] > current`.** Arriving at the second 30, the top holds 30; `30 > 30` is false, so nothing pops and the new index is pushed on top. The run accumulates. When 20 arrives, all three 30s and then the 40 pop, and every one of them is answered with the position of the 20. Semantics: *next strictly cheaper*. The stack is non-decreasing bottom to top, with ties allowed to sit side by side. **Weak, `pop while price[top] >= current`.** Arriving at the second 30 pops the first 30 and answers it with the second's position. Each member of the run answers to its immediate equal successor; only the last 30 in the run waits for the 20. Semantics: *next cheaper or equal*. The stack is strictly increasing bottom to top, since equals never coexist. Both results are internally consistent. Which is *correct* depends on whether "a supplier at the same price" satisfies the business question — for "find me a cheaper option" it does not; for "find me the next quote that is not more expensive" it does. ## Why this bug is expensive in production Three properties make it nasty. First, it is invisible on distinct data: any price list with no repeats produces identical output under both rules, so a test fixture with unique prices passes either way. Second, it does not degrade performance — the push-once, pop-at-most-once accounting holds under both comparisons, so the scan stays linear and no timeout fires. Third, the wrong answer is *plausible*: it points at a real supplier at a real position, just the wrong one, and it is wrong only on the rows where prices repeat, which in real catalogues is exactly the crowded, competitive part of the data. The failure surfaces as a slow-burning data-quality complaint, not a crash. The defence is a test fixture with deliberate duplicate runs — several equal prices in a row, a run at the start, a run at the very end — and an assertion on which occurrence each member points to. That fixture is what separates candidates who have shipped this from candidates who have solved it on a whiteboard. ## The four variants, stated once With a left-to-right scan and the stack holding open questions: | Wanted | Pop while | Stack, bottom to top | | --- | --- | --- | | next strictly greater | `top < current` | non-increasing | | next greater or equal | `top <= current` | strictly decreasing | | next strictly smaller | `top > current` | non-decreasing | | next smaller or equal | `top >= current` | strictly increasing | One operator selects the row. Memorising the table is less useful than deriving it: ask "should an equal value close this question?" — if yes, include equality in the pop test; if no, exclude it and let equals accumulate. ## Edge cases worth naming A run of equal prices at the *end* of the list survives to the end under either rule, minus whichever members the weak rule answered internally. An all-equal list produces no answers at all under the strict rule and answers everything except the last element under the weak rule — a good sanity check to state out loud, because it separates the two rules maximally. And if the consumer wants *distance* to the next cheaper quote rather than its position, the tie rule changes those distances dramatically inside a run: all-the-way-to-the-end under strict, one step under weak. ## What to say when asked "Direction is one operator: pop while the stacked price is greater than the current one. Ties are a separate decision — strict comparison means equal prices never answer each other and a whole run resolves to the same later cheaper quote; non-strict means each answers its immediate equal neighbour. Both are linear, so the only symptom of picking wrong is quietly wrong data on duplicate-heavy input, which is why I would pin it with a duplicates fixture."