123. Next Greater Element I
🔗 LeetCode Problem: 496. Next Greater Element I
📊 Difficulty: Easy
🏷️ Topics: Array, Hash Table, Stack, Monotonic Stack
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 0-indexed integer arrays nums1 and nums2, where nums1 is a subset of nums2.
For each 0 <= 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.
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: Next greater in nums2 is -1 (no greater element)
For 1 in nums1: Next greater in nums2 is 3
For 2 in nums1: Next greater in nums2 is -1 (no greater element)
Example 2:
Input: nums1 = [2,4], nums2 = [1,2,3,4]
Output: [3,-1]
Explanation:
For 2 in nums1: Next greater in nums2 is 3
For 4 in nums1: Next greater in nums2 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 the integers of nums1 also appear in nums2
🌟 Understanding the Problem
What Are We Really Asking?
Simple version:
For each element in nums1, find its next greater element in nums2.
Example: nums2 = [1, 3, 4, 2]
Element 1: Look right → 3, 4, 2
First greater than 1? → 3 ✓
Element 3: Look right → 4, 2
First greater than 3? → 4 ✓
Element 4: Look right → 2
First greater than 4? → None, return -1
Element 2: Look right → (nothing)
First greater than 2? → None, return -1
Key Insight: We're looking for the FIRST element to the right that is LARGER.
💡 How to DISCOVER the Solution
Let me show you the natural thought process - how we'd solve this step by step.
🎯 STEP 1: Understanding "Next Greater Element"
What does "next greater" mean?
Array: [2, 1, 5, 3, 4]
For element 2:
Look right: 1 (not greater), 5 (GREATER!) ✓
Answer: 5
For element 1:
Look right: 5 (GREATER!) ✓
Answer: 5
For element 5:
Look right: 3, 4 (none greater than 5)
Answer: -1
For element 3:
Look right: 4 (GREATER!) ✓
Answer: 4
For element 4:
Look right: (nothing)
Answer: -1
Pattern:
Scan to the RIGHT until you find something BIGGER.
If found → that's the answer
If not found → return -1
🎯 STEP 2: First Attempt - What Would You Naturally Do?
Brute Force Thinking:
"For each element in nums1:
1. Find it in nums2
2. Scan right from that position
3. Return first element that's greater
4. If nothing found, return -1"
Let's code this intuition:
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
int[] result = new int[nums1.length];
for (int i = 0; i < nums1.length; i++) {
int target = nums1[i];
// Find target in nums2
int found = -1;
for (int j = 0; j < nums2.length; j++) {
if (nums2[j] == target) {
found = j;
break;
}
}
// Scan right for next greater
result[i] = -1; // Default: not found
for (int j = found + 1; j < nums2.length; j++) {
if (nums2[j] > target) {
result[i] = nums2[j];
break;
}
}
}
return result;
}
Time Complexity: O(n × m × m) where n = nums1.length, m = nums2.length
- For each element in nums1: O(n)
- Find it in nums2: O(m)
- Scan right in nums2: O(m)
Total: O(n × m²) - Very slow!
🎯 STEP 3: Can We Avoid Finding Element Each Time?
Observation:
Finding element in nums2 is slow (O(m) each time).
Can we pre-compute positions?
Yes! Use a HashMap!
Optimization 1: HashMap for positions
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
// Pre-compute positions
Map<Integer, Integer> positions = new HashMap<>();
for (int i = 0; i < nums2.length; i++) {
positions.put(nums2[i], i);
}
int[] result = new int[nums1.length];
for (int i = 0; i < nums1.length; i++) {
int target = nums1[i];
int pos = positions.get(target); // O(1) lookup!
// Scan right for next greater
result[i] = -1;
for (int j = pos + 1; j < nums2.length; j++) {
if (nums2[j] > target) {
result[i] = nums2[j];
break;
}
}
}
return result;
}
Time Complexity: O(n × m)
Better! But still scanning right each time.
🎯 STEP 4: The Bottleneck - Can We Pre-compute Next Greater?
Key Realization:
We're computing "next greater" for elements in nums2 repeatedly.
What if we pre-compute next greater for ALL elements in nums2?
Then just lookup!
New Strategy:
Step 1: Build a map: element → next greater element (for all nums2)
Step 2: For each element in nums1, just lookup in map
But how to build this map efficiently?
🎯 STEP 5: Building Next Greater Map - The Naive Way
Attempt:
Map<Integer, Integer> nextGreater = new HashMap<>();
for (int i = 0; i < nums2.length; i++) {
int current = nums2[i];
// Find next greater
int next = -1;
for (int j = i + 1; j < nums2.length; j++) {
if (nums2[j] > current) {
next = nums2[j];
break;
}
}
nextGreater.put(current, next);
}
Time: O(m²) to build the map Problem: Still quadratic! Can we do better?
🎯 STEP 6: The Insight - What Pattern Do We See?
Let's trace through an example carefully:
Array: [2, 1, 5, 3, 4]
Process 2: Look right → find 5
Process 1: Look right → find 5 (same as 2!)
Process 5: Look right → nothing
Process 3: Look right → find 4
Process 4: Look right → nothing
Wait! Notice something?
When we're at 1, we already processed 2.
Both 2 and 1 have next greater as 5.
What if we could "remember" what we've seen?
Another observation:
Array: [4, 3, 2, 5]
When we reach 5:
- 4 is waiting (next greater is 5)
- 3 is waiting (next greater is 5)
- 2 is waiting (next greater is 5)
All waiting elements get resolved by 5!
The pattern:
Elements that haven't found their next greater are "waiting".
When a larger element appears, it resolves ALL smaller waiting elements!
🎯 STEP 7: Where Should We Store "Waiting" Elements?
What do we need?
1. Store elements that are waiting
2. When a larger element appears, resolve them
3. Resolve in what order? Most recent first!
Example:
Array: [4, 3, 2, 5]
After seeing 4: waiting = [4]
After seeing 3: waiting = [4, 3] (3 is more recent)
After seeing 2: waiting = [4, 3, 2]
Now seeing 5:
- Check 2 < 5? YES → resolve 2
- Check 3 < 5? YES → resolve 3
- Check 4 < 5? YES → resolve 4
Notice: We check most recent FIRST (LIFO)
What data structure is LIFO?
STACK!
🎯 STEP 8: How Does Stack Help?
The Stack Algorithm:
Scan LEFT to RIGHT:
For each element:
1. While stack is not empty AND stack.top < current:
- Pop from stack
- This popped element's next greater is current!
2. Push current to stack
(it's waiting for its next greater)
Why this works:
Stack stores elements in DECREASING order (waiting for next greater).
When we see a larger element:
- It's the next greater for ALL smaller elements in stack
- Pop and resolve them
Elements remaining in stack:
- No next greater found → return -1
🎯 STEP 9: Visual Understanding
Array: [2, 1, 5, 3, 4]
═══════════════════════════════════════════════════════════
Process 2:
═══════════════════════════════════════════════════════════
Stack: []
Action: Push 2
Stack: [2]
Waiting: [2]
═══════════════════════════════════════════════════════════
Process 1:
═══════════════════════════════════════════════════════════
Stack: [2]
Check: 1 < 2? (Is stack.top > 1?) NO, don't pop
Action: Push 1
Stack: [2, 1]
Waiting: [2, 1]
(Note: Stack is DECREASING: 2 > 1)
═══════════════════════════════════════════════════════════
Process 5:
═══════════════════════════════════════════════════════════
Stack: [2, 1]
Check: stack.top (1) < 5? YES!
Pop 1 → Next greater for 1 is 5 ✓
Stack: [2]
Check: stack.top (2) < 5? YES!
Pop 2 → Next greater for 2 is 5 ✓
Stack: []
Action: Push 5
Stack: [5]
Resolved: 1→5, 2→5
═══════════════════════════════════════════════════════════
Process 3:
═══════════════════════════════════════════════════════════
Stack: [5]
Check: 3 < 5? (Is stack.top > 3?) NO, don't pop
Action: Push 3
Stack: [5, 3]
Waiting: [5, 3]
═══════════════════════════════════════════════════════════
Process 4:
═══════════════════════════════════════════════════════════
Stack: [5, 3]
Check: stack.top (3) < 4? YES!
Pop 3 → Next greater for 3 is 4 ✓
Stack: [5]
Check: stack.top (5) < 4? NO, stop
Action: Push 4
Stack: [5, 4]
Resolved: 3→4
═══════════════════════════════════════════════════════════
Final Stack: [5, 4]
═══════════════════════════════════════════════════════════
Elements still in stack have no next greater:
5 → -1
4 → -1
Complete map:
2 → 5
1 → 5
5 → -1
3 → 4
4 → -1
🎯 STEP 10: Why Stack Maintains Decreasing Order
This is crucial to understand!
The invariant: Stack is ALWAYS in DECREASING order (top to bottom)
Why?
When we see element X:
- We pop all elements < X
- Remaining elements are ≥ X
- We push X
- So stack is still decreasing!
Example:
Stack: [7, 5, 3] (decreasing)
New element: 4
Pop 3 (3 < 4)
Stack: [7, 5]
Can't pop 5 (5 > 4)
Push 4
Stack: [7, 5, 4] (still decreasing!)
Why decreasing order helps:
When a larger element appears, we know EXACTLY which elements
it's the next greater for: ALL smaller ones in stack!
We pop them all in one sweep.
🎯 Approach 1: Brute Force
Implementation
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
int[] result = new int[nums1.length];
for (int i = 0; i < nums1.length; i++) {
int target = nums1[i];
// Find target in nums2
boolean found = false;
result[i] = -1;
for (int j = 0; j < nums2.length; j++) {
if (found && nums2[j] > target) {
result[i] = nums2[j];
break;
}
if (nums2[j] == target) {
found = true;
}
}
}
return result;
}
Complexity Analysis
⏰ Time: O(n × m) where n = nums1.length, m = nums2.length
For each element in nums1: O(n)
Scan through nums2: O(m)
💾 Space: O(1) - excluding output array
🎯 Approach 2: HashMap + Stack (Optimal)
The Complete Strategy
Step 1: Build next greater map for all elements in nums2
- Use stack to find next greater in O(m) time
- Store in HashMap
Step 2: For each element in nums1, lookup in map
- O(1) per lookup
- Total O(n)
Total time: O(m + n) - Optimal!
Why Stack? (Summary)
1. We need to track "waiting" elements
2. Most recent waiting elements get resolved first (LIFO)
3. When larger element appears, resolve ALL smaller
4. Stack naturally maintains decreasing order
5. Each element pushed/popped once → O(m)
Implementation
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
// Step 1: Build next greater map using stack
Map<Integer, Integer> nextGreater = new HashMap<>();
Stack<Integer> stack = new Stack<>();
// Process nums2 from left to right
for (int num : nums2) {
// Pop all smaller elements - current is their next greater
while (!stack.isEmpty() && stack.peek() < num) {
nextGreater.put(stack.pop(), num);
}
// Current element is waiting for next greater
stack.push(num);
}
// Elements still in stack have no next greater
while (!stack.isEmpty()) {
nextGreater.put(stack.pop(), -1);
}
// Step 2: Build result using the map
int[] result = new int[nums1.length];
for (int i = 0; i < nums1.length; i++) {
result[i] = nextGreater.get(nums1[i]);
}
return result;
}
Detailed Dry Run
Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
═══════════════════════════════════════════════════════════
Step 1: Build next greater map for nums2 = [1,3,4,2]
═══════════════════════════════════════════════════════════
Process 1:
Stack: []
Action: Push 1
Stack: [1]
Map: {}
Process 3:
Stack: [1]
Check: stack.peek() (1) < 3? YES
Pop 1, put (1 → 3) in map
Stack: []
Action: Push 3
Stack: [3]
Map: {1→3}
Process 4:
Stack: [3]
Check: stack.peek() (3) < 4? YES
Pop 3, put (3 → 4) in map
Stack: []
Action: Push 4
Stack: [4]
Map: {1→3, 3→4}
Process 2:
Stack: [4]
Check: stack.peek() (4) < 2? NO
Action: Push 2
Stack: [4, 2]
Map: {1→3, 3→4}
After processing all:
Stack: [4, 2] (elements with no next greater)
Put (4 → -1) and (2 → -1)
Map: {1→3, 3→4, 4→-1, 2→-1}
═══════════════════════════════════════════════════════════
Step 2: Build result using map
═══════════════════════════════════════════════════════════
nums1[0] = 4: nextGreater.get(4) = -1
nums1[1] = 1: nextGreater.get(1) = 3
nums1[2] = 2: nextGreater.get(2) = -1
Result: [-1, 3, -1] ✓
Complexity Analysis
⏰ Time: O(m + n)
Building map:
- Each element in nums2 pushed once: O(m)
- Each element in nums2 popped once: O(m)
- Total: O(m)
Building result:
- Lookup for each element in nums1: O(n)
Overall: O(m + n) ✓
💾 Space: O(m)
HashMap: O(m) - stores all elements from nums2
Stack: O(m) - worst case all elements
📊 Approach Comparison
┌────────────────────────────────────────────────────────┐
│ Approach 1 Approach 2 │
│ (Brute Force) (Stack + HashMap) │
├────────────────────────────────────────────────────────┤
│ Core Idea For each in Pre-compute all │
│ nums1, scan next greater │
│ nums2 │
│ │
│ Time O(n × m) O(m + n) ✓ │
│ │
│ Space O(1) O(m) │
│ │
│ When to Small arrays Always! ✓ │
│ use │
└────────────────────────────────────────────────────────┘
🧪 Edge Cases
Edge Case 1: No Greater Element
Input: nums1 = [2], nums2 = [1,2]
Output: [-1]
2 has nothing to its right
Edge Case 2: All Elements Have Next Greater
Input: nums1 = [1,2], nums2 = [1,2,3,4]
Output: [2,3]
1 → 2, 2 → 3
Edge Case 3: Decreasing Array
Input: nums1 = [4,3,2], nums2 = [4,3,2,1]
Output: [-1,-1,-1]
All elements decreasing, no next greater
Edge Case 4: Single Element
Input: nums1 = [5], nums2 = [5]
Output: [-1]
Only one element, no next greater
⚠️ Common Mistakes
Mistake 1: Wrong stack order
// ❌ WRONG - Popping when current is smaller
while (!stack.isEmpty() && stack.peek() > num) {
stack.pop();
}
// ✓ CORRECT - Pop when current is LARGER
while (!stack.isEmpty() && stack.peek() < num) {
nextGreater.put(stack.pop(), num);
}
Mistake 2: Forgetting elements in stack
// ❌ WRONG - Not handling remaining elements
// After processing, stack might not be empty!
// ✓ CORRECT - Handle remaining elements
while (!stack.isEmpty()) {
nextGreater.put(stack.pop(), -1);
}
Mistake 3: Not checking empty stack
// ❌ WRONG - Might throw exception
while (stack.peek() < num) {
stack.pop();
}
// ✓ CORRECT - Check isEmpty first
while (!stack.isEmpty() && stack.peek() < num) {
stack.pop();
}
🎯 Pattern Recognition
This pattern works when:
- Finding "next greater/smaller" element
- Looking for first element that satisfies a condition
- Processing elements left to right
- Need to remember "waiting" elements
Similar Problems: - Daily Temperatures (LC 739) - Next Greater Element II (LC 503) - Largest Rectangle in Histogram (LC 84) - 132 Pattern (LC 456)
📝 Quick Revision Notes
🎯 Core Concept
Find next greater element efficiently using monotonic stack. Stack stores elements in decreasing order (waiting for next greater). When larger element appears, pop and resolve ALL smaller elements. Elements in stack at end have no next greater (-1).
⚡ Quick Implementation
import java.util.Arrays;
import java.util.HashMap;
import java.util.Stack;
class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
int[] res = new int[nums1.length];
Arrays.fill(res, -1);
// // Approach 1 - brute force
// for(int i = 0; i < nums1.length; i++) {
// // find index in nums2
// int index = -1;
// for(int j = 0; j < nums2.length; j++) {
// if(nums1[i] == nums2[j]) {
// index = j;
// break;
// }
// }
// if(index == -1) {
// return res;
// }
// for(int k = index + 1; k < nums2.length; k++) {
// if(nums2[k] > nums1[i]) {
// res[i] = nums2[k];
// break;
// }
// }
// }
// // Approach 2 - brute force with map that stores positions of the elements.
// HashMap<Integer, Integer> map = new HashMap<>();
// for(int i = 0; i < nums2.length; i++) {
// map.put(nums2[i], i);
// }
// for(int i = 0; i < nums1.length; i++) {
// int index = map.getOrDefault(nums1[i], -1);
// if(index == -1) {
// return res;
// }
// for(int j = index + 1; j < nums2.length; j++) {
// if(nums2[j] > nums1[i]) {
// res[i] = nums2[j];
// break;
// }
// }
// }
// // Approach 3 - precompute greater elements of num2 array and store in a map
// // where key is array element and value in next greater element
// // Now, loop through nums1 array and get the result by looking into map.
// // Need to track greater element at each index from LEFT to RIGHT - STILL O(N2)
// HashMap<Integer, Integer> map = new HashMap<>();
// for(int i = 0; i < nums2.length; i++) {
// for(int j = i + 1; j < nums2.length; j++) {
// if(nums2[j] > nums2[i]) {
// map.put(nums2[i], nums2[j]);
// break;
// }
// }
// }
// for(int i = 0; i < nums1.length; i++) {
// res[i] = map.getOrDefault(nums1[i], -1);
// }
// Approach 4 - monotonic increasing stack (4, 3, 2 => 2 being top of the stack) + hashmap
HashMap<Integer, Integer> map = new HashMap<>();
Stack<Integer> stack = new Stack<>();
for(int i = 0; i < nums2.length; i++) {
// simply push if stack is empty.
if(stack.isEmpty()) {
stack.push(nums2[i]);
} else if (stack.peek() > nums2[i]) {
// In [1,4,3,2,5] when num2 is 3, we have stack top as 4.
// We do not have an element greater than the current stack top (4). Hence push 3 also to the stack.
stack.push(nums2[i]);
} else {
while (!stack.isEmpty() && stack.peek() < nums2[i]) {
// max found for current element. Store it in map.
// For exmaple, in [1,4,3,2,5], stack stores [4,3,2] and when 5 comes, map becomes {4:5,3:5,2:5} and stack holds now 5.
int num = stack.pop();
map.put(num, nums2[i]);
}
stack.push(nums2[i]);
}
}
for(int i = 0; i < nums1.length; i++) {
res[i] = map.getOrDefault(nums1[i], -1);
}
return res;
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(Arrays.toString(s.nextGreaterElement(new int[] {4,1,2}, new int[] {1,3,4,2})));
System.out.println(Arrays.toString(s.nextGreaterElement(new int[] {2,4}, new int[] {1,2,3,4})));
}
}
🔑 Key Insights
Why Stack? - Tracks "waiting" elements (haven't found next greater) - LIFO matches our need (check recent first) - Maintains decreasing order automatically
The Algorithm:
1. Scan left to right
2. Pop smaller elements (current is their next greater)
3. Push current (waiting for its next greater)
4. Elements in stack at end → -1
Time Complexity: - Each element pushed once: O(m) - Each element popped once: O(m) - Total: O(m + n) ✓
🎪 Memory Aid
"Stack holds decreasing elements waiting"
"Larger comes → pop smaller → resolve!"
"Left to right, push and pop!" ✨
⚠️ Don't Forget
- Check
!stack.isEmpty()before peek/pop - Pop when
stack.peek() < current(current is LARGER) - Handle remaining stack elements (set to -1)
- Use
getOrDefault(num, -1)for safe lookup
Happy coding! This is your foundation for all monotonic stack problems! 🚀