In a daily-score series, why does a monotonic stack give each day's weaker-prior-day streak as an index gap rather than a pop count?
answer
- Ask what a pop actually erases
- A popped day never answers again
- One entry may stand for many days
- Whoever survives on top is the last stronger day
- Subtract indices instead of counting pops
basics
~20 sEach popped day already absorbed the days it dominated, so counting pops undercounts. The streak is today's index minus the index still sitting on top of the stack, which spans every absorbed day in one subtraction.
solid answer
~50 sKeep a stack of day indices whose scores strictly decrease. For day `i` you pop every index whose score is at most today's; a popped day is dominated by today and can never answer for any later day. The streak — how many consecutive days ending at `i` have a score not exceeding today's — is then `i - top(stack)`, using `-1` when the stack empties, because the index left on top is the most recent day that actually beat today and everything strictly between it and `i` is weaker by construction. Counting this iteration's pops gives the wrong number: a day popped now may itself have swallowed a long run earlier, and days popped on previous iterations are already gone. The subtraction recovers all of them at once, which is precisely why the pattern stores indices rather than scores.
go deeper
Be ready to say what the stack holds — day indices, kept in decreasing score order — and to compute one day's run as today's index minus the index left on top, with the empty-stack case reaching the start of the series.
Explain why a popped day is gone for good: today dominates it for every future day, so its whole absorbed run must be folded into the index gap at the moment it leaves. Justify the gap rather than asserting it.
Show you can restate the metric under a changed specification — ties folded in or excluded, today counted or not, days arriving one at a time — without rederiving the pattern from scratch each time.
Own the call on whether this needs the stack at all. On short series recomputed on a nightly batch, a plain backward scan is simpler to review and fast enough; reserve the invariant-carrying version for hot paths where the quadratic scan actually shows up.
## The metric Take a series of daily performance scores. For each day you want a pressure reading: **how many consecutive days, ending with today, have a score that does not exceed today's**. A day that beats every recent day gets a long run; a day in the shadow of a strong recent day gets a run of one (itself). The naive computation walks backwards from each day until it meets a stronger day. That is quadratic on a series that trends upward, because each day walks nearly the whole prefix. ## What the stack actually holds The pattern keeps a stack of **indices**, maintained so their scores strictly decrease from bottom to top. Processing day `i`: 1. While the stack is non-empty and `score[top(stack)] <= score[i]`, pop. 2. Let `p = top(stack)` after the popping, or `-1` if the stack is now empty. 3. `streak[i] = i - p`. 4. Push `i`. Step 3 is the whole idea, and it deserves a proof rather than a shrug. ## Why the gap is exactly right After step 1, `p` is the **most recent index with a score strictly greater than today's**. Claim: every index `j` with `p < j < i` has `score[j] <= score[i]`. Suppose some such `j` had a bigger score. Either `j` is still on the stack — impossible, because then `j` would be above `p` and would have survived step 1 only by being greater than today's score, contradicting that `p` is the top; or `j` was popped earlier by some day `k` with `j < k <= i` and `score[j] <= score[k]`. Chaining that relation forwards, `score[j] <= score[k] <= ... <= score[i]`. Either way `j` is not stronger than today. So days `p+1 .. i` are exactly the run, and its length is `i - p`. When no earlier day beat today, `p = -1` and the run is `i + 1` days: the whole prefix. ## Why a pop count is the classic wrong answer The intuition "today popped three entries, so three days are in my run" fails for two independent reasons. - **Absorption.** Each entry on the stack is a *representative* of the run it already swallowed, not a single day. Popping one entry may retire a run of forty days. The count of pops is the number of representatives retired, never the number of days covered. - **Prior removal.** Days that were popped on earlier iterations are not on the stack at all, so they cannot be counted today — yet they are inside today's run whenever they were weaker than the day that evicted them, which is exactly why they were evicted. Some presentations of the pattern do carry an explicit run length alongside each stacked entry and add them up on pop. That is arithmetically equivalent and it is where the intuition comes from, but it stores a redundant number: with indices on the stack, one subtraction reproduces the same total for free. Storing indices also keeps every other question about the same scan (distance, boundary, width) answerable from the same stack, which is why index-stacks are the idiom. ## The tie rule is a decision, not a detail Whether you pop on `<=` or on `<` changes the metric, not the mechanics. Popping on `<=` folds days with an equal score into today's run — "not exceeding today". Popping on `<` leaves an equal-scoring day on the stack, so it becomes the boundary and today's run stops at it — "strictly weaker than today". Pick the rule from the definition you were handed, and say out loud which one you picked; interviewers listen for that sentence. ## Streaming and off-by-one The scan is naturally online: day `i` needs only the stack, not the future, so the metric can be emitted as each day arrives. The two boundary cases worth stating explicitly are the empty stack (`p = -1`, run reaches the start of the series) and the definition of whether today counts itself. With the formula `i - p` today is included, so the minimum answer is 1 — never 0. If your specification excludes today, the answer is `i - p - 1` and the minimum is 0. Interviewers deliberately ask which one your code returns for the first day of the series.
- What answer does the formula give for the very first day of the series?The stack is empty, so the previous-stronger index is taken as `-1` and the run is `0 - (-1) = 1`: the first day is its own run of one. Any implementation that returns 0 there has either dropped the empty-stack case or is using the variant that excludes today — say which convention you intended.
- Does the answer change if you pop on strictly weaker instead of weaker-or-equal?Yes, and only for ties. Popping on weaker-or-equal folds equal-scoring days into today's run; popping on strictly weaker leaves an equal day on the stack as a boundary, cutting today's run short. Neither is more correct — the specification decides. State the rule you chose before writing the loop.
- Why store indices rather than the scores themselves?Scores alone tell you which day is stronger but not how far back it sits, and the run length is a distance. With indices, one subtraction yields the run, and the same stack simultaneously answers boundary and width questions. Storing a score plus a separately maintained run length works too, but it duplicates information the index already carries.
A stacked entry is a manager who already reports for a whole team. When they are dismissed, the team leaves with them, so counting departing managers tells you nothing about how many people walked out.
saying these in an interview costs you the question
- Reports the number of pops as the streak
- Assumes the stack still holds every earlier day
- Stores scores only, then cannot compute a distance
- Forgets the empty-stack case reaching the series start
- Falls back to a backward scan per day