Next Greater Element I — Monotonic Stack with HashMap

Problem Statement#

The next greater element of some element x in an array is the first greater element that is to the right of x in the same array.

You are given two distinct integer arrays nums1 and nums2, where nums1 is a subset of nums2. For each 0 &lt;= i < nums1.length, find the index j such that nums1[i] == nums2[j] and determine the next greater element of nums2[j] in nums2. If there is no next greater element, then the answer for this query is -1.

Constraints:

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

Input:  nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1,3,-1]
Explanation:
4 → no element greater than 4 to its right in nums2 → -1
1 → next greater after 1 in nums2 is 3 → 3
2 → no element greater than 2 to its right in nums2 → -1

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

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

Why This Problem Matters#

LC 496 is the gateway problem to the monotonic stack + hash map combo pattern. It extends the Daily Temperatures concept by separating the "precompute all next-greater values" phase from the "answer queries" phase. This two-phase approach is fundamental to:

• Next Greater Element II (LC 503, circular array)
• Online Stock Span (LC 901)
• 132 Pattern (LC 456)
• Car Fleet (LC 853)

The pattern is: precompute next-greater for all elements in nums2 using a monotonic stack, store results in a hash map, then answer each nums1 query in O(1). This decoupling allows O(n+m) total time instead of O(n*m) brute force.

Companies that ask this: Amazon, Google, Meta, and Bloomberg — often as a stepping stone before asking Next Greater Element II or Daily Temperatures.

The Core Insight#

Brute force: For each element in nums1, find it in nums2 and scan rightward for the next greater element. O(n*m) time.

Monotonic stack + hash map: Process nums2 once with a monotonic stack to precompute the next greater element for every value. Store results in nge (next greater element) map. Then for each query in nums1, look up in O(1).

The monotonic stack maintains values in decreasing order. When a new element x arrives that is larger than the stack top, the stack top has found its next greater element (x). Pop and record in the map. Continue popping while the condition holds.

Key insight: Because all values in nums1 and nums2 are unique, mapping value → next greater value is unambiguous. We store nge[value] = next_greater_value rather than indexing by position.

Visual Dry Run#

nums2 = [1,3,4,2], processing with monotonic stack:

Remaining stack [4,2]: no next greater → nge[4]=-1, nge[2]=-1 (default).

nums1 = [4,1,2] queries:

• nge.get(4, -1) = -1
• nge.get(1, -1) = 3
• nge.get(2, -1) = -1

Result: [-1, 3, -1]

Solution (Optimal)#

# Python — monotonic stack + hash map, O(n+m) time
def nextGreaterElement(nums1: list[int], nums2: list[int]) -> list[int]:
    # Precompute next greater element for every value in nums2
    nge = {}      # maps value → its next greater element (or -1)
    stack = []    # monotonic decreasing stack of VALUES (not indices)
 
    for x in nums2:
        # x is greater than everything currently on the stack
        # those stack elements have found their next greater element
        while stack and stack[-1] < x:
            nge[stack.pop()] = x
        stack.append(x)
 
    # Remaining stack elements have no next greater element
    for x in stack:
        nge[x] = -1
 
    # Answer queries using the precomputed map
    return [nge[x] for x in nums1]

// JavaScript — monotonic stack + hash map, O(n+m) time
function nextGreaterElement(nums1, nums2) {
    const nge = new Map();  // value → next greater value
    const stack = [];       // monotonic decreasing stack of values
 
    for (const x of nums2) {
        while (stack.length > 0 && stack[stack.length - 1] < x) {
            nge.set(stack.pop(), x);
        }
        stack.push(x);
    }
 
    // Remaining in stack have no next greater element
    for (const x of stack) {
        nge.set(x, -1);
    }
 
    return nums1.map(x => nge.get(x));
}

Complexity:

Common Mistakes#

1. Storing indices instead of values in the stack. Since nums1 queries are by value, the map key must be the value, not the index. Here we store values in the stack (unlike Daily Temperatures where we store indices).

2. Not handling remaining stack elements. After processing nums2, elements still in the stack have no next greater element. You must explicitly set them to -1 (or rely on a default in the map lookup).

3. Processing nums1 instead of nums2 with the stack. The stack processes nums2 (the full array). nums1 is only for querying. A common mistake is to iterate nums1 with the stack.

4. Using nge[x] without default when x is not in the map. In Python, use nge.get(x, -1). In JavaScript, use nge.has(x) ? nge.get(x) : -1. Values with no next greater element may not be in the map if you handle them lazily.

5. Confusing this problem with Next Greater Element II. NGE I has a linear array (no wrap-around). NGE II is circular. Do not add the % n modulo logic here.

Interview Tips#

• State the two-phase approach: "Phase 1: precompute next-greater for all of nums2 using a monotonic stack — O(n). Phase 2: answer each nums1 query in O(1) using the hash map — O(m). Total O(n+m)."
• Clarify why you store values (not indices) in the stack: "Since the queries are by value and all values are unique, I map value to next-greater-value directly."
• If asked about the difference from NGE II: "In this problem, the array is linear — no circular wrap-around. I process nums2 once without doubling it."

Follow-up Questions#

1. Next Greater Element II (LC 503) — circular array; process 2n elements with modulo indexing.
2. What if nums1 is not a subset of nums2? Add a check — if the value is not in nums2, return -1. Or use a hash set of nums2 for O(1) membership checking.
3. Previous Greater Element. Process from right to left with a decreasing stack, or process left to right with the stack storing elements to find PGE for elements arriving later.
4. Next Smaller Element. Same stack approach but with a monotonic increasing stack (pop when new element is smaller than stack top).
5. Next Greater Element for all elements in nums2 itself. Return the nge map values in order of nums2 — no separate query step needed.

Key Takeaways#

• Two-phase pattern: precompute next-greater for all elements in nums2 using a monotonic stack (O(n)), then answer each nums1 query in O(1) using a hash map.
• Store values (not indices) in the stack when the queries are by value and all values are unique.
• Elements remaining in the stack after processing nums2 have no next greater element → they map to -1.
• This problem uses a monotonically decreasing stack: pop when the new element is greater than the top, recording the pair (top → new element) in the map.
• The O(n+m) solution is strictly better than the O(n*m) brute force — always explain this trade-off explicitly in interviews.
• Mastering this problem unlocks Next Greater Element II (circular), Stock Span, and 132 Pattern — all use the same monotonic stack precomputation idea.