top of page

Next Greater Element II: The Circular Monotonic Stack

Nov 2
2 min read

Next Greater Element II (LeetCode 503) gives a circular array and asks, for each element, the first larger value you meet walking forward and wrapping around. Brute force is O(n^2); the interviewer wants O(n).

The stack idea

Keep a stack of indices whose answer is still unknown. Values on the stack are decreasing from bottom to top. When a new value is larger than the value at the top index, that new value is the answer for the top index, so pop and record it. Keep popping while that holds, then push the current index.

Handling the wrap

Loop i from 0 to 2n - 1 and read nums[i % n]. The second pass lets elements near the end find a larger value near the start. Only push indices during the first pass, because pushing in the second pass would just repeat work.


def nextGreaterElements(nums):
    n = len(nums)
    res = [-1] * n
    st = []
    for i in range(2 * n):
        x = nums[i % n]
        while st and nums[st[-1]] < x:
            res[st.pop()] = x
        if i < n:
            st.append(i)
    return res

Why it is linear

Each index is pushed once and popped at most once, so the total work is O(n) even though there is a nested while loop. Say this out loud; it is the part interviewers listen for.

Common slips

  • Using values instead of indices on the stack, which makes duplicates impossible to resolve.

  • Using <= instead of <, which pops equal values that have no greater element yet.

  • Forgetting that the maximum element keeps -1.

Disclosure: I work on AI coding interview assistant, a tool that helps candidates practice explaining patterns like this one under time pressure.

 
 
 

Recent Posts

See All
Image Smoother (LeetCode 661): Clean Neighbor Loops

For each cell of a grayscale image, replace it with the floor of the average of itself and its up to eight neighbors. Idea Loop over the 3x3 block around each cell, skip coordinates outside the grid,

 
 
 

Comments


bottom of page