Next Greater Element I — Your First Monotonic Stack Problem

Problem Statement#

Given two distinct 0-indexed integer arrays nums1 and nums2, where nums1 is a subset of nums2, for each nums1[i] find the next greater element of the same value in nums2. If no greater element exists, return -1 for that position.

Constraints:

• 1 <= nums1.length <= nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 10^4
• All integers in nums1 and nums2 are unique

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

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

Why This Problem Matters#

Next Greater Element I is officially rated Easy, but it is the gateway problem for the entire monotonic stack category. Interviewers use it to introduce the concept before pivoting to harder variants: Daily Temperatures (medium), Next Greater Element II (circular array, medium), Largest Rectangle in Histogram (hard), and Trapping Rain Water (hard). If you cannot explain the monotonic stack approach here, you will fail all those harder problems.

The problem also tests a secondary skill: using a hash map to decouple precomputation (next greater element for every element in nums2) from the query phase (looking up the answer for elements in nums1). This pattern — precompute into a hash map, then answer queries in O(1) — appears frequently in interval and range problems.

At Amazon, this appears as a warm-up or phone screen filter. The expectation is that you immediately identify the monotonic stack approach rather than proposing an O(n x m) brute force.

The Core Insight#

The brute-force approach is O(n x m): for each element in nums1, find it in nums2, then scan right for the first greater element. This works but is not interview-worthy.

The O(n + m) insight: precompute the next greater element for every element in nums2 using a single pass with a monotonic decreasing stack, then answer each query from nums1 with a hash map lookup.

Maintain a stack of elements "waiting" for their next greater element. The stack is always in decreasing order from bottom to top. When you encounter a new element x, pop everything smaller (they just found their NGE as x) and push x. After the loop, remaining stack elements have no NGE and get -1.

Visual Dry Run#

Input: nums2 = [1, 3, 4, 2]

After loop, stack = [4, 2]. Neither has NGE. Final map: {1:3, 3:4, 4:-1, 2:-1}.

Answer queries from nums1 = [4,1,2]: output is [-1, 3, -1].

Solution (Optimal)#

class Solution:
    def nextGreaterElement(self, nums1: list[int], nums2: list[int]) -> list[int]:
        nge = {}
        stack = []  # Decreasing monotonic stack
 
        for num in nums2:
            while stack and stack[-1] < num:
                nge[stack.pop()] = num
            stack.append(num)
 
        # Elements remaining in stack have no NGE (default -1 via .get)
        return [nge.get(num, -1) for num in nums1]

var nextGreaterElement = function(nums1, nums2) {
    const nge = new Map();
    const stack = [];
 
    for (const num of nums2) {
        while (stack.length > 0 && stack[stack.length - 1] < num) {
            nge.set(stack.pop(), num);
        }
        stack.push(num);
    }
 
    return nums1.map(num => nge.get(num) ?? -1);
};

Time: O(n + m) — each element in nums2 is pushed and popped at most once; each nums1 query is O(1) Space: O(m) — stack and hash map hold at most m elements

Common Mistakes#

• Using the O(n x m) brute force scan — always lead with the monotonic stack approach
• Confusing increasing vs decreasing stack: next greater uses a decreasing stack; next smaller uses an increasing stack
• Forgetting elements left in the stack after the loop — they have no NGE and need -1
• Storing indices in the stack when values are unique — for this problem, values in the stack are fine since all values are distinct
• Reversing the comparison direction: stack[-1] < num is correct for next GREATER; flip it for next SMALLER

Interview Tips#

• Open with: "This is a classic monotonic stack problem. I precompute the NGE for every element in nums2 in one O(m) pass, then answer each query in O(1) with a hash map."
• Explain the invariant: "The stack is decreasing from bottom to top. When a larger element arrives, it pops all smaller ones — each pop records that element's NGE."
• Anticipate the follow-up: "What if nums2 is circular?" — iterate twice with modular indexing (LC 503).

Follow-up Questions#

• What if nums2 is circular (LC 503)? Iterate 2n indices using modulo; only push indices during the first pass.
• What if elements in nums2 are not unique? Switch to storing indices in the stack so hash map keys remain unique.
• What if you need the next greater for all elements in a single array? Apply the same algorithm directly without a separate query step.
• Can you find the previous greater element? Process right to left with the same decreasing stack.

Key Takeaways#

• A decreasing monotonic stack finds the next greater element for every array element in O(n) time.
• Elements waiting in the stack have not yet found their NGE; a larger incoming element answers all smaller ones simultaneously.
• The push-pop-once property guarantees O(n) amortized time even when individual iterations pop multiple elements.
• Separate the precomputation phase (build NGE map over nums2) from the query phase (look up nums1 answers) using a hash map.
• This two-phase precompute-then-query pattern generalizes to many interval and range problems.
• For NGE, use a decreasing stack; for next smaller element, use an increasing stack — getting the direction wrong produces a different problem entirely.
• Remaining stack elements after the loop always map to -1; use .get(key, -1) in Python to handle this elegantly.