Definition
- Monotonic stack – a stack maintained in decreasing order from bottom to top, holding values awaiting their next greater element.
- Resolution – when the current value exceeds the stack top, the current value is the next greater for that top, so pop and record it.
- HashMap – stores the mapping from each value to its next greater element for O(1) lookup.
- Query – since
nums1is a subset ofnums2, read each answer from the map after processingnums2. - Complexity – O(n + m) time where n is the length of
nums2and m is the length ofnums1.
Priya at the National Bank of India reviews a sequence of daily closing stock prices and wants, for each day, the next day whose price is higher. She keeps a pile of waiting days whose answer she has not found yet. When a new higher price arrives, it answers every waiting day on the pile that is lower, so she pops them and writes down the answer. Days still waiting at the end never find a higher day and get -1.
Understanding the Concepts
What is the Next Greater Element problem?
Given two arrays nums1 (a subset of nums2), for each element in nums1, find the first element to its right in nums2 that is larger. If no such element exists, return -1.
At the National Bank of India, Rajesh monitors stock prices and wants to know, for each stock on his watchlist (nums1), the next trading day in the full price series (nums2) that exceeds the current day's price.
How does the monotonic stack approach work?
Scan nums2 left to right. Maintain a stack that stays decreasing from bottom to top. When the current value exceeds the stack top, it is the next greater element for that top.
package com.bank.analytics;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;
public class NextGreaterElement {
public static int[] nextGreater(int[] watchlist, int[] prices) {
Map<Integer, Integer> map = new HashMap<>();
Deque<Integer> stack = new ArrayDeque<>();
for (int price : prices) {
while (!stack.isEmpty() && price > stack.peek()) {
map.put(stack.pop(), price);
}
stack.push(price);
}
int[] result = new int[watchlist.length];
for (int i = 0; i < watchlist.length; i++) {
result[i] = map.getOrDefault(watchlist[i], -1);
}
return result;
}
public static void main(String[] args) {
int[] watchlist = {4, 1, 2};
int[] prices = {1, 3, 4, 2};
int[] result = nextGreater(watchlist, prices);
for (int i = 0; i < watchlist.length; i++) {
System.out.println(watchlist[i] + " -> " + result[i]);
}
}
}
4 -> -1
1 -> 3
2 -> -1
Why does the stack stay decreasing?
When a larger value arrives, it resolves and removes all smaller pending values on top. After that sweep, the larger value sits on top. Values below it are at least as large, maintaining the decreasing order. No element needs to be revisited.
What is the step-by-step trace?
For prices = [1, 3, 4, 2]:
- Process 1: stack is empty, push 1. Stack: [1]
- Process 3: 3 > 1, pop 1, map 1->3. Push 3. Stack: [3]
- Process 4: 4 > 3, pop 3, map 3->4. Push 4. Stack: [4]
- Process 2: 2 < 4, push 2. Stack: [4, 2]
- End: remaining {4, 2} have no next greater. Map 4->-1, 2->-1.Final map: {1:3, 3:4, 4:-1, 2:-1}.
What is the time and space complexity?
| Operation | Cost |
|---|---|
| Stack processing of nums2 | O(n), each element pushed and popped at most once |
| HashMap lookup for nums1 | O(m), one lookup per query element |
| Total | O(n + m) |
| Space | O(n) for the map and stack |
How is this different from the brute-force approach?
// Brute force: O(m * n) per query element
for (int i = 0; i < nums1.length; i++) {
boolean found = false;
for (int j = indexOf(nums1[i], nums2) + 1; j < nums2.length; j++) {
if (nums2[j] > nums1[i]) {
result[i] = nums2[j];
found = true;
break;
}
}
if (!found) result[i] = -1;
}
// Monotonic stack: O(n + m)
// Build the map in one pass over nums2, then answer all queries from the map.
What are common mistakes?
Using >= instead of > in the stack comparison. The problem asks for strictly greater, so equal values should not resolve the waiting element.
// Wrong: resolves on equal values
while (!stack.isEmpty() && price >= stack.peek())
// Correct: strictly greater
while (!stack.isEmpty() && price > stack.peek())
What are the edge cases?
- nums2 is strictly increasing: every element except the last has a next greater element.
- nums2 is strictly decreasing: no element has a next greater element; all map to -1.
- nums1 is empty: return an empty array.
- All elements equal: no element has a strictly greater successor.
What should a senior engineer know?
The monotonic stack pattern is a family of problems, not a single trick.
- Next Greater Element II (circular): process the array twice to simulate wrapping.
- Daily Temperatures: same pattern but record the index distance instead of the value.
- Stock Span: use a decreasing stack to find how many consecutive days the price was not higher.
- Largest Rectangle in Histogram: use an increasing stack to find boundaries.
Recognizing which flavor of monotonic stack (increasing vs decreasing, by value vs by index) to apply is the senior skill.
What are common interview follow-up questions?
- What if the array is circular? (Process it twice, using modulo indexing.)
- Can you solve it for the next smaller element? (Use an increasing stack instead.)
- How would you adapt this for a stream? (Maintain the stack and resolve as new elements arrive.)
Visual Overview
Prices: [1, 3, 4, 2]
Step 1: push 1 Stack: [1]
Step 2: 3 > 1 -> pop 1, map[1]=3. Push 3. Stack: [3]
Step 3: 4 > 3 -> pop 3, map[3]=4. Push 4. Stack: [4]
Step 4: 2 < 4 -> push 2. Stack: [4, 2]
End: pop 4 -> map[4]=-1. pop 2 -> map[2]=-1.
Map: {1:3, 3:4, 4:-1, 2:-1}
Watchlist lookup: 4 -> -1, 1 -> 3, 2 -> -1
┌──────────────────────────────────────────────┐ │ Monotonic Stack Resolution Flow │ ├──────────────────────────────────────────────┤ │ │ │ For each value in nums2: │ │ │ │ │ ▼ │ │ ┌──────────────────────────────┐ │ │ │ While stack top < current: │ │ │ │ pop top │ │ │ │ map[top] = current │ resolve │ │ └──────────────────────────────┘ │ │ │ │ │ ▼ │ │ Push current onto stack │ │ │ │ After all values: │ │ Remaining stack items -> map to -1 │ │ │ │ For each query in nums1: │ │ result[i] = map.getOrDefault(q, -1) │ └──────────────────────────────────────────────┘
Key Takeaway
Next Greater Element is the canonical monotonic stack problem. The brute force compares each element with everything to its right, but a decreasing monotonic stack resolves answers as you go in a single linear pass.
You scan the full array once and keep a stack of values waiting for their next greater element. When the current value exceeds the stack top, the current value is the answer for that top, so you pop and record the mapping. You repeat until the top is no longer smaller, then push the current value as a new pending element. Anything on the stack at the end maps to -1.
The answers go into a HashMap so that queries from the watchlist are constant-time lookups. The total complexity is O(n + m), and the signature property is that each element is pushed once and popped at most once.
At the National Bank of India, Rajesh used this on the trading desk. For each stock on a trader's watchlist, he needed the next trading day whose price first exceeded the current day's price. One pass over the full price series built the complete answer map, and the watchlist lookups were instant.
Remember one sentence: a decreasing monotonic stack resolves pending values the moment a larger value arrives, and a HashMap stores the answers for instant query lookup.
---