In a next-greater-element scan over an array, what do the indices on the stack represent?
answer
- who is still waiting for an answer
- each entry is a pending question
- what ordering does eviction force
- non-increasing from bottom to top
- the current value resolves everyone smaller
basics
~10 sThe stack holds indices of items still waiting for a greater value to their right, kept in decreasing order of value. Each new item answers every stacked index it beats, then is pushed itself.
solid answer
~50 sScanning a leaderboard snapshot left to right, the stack is a list of unanswered questions: every stacked index belongs to a score that has not yet met a strictly higher score further right. Any index whose score was already beaten got popped at that moment, so the scores under the stacked indices are non-increasing from bottom to top — that ordering is a consequence of the eviction rule, not something maintained separately. When the scan reaches score `s`, every stacked index with a smaller score has just found its answer: pop each one and record the current position as its next greater, then push the current index. Indices are stored rather than values because the caller usually wants the position or the distance, and the value is one lookup away. Whatever remains stacked at the end has no next greater element at all.
go deeper
Be ready to say in one sentence what sits on the stack: indices whose next greater value has not been found yet. Then walk a short sequence out loud, naming each push and each pop.
Explain why the non-increasing ordering is forced by the eviction rule rather than maintained separately, and why the pop comparison is strict so that equal values stay waiting.
Show that you can state the meaning of the leftovers precisely and that you pick the scan direction deliberately, because the stack means open questions in one direction and candidate answers in the other.
Own the framing question: which output the consumer actually needs — position, distance, or value — since that decision fixes whether indices or values go on the stack before anyone writes a line.
## The question the algorithm answers Take a leaderboard snapshot: a sequence of records, each with a player and a score. The next-greater-element question asks, for every position, where the first **strictly higher** score appears to its right — and a sentinel (no answer) when none does. The naive answer scans forward from every position, which is quadratic on a long board. A monotonic stack answers all n queries in a single left-to-right pass, and the whole idea lives in what the stack is permitted to contain. ## The stack is a set of open questions Walk the board left to right. At the moment the scan stands on position `i`, some earlier positions have already found their answer — a bigger score appeared after them — and some have not. The algorithm keeps only the unanswered ones. **The stack holds exactly the indices whose next-greater question is still open**, in the order they were encountered. That single rule forces an ordering, for free. Suppose two indices `j < k` are both stacked. If `score[j]` were smaller than `score[k]`, then `k` itself would have answered `j`, and `j` would already have been popped. So every surviving pair satisfies `score[j] >= score[k]` with `j` below `k`: read bottom to top, the scores are non-increasing. That is the monotonic invariant. It is a *consequence* of the eviction discipline, not an extra structure you maintain, which is exactly why the pattern is cheap. ## One step of the scan Arriving at position `i` with score `s`: 1. While the stack is non-empty and the score at the top index is **less than** `s`, pop that index and record `i` as its next greater. 2. Push `i`. Step 1 uses a strict comparison, so an equal score is *not* popped — an equal score is not a greater one, so its question stays open. Step 2 is unconditional: the current index has not been answered by anything yet, so it becomes an open question too. Because the scan pops from the top and the top always carries the smallest of the stacked scores, popping stops the instant it reaches an index whose score is at least `s`. Everything below is at least as large and must also stay. ## Why indices and not values Storing indices costs nothing extra and buys three things: the value is always one lookup away; answers can be reported as positions or as distances (how many places ahead the higher score sits); and duplicates stay distinguishable, which matters as soon as scores repeat. Implementations that stack raw values work for the "give me the value" variant and then have to be rewritten for the "give me the position" variant. ## What is left on the stack at the end The leftovers are not a bug and not a leak. An index survives the whole scan exactly when nothing to its right is strictly greater — under a strict pop condition, that means its score is greater than or equal to every score after it. Those positions are the running record-holders read from the right end, and they are precisely the entries that deserve the sentinel answer. A candidate who says "the stack should be empty at the end" has misread the invariant. ## The right-to-left mirror The same problem can be solved by scanning right to left, and the stack changes meaning: it then holds **candidate answers** rather than open questions. Standing on `i`, pop everything whose score is less than or equal to `score[i]` — such an entry is both smaller and farther away, so it can never be anyone's answer again — and whatever is left on top is `i`'s next greater element, or nothing if the stack empties. Then push `i`. Both directions are one pass and both are linear; the left-to-right form resolves *other* indices as it goes, while the right-to-left form answers the current index immediately. Interviewers accept either, but they expect you to say which role your stack is playing, because the pop condition and the meaning of an empty stack differ between them. ## The wrong mental models to avoid - "The stack holds the answers computed so far." It holds the *questions*; answers go into a separate result array as pops happen. - "The stack holds everything seen so far." Then it would just be the prefix, and nothing would be gained; the eviction is the algorithm. - "Values increase from bottom to top." That is the next-*smaller* variant's invariant. Getting the direction backwards is the single most common slip when the same code is adapted from one variant to the other. - "Leftovers mean the loop ended early." Leftovers are the elements with no answer, and they are the correct output.
- Why keep indices on the stack rather than the values themselves?The value is one lookup away from the index, but the index is not recoverable from a value — especially with duplicate scores. Keeping indices lets you report the answer as a position or a distance (how many places ahead the higher score is), and it makes the circular and span variants work without a second pass. It costs the same memory.
- After the scan finishes, what should the indices still on the stack be assigned?The sentinel meaning "no next greater element". Under a strict pop condition, an index survives exactly when its score is greater than or equal to every score to its right, so no valid answer exists. Initialising the whole result array to the sentinel up front means you never have to drain the stack explicitly.
- Does the invariant still hold if you scan right to left instead?Yes, but the stack changes meaning: it holds candidate answers instead of open questions. You pop every entry less than or equal to the current value — smaller and farther away, so never useful again — and the remaining top is the current index's answer, or none if the stack empties. Both directions are a single linear pass.
Think of a queue of people asking "who ahead of me is taller?" — as soon as someone taller walks by, that person's question is answered and they leave the line, so whoever is still waiting is always in descending order of height.
saying these in an interview costs you the question
- Says the stack stores the answers already computed
- Claims the stack keeps every element seen so far
- States values increase from bottom to top in a next-greater scan
- Treats leftover stack entries as a bug rather than the no-answer cases
- Cannot explain why a popped index never needs to come back