Next Greater Element I

Description

496. Next Greater Element I

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 0-indexed integer arrays nums1 and nums2, where nums1 is a subset of nums2.

For each $0\le i<\text{nums1.length}$, find the index $j$ such that $\text{nums1}[i]==\text{nums2}[j]$ and determine the next greater element of $\text{nums2}[j]$ in nums2. If there is no next greater element, then the answer for this query is -1.

Return an array ans of length nums1.length such that ans[i] is the next greater element as described above.

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

• For 4 in nums1: 4 is at nums2[2]. There is no element greater than 4 to its right. Answer is -1.
• For 1 in nums1: 1 is at nums2[0]. The next element greater than 1 to its right is 3. Answer is 3.
• For 2 in nums1: 2 is at nums2[3]. There is no element to its right. Answer is -1.

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

Constraints:

• $1\le \text{nums1.length}\le \text{nums2.length}\le 1000$
• $0\le \text{nums1}[i],\text{nums2}[i]\le 10^4$
• All integers in nums1 and nums2 are unique.
• All the integers of nums1 also appear in nums2.

---

Approach 1: Brute Force with Hash Map

Intuition

First, record the index of every element in nums2 using a hash map so we can jump straight to its position. For each number in nums1, start scanning to the right in nums2 starting from that index until we find the first element strictly larger than it.

import java.util.HashMap;
import java.util.Map;
 
class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer, Integer> indexMap = new HashMap<>();
        for (int i = 0; i < nums2.length; i++) {
            indexMap.put(nums2[i], i);
        }
 
        int[] result = new int[nums1.length];
 
        for (int i = 0; i < nums1.length; i++) {
            int num = nums1[i];
            int startIndex = indexMap.get(num);
            int nextGreater = -1;
 
            for (int j = startIndex + 1; j < nums2.length; j++) {
                if (nums2[j] > num) {
                    nextGreater = nums2[j];
                    break;
                }
            }
 
            result[i] = nextGreater;
        }
 
        return result;
    }
}
 

Complexity

• Time Complexity: $O(M\times N)$ — Where $M=\text{nums1.length}$ and $N=\text{nums2.length}$. In the worst case, we scan up to $N$ elements for each of the $M$ elements in nums1.
• Space Complexity: $O(N)$ — Hash map stores indices of elements in nums2.

---

Most Optimized Solution: Monotonic Stack + Hash Map ($O(M+N)$)

Intuition

Instead of searching to the right repeatedly, precompute the next greater element for every number in nums2 in a single pass using a Monotonic Decreasing Stack:

1. Maintain a stack of elements that are still waiting to find their “next greater element.”
2. Iterate through nums2. For each current number num:
   • While num is larger than the top element of the stack, num is the next greater element for that top value! Pop it from the stack and store (popped_value -> num) in a Hash Map.
3. Push num onto the stack.
4. After processing nums2, any numbers remaining in the stack have no greater element to their right, so their mapped value is -1 (defaulting via getOrDefault).
5. Finally, construct the answer array by doing $O(1)$ map lookups for each element in nums1.

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;
 
class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer, Integer> nextGreaterMap = new HashMap<>();
        Stack<Integer> stack = new Stack<>();
 
        for (int num : nums2) {
            // While current number is greater than stack's top, map top -> num
            while (!stack.isEmpty() && stack.peek() < num) {
                nextGreaterMap.put(stack.pop(), num);
            }
            stack.push(num);
        }
 
        // Build result for nums1 using precomputed map
        int[] result = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            result[i] = nextGreaterMap.getOrDefault(nums1[i], -1);
        }
 
        return result;
    }
}
 

Complexity

• Time Complexity: $O(M+N)$ — Each element of nums2 is pushed and popped from the stack at most once ($O(N)$). Building the result array takes $O(M)$ time.
• Space Complexity: $O(N)$ — Stack and Hash Map store up to $N$ elements from nums2.

---

Easy Memory Rule

“Maintain a decreasing stack for nums2. When a bigger number comes along, pop smaller numbers and save (popped_item -> bigger_number) in a map.”

Core Data Structures

• Stack<Integer>: Stores numbers from nums2 whose next greater element has not been found yet. Because elements are kept in decreasing order, the smallest number in the stack is always at the top (stack.peek()).
• Map<Integer, Integer>: Stores the result for each processed number as a key-value pair: (Number -> Next Greater Element).

---

Phase 1: Finding Next Greater Elements in nums2

We iterate through nums2 element by element (num):

1. Compare with Stack Top (while (!stack.isEmpty() && stack.peek() < num)):
   • Before pushing num onto the stack, check if num is strictly greater than the number at the top of the stack.
   • If num is greater, then num is the first element to the right that is larger than stack.peek().
2. Pop and Record (nextGreaterMap.put(stack.pop(), num)):
   • Remove the top element from the stack using stack.pop().
   • Save the relationship in the map: key = popped element, value = num.
   • Continue this loop to check if num is also greater than the next element below it in the stack.
3. Push Current Element (stack.push(num)):
   • Push num onto the stack so its own next greater element can be determined in future iterations.

---

Phase 2: Generating Output for nums1

We iterate through nums1 and retrieve the precomputed answers:

1. For each nums1[i], perform a lookup in nextGreaterMap.
2. nextGreaterMap.getOrDefault(nums1[i], -1):
   • If nums1[i] was popped during Phase 1, return its mapped value.
   • If nums1[i] remained in the stack at the end, no larger element existed to its right, so return -1.

---

Exact Step-by-Step Code Trace

Given nums2 = [2, 1, 3] and nums1 = [1, 2]:

Iteration 1 (num = 2):

• Stack is empty. Skip while loop.
• Execute stack.push(2).
• Stack: [2] | Map: {}

Iteration 2 (num = 1):

• stack.peek() is 2. Since 2 < 1 is false, skip while loop.
• Execute stack.push(1).
• Stack: [2, 1] | Map: {}

Iteration 3 (num = 3):

• stack.peek() is 1. Since 1 < 3 is true:

• Pop 1. Store map.put(1, 3).

• stack.peek() is 2. Since 2 < 3 is true:

• Pop 2. Store map.put(2, 3).

• Stack is now empty. Exit while loop.

• Execute stack.push(3).

• Stack: [3] | Map: {1: 3, 2: 3}

Lookup Phase (nums1 = [1, 2]):

• For 1: map.getOrDefault(1, -1) $\to$ 3
• For 2: map.getOrDefault(2, -1) $\to$ 3
• Output: [3, 3]