How does a monotonic-stack next-greater scan cover a circular array without duplicating it in memory?
answer
- the answer may lie before where you started
- how many laps over the roster
- one index, visited twice
- step mod n over 2n steps
- guard the push to the first lap
basics
~20 sRun the loop for 2n steps and index the data with step modulo n, pushing only during the first n steps. The second lap lets early positions see values that wrap past the end; whatever is still stacked has no answer.
solid answer
~50 sIn a rotating on-call roster the answer for the last shift may sit at the front of the schedule, so a single left-to-right pass cannot find it. The fix is not to materialise a doubled copy: iterate `step` from 0 to 2n-1 and read position `step mod n`, so every index gets a second visit and can therefore be compared against every other index. Push only while `step < n` — a second-pass push would register an index that is already on the stack, and it could later be popped and overwritten with a farther, wrong answer. Popping and answering happen on both laps. Complexity is unchanged: at most n pushes, at most n pops, 2n outer steps, so `O(n)` time and `O(n)` space with a constant factor of two. Indices surviving all 2n steps are global maxima and correctly get no answer.
code
pseudocode · 11 linesstack = empty // indices, ratings non-increasing
for i in 0..n-1:
ans[i] = NONE
for step in 0..2*n-1:
i = step mod n
while not empty(stack) and rating[top(stack)] < rating[i]:
ans[pop(stack)] = i
if step < n:
push(stack, i) // never re-register on the second lap
...
// indices left in stack tie the maximum rating: no answer existsgo deeper
Recall that a circular sequence needs each position visited twice, and that the second visit is done with modulo arithmetic rather than by copying the data.
Explain the push guard and why exactly two laps suffice: after the second lap every stacked index has been offered every element in the sequence as a candidate answer.
Show that you can justify the leftovers as global maxima rather than defects, and that you would avoid materialising a doubled copy when the records themselves are large.
Own the framing: decide whether the domain really is circular before adding the second lap, because a wrap-around answer that the business does not consider valid is a correctness bug dressed as a clever trick.
## What changes when the data is circular A rotating on-call roster has no true end: after the last shift the schedule wraps to the first. So "the next on-call with a higher seniority rating" for the final shift may be found near the front. The linear scan answers only questions whose answer lies strictly to the right in storage order; every wrap-around answer is missed, and those positions wrongly get the sentinel. ## Two ways to fix it, only one worth doing **Materialise a doubled sequence.** Concatenate the roster with itself, run the ordinary scan over 2n entries, then keep the answers for the first n positions and map each answer index back with a modulo. This is correct, and it is still `O(n)` time and `O(n)` space — but it copies the payload, and if records are fat, the copy dominates the actual work. **Index modulo n.** Keep one copy. Let the outer loop run `step` from 0 to 2n-1 and set `i = step mod n`. Every index is now visited twice, so every stacked index is offered every other element as a potential answer at least once. Nothing is copied, and the answer array stays length n with no remapping. ## The push guard is the part people get wrong Pop and answer on both laps; **push only when `step < n`**. The reason is that pushing on the second lap would place an index on the stack that may already be there, or that was already answered on the first lap. That duplicate can then be popped by a later element, overwriting a correct near answer with a farther one, and the invariant "the stack holds each open question exactly once" is destroyed. Some implementations instead push unconditionally and guard the *write* (`only set ans[j] if still unset`); that also works, but it needs two guards instead of one and it lets the stack grow past n. The single guard on the push is the cleaner statement of the same intent. ## Why 2n steps are enough, and why 3n adds nothing An index pushed during the first lap stays on the stack until something strictly greater pops it. Between its push at position `i` and the end of the run at step 2n-1, the scan visits every position of the roster at least once — the remainder of the first lap covers `i+1..n-1`, and the second lap covers `0..i`. So the index has been offered every element in the roster as a candidate answer. If it is still stacked at the end, no element anywhere is strictly greater than it, meaning it ties the global maximum. A third lap can only re-offer elements that have already failed, so it changes nothing; running 3n steps is a sign the candidate has not reasoned about coverage. This is also the clean answer to "how can leftovers be correct in a circular structure, where every element has something after it?" — having something after you is not the same as having something *greater* after you. The maxima are genuinely unanswerable, and there is at least one of them. ## Complexity Pushes: exactly n (one per first-lap step). Pops: at most n. Outer steps: 2n. Constant work per step, so `O(n)` time, `O(n)` auxiliary space. The doubled loop multiplies the constant factor by two and leaves the asymptotic class untouched; a candidate who says "two passes so it's quadratic" has confused sequential passes with nested ones. ## The same trick, generalised The `2n` with `mod n` device is the standard way to turn any single-pass, left-to-right sequence algorithm into its circular form, provided each element only needs to be *seen* once more to be resolved. It is exactly the same accounting: the number of pushes still bounds the number of pops, and the extra lap only supplies missing candidate answers. If an algorithm needs an element to be *processed* twice rather than merely seen, the trick does not apply and the guard on the second lap will not save it. ## Trace to keep in your pocket Ratings 3, 1, 2 arranged in a rotation. First lap: push 0 (rating 3); rating 1 does not pop it, push 1; rating 2 pops index 1 and answers with position 2, push 2. Second lap: rating 3 pops index 2 and answers with position 0, then does not pop index 0 (equal is not greater) and does not push. Rating 1 and rating 2 pop nothing. Index 0 survives — it is the maximum, so it correctly has no answer.
- Why do indices still on the stack after 2n steps genuinely have no answer?An index pushed at position i is offered every other position before the run ends: the rest of the first lap covers everything after it, and the second lap covers everything before it. Surviving means nothing anywhere is strictly greater, so it ties the roster maximum. In a circular structure every element has a successor, but not every element has a greater one.
- What goes wrong if you push during the second lap as well?An index can end up on the stack twice, or be re-registered after it was already answered. A later element then pops the duplicate and overwrites a correct near answer with a farther one, and the stack may exceed n entries. Either guard the push to the first lap, or guard the write so an answer is never overwritten — the push guard is simpler.
- Does the doubled loop change the complexity?No. There are still at most n pushes and n pops, and the outer loop runs 2n times with constant work per step, so it stays O(n) time and O(n) space with a constant factor of two. Two sequential passes add, they do not multiply; only a nested loop that does fresh work per outer step would raise the class.
saying these in an interview costs you the question
- Believes one left-to-right pass already covers wrap-around answers
- Pushes indices again during the second lap
- Says two passes make the scan quadratic
- Runs three or more laps thinking one wrap is not enough
- Calls leftover stack entries a bug in the circular case