Next Greater Element I (LC 496)

Pattern: Monotonic Stack + HashMap
Difficulty: Easy
Key Concept: Precompute every next-greater answer for nums2 in one O(n) pass, store it in a map, then answer each nums1 query in O(1).

Problem Statement

nums1 is a subset of nums2, both with distinct values. For each nums1[i], find the first element to its right in nums2 that is greater than it. Return -1 if none exists.

Input: int[] nums1, int[] nums2 (distinct, nums1 ⊆ nums2)
Output: int[] of the same length as nums1

Example

nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1, 3, -1]
  4 → nothing greater to its right in nums2      → -1
  1 → 3 is the first greater to its right        →  3
  2 → nothing to its right                       → -1

---

1. Algorithm & Pseudocode

Brute force

for each x in nums1:
    find index j of x in nums2          // O(n) linear search
    scan nums2 from j+1 rightwards      // O(n)
    first value > x  → record it, break
    none found       → record -1

Optimal (one monotonic stack pass + map lookup)

map   = empty HashMap<value, nextGreater>
stack = empty stack of VALUES           // distinct values, so values are safe here

for x in nums2:
    while stack not empty AND stack.top < x:
        map.put(stack.pop(), x)         // x is the next greater for everything smaller
    stack.push(x)

// whatever is left on the stack has no next greater
for i in nums1:
    result[i] = map.getOrDefault(nums1[i], -1)

---

2. Step-by-Step Analysis (Beginner-Friendly)

1. Two separate costs to kill The brute force pays twice: once to locate each nums1 value inside nums2, and again to scan forward. The fix removes both — a hash map for the lookup, a monotonic stack for the scan.

2. Decouple computation from query Nothing about the answer depends on nums1. So compute the next-greater for every value in nums2 first, cache it, and let nums1 just read from the cache. This “precompute-then-query” move shows up constantly in interviews.

3. Why values on the stack are safe here (and usually aren’t) The problem guarantees all values are distinct, so a value uniquely identifies an element and can be a map key. In almost every other monotonic-stack problem you must push indices — either because duplicates exist or because you need a distance/width. Call out that you noticed the distinctness guarantee.

4. What the stack invariant means The stack holds values still waiting for a greater neighbour, decreasing bottom to top. A new bigger value x resolves all of them in one sweep.

5. getOrDefault handles the leftovers Values still on the stack at the end were never resolved, so they were never put in the map, so getOrDefault(..., -1) returns exactly the required -1. No cleanup pass needed.

---

3. The Dry Run

nums2 = [1, 3, 4, 2]

Step	x	Pops → map entry	Stack after	Map
1	1	—	[1]	{}
2	3	pop 1 → 1→3	[3]	{1:3}
3	4	pop 3 → 3→4	[4]	{1:3, 3:4}
4	2	— (2 < 4)	[4, 2]	{1:3, 3:4}

Leftover 4 and 2 never resolved → absent from the map → default -1.

Now answer nums1 = [4, 1, 2]:

query	map lookup	result
4	miss	-1
1	hit → 3	3
2	miss	-1

Final: [-1, 3, -1] ✓

---

4. Java Solution

Brute Force

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] res = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            res[i] = -1;
            int j = 0;
            while (j < nums2.length && nums2[j] != nums1[i]) j++;   // locate
            for (int k = j + 1; k < nums2.length; k++) {            // scan right
                if (nums2[k] > nums1[i]) { res[i] = nums2[k]; break; }
            }
        }
        return res;
    }
}

Time O(m·n) · Space O(1) extra

Optimal

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer, Integer> nextGreater = new HashMap<>();
        Deque<Integer> stack = new ArrayDeque<>();     // values, decreasing bottom→top

        for (int x : nums2) {
            // x resolves every pending value smaller than it
            while (!stack.isEmpty() && stack.peek() < x) {
                nextGreater.put(stack.pop(), x);
            }
            stack.push(x);
        }

        int[] res = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            res[i] = nextGreater.getOrDefault(nums1[i], -1);   // unresolved → -1
        }
        return res;
    }
}

Time O(m + n) · Space O(n)

---

5. The “Java vs. Others” Edge

• getOrDefault replaces a containsKey + get pair — one hash lookup instead of two, and it reads as a single intent. map.getOrDefault(k, -1) is idiomatic modern Java.
• Deque<Integer> autoboxing and the Integer cache: stack.peek() < x unboxes the Integer to compare against int — that’s fine. But never write stack.peek() == someInteger for values outside −128..127; Integer identity comparison silently breaks above the cache range. Compare primitives or use .equals().
• ArrayDeque over Stack — see LC 739; Stack is a synchronized Vector with bottom-to-top iteration.
• Enhanced for-loop over int[] (for (int x : nums2)) has no boxing at all — the array is primitive. The boxing only happens at the stack.push(x) boundary.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute force	O(m·n)	O(1)	Locate + scan, both linear
Stack + HashMap	O(m + n)	O(n)	One pass over nums2, O(1) per query

---

Related Problems

#	Problem	Difference
LC 503	Next Greater Element II	circular array — loop i to 2n, push only while i < n
LC 739	Daily Temperatures	answer is the distance, so push indices not values
LC 556	Next Greater Element III	digits of a number — next permutation, not a stack