Next Greater Element I Solution

Problem

You have two arrays where nums1 is a subset of nums2. For each number in nums1, find the first number to its right in nums2 that is strictly greater — that is, the next greater element within nums2's ordering. Return -1 if no such element exists.

Input: nums1 = [4, 1, 2], nums2 = [1, 3, 4, 2]
Output: [-1, 3, -1]
Explanation: In nums2, 4 has nothing greater to its right, 1 is followed by 3 (greater), and 2 has nothing greater to its right.

Counter-example: nums1 = [2], nums2 = [3, 1, 2] → output is [-1] because 2 appears at the end of nums2 with nothing to its right, even though 3 exists elsewhere in the array.

Intuition

The problem asks: for each element, what is the first "breakthrough" — the first value to the right that breaks the non-increasing run? A monotonic stack captures exactly this relationship: as we scan nums2, we keep a stack of elements still waiting for their next greater. The moment we see a larger value, every smaller element in the stack has found its answer.

Approach 1 — Brute Force

For each element in nums1, locate it in nums2, then scan right until a larger value is found.

Build a position map from each value in nums2 to its index (values are unique per constraints).
For each number in nums1, start scanning nums2 from the position right after that number.
Return the first value encountered that is greater, or -1 if the scan reaches the end.

1def nextGreaterElement(nums1: list[int], nums2: list[int]) -> list[int]:
2    position = {val: idx for idx, val in enumerate(nums2)}
3    result = []
4
5    for num in nums1:
6        next_greater = -1
7        # scan everything to the right of num's position in nums2
8        for j in range(position[num] + 1, len(nums2)):
9            if nums2[j] > num:
10                next_greater = nums2[j]
11                break
12        result.append(next_greater)
13
14    return result

Time: O(n · m) — for each of the n elements in nums1, we scan up to m elements of nums2.
Space: O(m) — the position map holds one entry per element of nums2.

Approach 2 — Monotonic Stack

Precompute the next greater element for every value in nums2 in a single pass using a decreasing stack, then answer each nums1 query in O(1).

Initialize an empty stack and an empty hashmap next_greater.
Iterate through each num in nums2:
- While the stack is non-empty and the top of the stack is less than num, pop the top — num is its next greater element, so record next_greater[popped] = num.
- Push num onto the stack.
Elements remaining in the stack after the full scan have no next greater element; they'll default to -1 via the map.
For each element in nums1, return next_greater.get(element, -1).

1def nextGreaterElement(nums1: list[int], nums2: list[int]) -> list[int]:
2    next_greater = {}
3    # stack holds elements waiting for a greater value to appear to their right
4    decreasing_stack = []
5
6    for num in nums2:
7        # current num "answers" every smaller element still in the stack
8        while decreasing_stack and decreasing_stack[-1] < num:
9            next_greater[decreasing_stack.pop()] = num
10        decreasing_stack.append(num)
11
12    # elements left in stack have no next greater → not in map → defaults to -1
13    return [next_greater.get(n, -1) for n in nums1]

Time: O(n + m) — each element of nums2 is pushed and popped at most once; each element of nums1 is looked up in O(1).
Space: O(m) — the stack and hashmap each hold at most m entries.

Complexity Summary

Approach	Time	Space	When to use
Brute Force	O(n · m)	O(m)	Acceptable when both arrays are tiny (< 100 elements)
Monotonic Stack	O(n + m)	O(m)	Preferred — precomputes all answers in one sweep

Common Mistakes

Searching in nums1 instead of nums2 — the "next greater" relationship is defined by position within nums2, not nums1. Always locate the element in nums2 and scan right from there.
Scanning left instead of right — "next greater" means to the right. A common slip is iterating backward or from index 0.
Using a monotonic increasing stack — the stack must stay in decreasing order so that each new larger element can pop and answer all smaller waiting values. An increasing stack would never trigger pops at the right time.
Forgetting that stack leftovers have no answer — elements still in the stack after the full scan have no next greater element. Using .get(n, -1) or getOrDefault handles this without extra cleanup.
Confusing "next greater in nums1" with "next greater in nums2" — nums1 is only used to select which elements to answer. The entire next-greater structure is built from nums2.

Next Greater Element I — Solution