Next Greater Element I: Stack + Hash Map Pattern

LeetCode 496, Next Greater Element I, is an easy problem that teaches one of the most useful stack patterns in all of algorithm design. You are given two arrays, and you need to find the next greater element for each value in the first array by looking at the second array. The brute force is simple, but the optimal approach uses a monotonic stack paired with a hash map to solve it in linear time.

The problem

You are given two arrays nums1 and nums2 where nums1 is a subset of nums2. For each element in nums1, find the next greater element in nums2. The next greater element of a number x in nums2 is the first number to the right of x in nums2 that is greater than x. If no such number exists, the answer is -1.

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

For value 4 in nums1, look at nums2. The 4 sits at index 2, and there is nothing greater to its right (only 2), so the answer is -1. For value 1, it sits at index 0 in nums2, and the next greater element to its right is 3. For value 2, it sits at index 3, and there is nothing to its right at all, so the answer is -1.

The brute force

For each element in nums1, find it in nums2, then scan to the right looking for a value that is strictly greater.

def next_greater_element_brute(nums1, nums2):
    result = []
    for x in nums1:
        idx = nums2.index(x)
        found = -1
        for j in range(idx + 1, len(nums2)):
            if nums2[j] > x:
                found = nums2[j]
                break
        result.append(found)
    return result

For each of the m elements in nums1, you scan up to n elements in nums2. That is O(m * n) in the worst case. When both arrays are large, this is too slow.

The key insight

Instead of answering each query individually, you can preprocess all of nums2 in a single pass to build a hash map from each value to its next greater element. Then answering queries from nums1 is just a dictionary lookup.

The trick is a monotonic stack. Walk through nums2 from left to right. Maintain a stack that holds values in decreasing order (bottom to top). When you encounter a value that is greater than the top of the stack, it means that value is the next greater element for the top. Pop the top, record the mapping, and keep popping while the current value is still greater than the new top. Then push the current value onto the stack.

By the time you finish traversing nums2, the stack holds only values that have no next greater element. The hash map contains the answer for everything else.

Step-by-step walkthrough

Let's trace through nums2 = [1, 3, 4, 2]. At each step you will see the current element highlighted in the array, the state of the monotonic stack, and the next-greater-element map being built.

A few observations from the walkthrough:

• The stack is always decreasing. Every value we push is smaller than whatever is already on top. That is the monotonic property.
• Each element is pushed once and popped at most once. This gives us O(n) total work across the entire traversal.
• After the traversal, elements remaining on the stack (4 and 2) have no next greater element. They default to -1 in our final answer.
• The map is the bridge between nums2 and nums1. Once built, looking up any value from nums1 is O(1).

The code

def next_greater_element(nums1, nums2):
    nge_map = {}
    stack = []

    for val in nums2:
        while stack and val > stack[-1]:
            popped = stack.pop()
            nge_map[popped] = val
        stack.append(val)

    return [nge_map.get(x, -1) for x in nums1]

Let's break this down line by line:

1. nge_map stores the mapping from each value to its next greater element.
2. stack holds values in decreasing order, waiting for a greater element to appear.
3. For each val in nums2, the while loop pops all values from the stack that are smaller than val. For each popped value, val is its next greater element.
4. After the while loop, push val onto the stack. It is now waiting for its own next greater element.
5. The final line builds the result by looking up each value from nums1 in the map. If a value is not in the map, it means no next greater element was found, so we return -1.

Notice how clean this is. The stack stores values directly (not indices), and the entire preprocessing of nums2 happens in one short loop.

Complexity analysis

Time: O(m + n). Building the map takes O(n) because each of the n elements in nums2 is pushed and popped at most once. Looking up m elements from nums1 takes O(m). Total: O(m + n).

Space: O(n). The stack and the hash map each hold at most n entries.

Building blocks

The core pattern here is the monotonic stack pop loop:

while stack and compare(current, stack[-1]):
    popped = stack.pop()
    # process popped element using current
stack.append(current)

This same building block appears in many problems. The only things that change are:

• What you compare: greater than (next greater element), less than (next smaller element), or variations with equal
• What you store on the stack: values, indices, or tuples of both
• What you compute when popping: the next greater value, a distance, an area, or a water volume

For Next Greater Element I, you compare with >, store values, and record a value mapping. For Daily Temperatures, you compare with >, store indices, and record distances. For Largest Rectangle in Histogram, you compare with <, store indices, and compute areas. Same brick, different wall.

Edge cases

Before submitting, verify your solution handles:

• nums1 equals nums2: every element needs an answer, and the map covers all of them.
• Strictly increasing nums2 like [1, 2, 3, 4]: every element except the last has a next greater element. The stack never grows beyond one element.
• Strictly decreasing nums2 like [4, 3, 2, 1]: no element has a next greater element. The stack grows to n and nothing gets popped. Every answer is -1.
• Single element: nums1 = [1], nums2 = [1]. Answer is [-1].
• All elements the same like nums2 = [3, 3, 3]: equal is not greater, so nothing gets popped. Every answer is -1.
• nums2 has duplicates: the problem guarantees nums2 has distinct elements, so you do not need to worry about duplicate keys in the map.

The monotonic stack solution handles all of these without special cases.

From understanding to recall

You have seen the full monotonic stack plus hash map solution. The pattern is concise, and the code is short. But under interview pressure, small details trip people up. Did you push before or after the while loop? Did you use > or >=? Did you store values or indices?

Spaced repetition turns understanding into automatic recall. Instead of solving this problem once and moving on, you practice writing the monotonic stack pop loop at increasing intervals. After a few repetitions, the pattern is in your long-term memory and you can apply it to any next-greater-element variant without hesitation.

Related posts

• Daily Temperatures - same monotonic stack pattern
• Largest Rectangle in Histogram - another classic stack problem
• Stack Patterns - overview of stack patterns

CodeBricks breaks the monotonic stack pattern into its reusable pieces and drills them individually. You type the pop loop from scratch each time, building the muscle memory so that when you see Next Greater Element or Daily Temperatures in an interview, the code flows naturally.