Coding Interview: Solve Next Greater Element II with a Monotonic Stack

What the interviewer evaluates

Given a circular integer array, return the first strictly greater value encountered clockwise for every element, or -1 when none exists. Inputs may contain duplicates, monotonic runs, or all equal values.

Constraints and boundaries

• “Greater” is strict; an equal value cannot resolve an index.
• Index i searches i+1 through n-1, then wraps to 0.
• Each position receives at most one answer; the second pass must not overwrite a resolved result.
• Target O(n) time and O(n) extra space.

30-second answer framework

“I keep a decreasing stack of indexes that are still waiting for a greater value. I scan a virtual doubled array: a strictly larger current value pops and resolves stack entries; indexes enter only during the first pass, while the second pass supplies wraparound candidates. Each index is pushed and popped at most once, so the algorithm is linear.”

Store positions waiting for an answer

Store indexes rather than values so the algorithm can write results and preserve duplicate positions. Keep values non-increasing from the stack bottom to the top. A larger current value resolves every smaller waiting value it can pop.

Turn wraparound into a bounded scan

Read nums[i % n] for i from 0 through 2n-2. When i is below n, push the index after resolving older entries; on the second visit, use it only to resolve the remaining stack. This avoids copying the array and prevents an infinite loop.

Handle strict comparison and duplicates

Pop only when nums[current] > nums[stackTop]. Greater-than-or-equal would incorrectly let equal values resolve each other; less-than breaks the decreasing invariant. Unresolved indexes keep the initial -1.

Clarifying questions before answering

• Is “next” strictly greater? Allowing greater-or-equal changes the pop condition and duplicate behavior.
• Can the array be empty? Define the return shape before implementing.
• Should the result contain values or indexes? Distances and indexes need different wraparound calculations.

Step-by-step deep dive

Initialize every result to -1 and keep an empty stack. For virtual position i, set index = i % n and read value = nums[index]. First resolve stack indexes whose value is smaller; when i is below n, push index because it has not yet had its full clockwise search. The second pass never pushes, so every index enters once.

result = [-1] * n
stack = []
for i in range(2 * n - 1):
    index = i % n
    while stack and nums[stack[-1]] < nums[index]:
        result[stack.pop()] = nums[index]
    if i < n:
        stack.append(index)

For [1,2,1], the final 1 sees 2 after wrapping, while 2 has no strictly greater value. The remaining stack indexes correctly retain -1.

Model high-quality answer

“I store indexes that have not found an answer in a non-increasing stack. I logically scan the array twice with i % n; a current value strictly greater than the stack top pops and resolves that index. I push each index only on its first visit, so the second pass handles wraparound without duplication. Results start at -1, making equal arrays and missing answers correct. Every index is pushed and popped at most once, giving O(n) time and O(n) space.”

Common mistakes

• Copying the array three times to handle circularity.
• Pushing indexes again in the second pass, causing duplicate work or overwrites.
• Using greater-than-or-equal and treating equal values as greater.
• Scanning from the right without stating a stack invariant, so the answer is not the first greater value.
• Leaving results uninitialized and trying to repair the stack after the scan.

Failure symptoms and fixes

If [1,1,1] returns a non--1 value, the equality rule is wrong. If the last 1 in [1,2,1] returns -1, wraparound was omitted. Trace stack indexes and values and assert that every pop has a strictly larger current value.

Production implementation

Use an index type wide enough for the input. Avoid copying the array when memory is tight. To return distance, compute (index - j + n) % n when resolving index j, and define whether a zero distance is allowed.

Verification checklist

Test empty input, one element, all equal, strictly increasing, strictly decreasing, repeated peaks, and random arrays. For small inputs, compare with an O(n²) reference that scans clockwise from every index, using randomized differential tests.

Follow-up questions and answers

Why can each index be popped only once?

Once an index sees its first strictly greater value, it leaves the stack. A farther element cannot be the first greater value. Each index enters once and leaves once, so total popping is O(n).

What changes for greater-or-equal?

Pop when the current value is less than or equal to the stack top, then define how equal values should behave around the circle, including whether an element may resolve itself on a later visit.

What if the input is an infinite repeating stream?

Do not wait for every position to resolve. Set a finite observation window or timeout. For a fixed array, two passes cover every possible later candidate.

Scoring rubric

• Invariant: explains that the decreasing stack holds indexes waiting for answers.
• Circular handling: uses two bounded passes without copying or looping forever.
• Duplicate boundary: uses strict comparison and preserves unresolved -1 values.
• Complexity: gives O(n) time and O(n) extra space.
• Verification: includes an O(n²) oracle and random, duplicate, and monotonic tests.

Compliance check

Confirm that the stack invariant, circular boundaries, and complexity claim stay consistent.

Interview answer checklist

State that stack indexes wait for a greater value, then explain i % n, two passes, strict popping, one push per index, and amortized complexity.

One-sentence takeaway

A circular next-greater query becomes linear with two index passes and a decreasing monotonic stack, while strict comparison and -1 initialization preserve duplicate and missing-value semantics.