Next Greater Element I (LeetCode 496)

The problem

You get two arrays of distinct integers, nums1 and nums2, where every value in nums1 also appears in nums2. For each x in nums1, find where x sits in nums2 and return the first value to its right that is larger than x. If there is none, the answer for x is -1.

Input:  nums1 = [4, 1, 2], nums2 = [1, 3, 4, 2]
Output: [-1, 3, -1]

In nums2, nothing to the right of 4 is bigger, 1 is followed by 3, and 2 is the last element.

How to think about it

Start with brute force. For each x in nums1, find it in nums2, then scan right until you see something bigger. That is O(m · n) in the worst case, where m = len(nums1) and n = len(nums2). Fine for tiny inputs, but it repeats the same rightward scans over and over.

Separate the queries from the work. Because the values in nums2 are distinct, “the next greater element of x” is a property of x alone. So compute it once for every value in nums2, store it in a dictionary, and answer each query from nums1 with a lookup.

The key insight: one left-to-right pass with a decreasing stack finds every next greater element. Keep a stack of values that are still waiting for something bigger. Those waiting values are always in decreasing order from bottom to top, because anything smaller than a later value would already have been resolved by it. When a new value x arrives, it is the answer for every waiting value smaller than it: pop them and record x for each. Then push x, since it now waits too.

Which pattern is this? Monotonic stack. The tell is the phrase “next greater” (or next smaller, previous greater). Any time each element needs the first element to one side that beats it, reach for this stack.

Approach

1. Create an empty dictionary nge and an empty stack st.
2. Walk nums2 from left to right. For each x:
   • While the stack top is smaller than x, pop it and set nge[popped] = x.
   • Push x.
3. Values still on the stack at the end have no greater element.
4. Return [nge.get(x, -1) for x in nums1].

Solution

def next_greater_element(nums1, nums2):
    nge = {}; st = []
    for x in nums2:
        while st and st[-1] < x:      # x is the first bigger value for these
            nge[st.pop()] = x
        st.append(x)                  # x now waits for its own answer
    return [nge.get(x, -1) for x in nums1]
# next_greater_element([4,1,2], [1,3,4,2]) -> [-1,3,-1]

Dry run

Building nge from nums2 = [1, 3, 4, 2]:

4 and 2 are never popped, so they map to -1. Looking up [4, 1, 2] gives [-1, 3, -1].

Complexity

• Time: O(n + m). Each value of nums2 is pushed once and popped at most once, so the while loop does O(n) work in total across the whole pass. Answering nums1 is O(m).
• Space: O(n). The dictionary and the stack each hold at most n values.

Edge cases and pitfalls

• Strictly increasing nums2 pops one value per step; strictly decreasing pops nothing, and every answer is -1.
• Use <, not <=. The problem wants strictly greater. With distinct values this makes no difference, but it matters in variants with duplicates.
• Keying by value only works because values are distinct. If duplicates were allowed you would store indices on the stack and key the answers by index.
• “It looks O(n²)” because of the nested while loop. It isn’t: count pushes and pops, not loop nesting. Be ready to explain this amortised argument.

Related problems

• Next Greater Element II (LeetCode 503): the same stack on a circular array, using indices.
• Daily Temperatures (LeetCode 739): next greater element, but return the distance instead of the value.
• Online Stock Span (LeetCode 901): the mirror question, “previous greater”, answered online.