Next Greater Element I
Problem statement
The next greater element of a value x in an array is the first value
to its right that's bigger than x. Think of it as scanning a time series
of metric readings for the next reading that's higher than the current one.
You're given two arrays of distinct integers, nums1 and nums2, where
every value in nums1 also appears somewhere in nums2. For each value in
nums1, find where it sits in nums2 and report its next greater element
there — or -1 if nothing to its right in nums2 is bigger. Return the
answers in the same order as nums1.
Examples
Example 1
Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1,3,-1]
Explanation: 4 sits at the end of [3, 4, 2]'s "4" position in nums2 — nothing after it (just 2) is bigger, so -1. 1 sits at the start of nums2; the next value bigger than 1 is 3. 2 is the last element of nums2, so there's nothing to its right at all, hence -1.
Example 2
Input: nums1 = [2,4], nums2 = [1,2,3,4]
Output: [3,-1]
Explanation: 2 is followed by 3, which is bigger, so its answer is 3. 4 is the last element of nums2, so nothing follows it — the answer is -1.
Hints
Approach
Optimal: Monotonic stack
Intuition
Answer the bigger question once, instead of the small question n times:
"what's the next greater element for every value in nums2?" Walk
nums2 left to right, keeping a stack of values still "waiting" for
something bigger to appear. Whenever the current value is bigger than the
stack's top, the top value has just found its answer — record it and pop,
and keep popping, since the current value might answer several waiting
values in a row. Then push the current value itself, since it's now
waiting for its own answer. Anything left on the stack once the walk
finishes never found a bigger value, so it maps to -1. Each nums1 query
then becomes a plain lookup into that map.
Steps
- Create an empty stack (values from
nums2still waiting for their next greater element) and an empty map from value to its next greater element. - Walk through
nums2left to right. For each valuex:- While the stack isn't empty and its top is less than
x: pop the top and recordnext_greater[popped] = x. - Push
xonto the stack.
- While the stack isn't empty and its top is less than
- Once the walk finishes, anything still on the stack never found a bigger
value — leave it out of the map, so a lookup for it defaults to
-1. - For each value in
nums1, look it up in the map: the answer is the mapped value, or-1if it isn't there.
Dry run
nums2 = [1, 3, 4, 2], stack starts empty:
| x | while: pop while top < x | push | stack after |
|---|---|---|---|
| 1 | (empty, nothing to pop) | push 1 | [1] |
| 3 | pop 1 → next_greater[1] = 3 | push 3 | [3] |
| 4 | pop 3 → next_greater[3] = 4 | push 4 | [4] |
| 2 | top is 4, 4 < 2? no | push 2 | [4, 2] |
Final map: {1: 3, 3: 4}. 4 and 2 are left on the stack, so they're
not in the map at all.
For nums1 = [4, 1, 2]: 4 → not in map → -1; 1 → 3; 2 → not in
map → -1. Result: [-1, 3, -1], matching Example 1.
Edge cases: a strictly decreasing nums2 (like [5, 4, 3, 2, 1]) never
pops anything — the map stays empty, and every nums1 value gets -1. A
strictly increasing nums2 pops immediately at every step, so every value
except the very last one gets an answer right away.
Complexity
Time O(n + m) - one pass through `nums2` (each value pushed and popped from the stack at most once), plus one pass through `nums1` for lookups.
Space O(m) - for the map and stack.
from typing import List
class Solution:
def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
next_greater = {}
stack = []
for x in nums2:
while stack and stack[-1] < x:
next_greater[stack.pop()] = x
stack.append(x)
return [next_greater.get(target, -1) for target in nums1]
if __name__ == "__main__":
print(Solution().nextGreaterElement([4, 1, 2], [1, 3, 4, 2])) # [-1, 3, -1]
print(Solution().nextGreaterElement([2, 4], [1, 2, 3, 4])) # [3, -1]RecapThe whole problem in a few lines, for the night before
- Spot it: "for every element, find the first bigger element somewhere to its right" — the classic monotonic-stack shape
- Idea: sweep the source array once with a decreasing stack; when a bigger value arrives, it's the answer for everything still waiting on the stack
- Cost: O(n + m) time, O(m) space for the map and stack (n = len(nums1), m = len(nums2))
- Trap: re-scanning
nums2from scratch for everynums1query costs O(n·m) — build the next-greater map once, up front, instead of per-query
Interview follow-ups
What if
nums1could contain values that aren't innums2at all?The map lookup already handles this gracefully — a value that was never seen while walking
nums2was never pushed onto the stack or recorded in the map, so looking it up with a default of-1(Python'sdict.get, Java'sgetOrDefault) just falls through correctly without any extra code.How would this change for a circular array, where "to the right" wraps back around to the start (Next Greater Element II)?
Walk the array twice conceptually — once so every element also gets a chance to see values that wrap around to its left — by iterating index
i % nforifrom0up to2n - 1, while still only ever pushing and popping indices0throughn - 1onto the stack. The monotonic-stack mechanics themselves don't change at all; only the range being iterated does.
Frequently asked questions
Because the only thing ever pushed is the current value, and by the time it goes on, every smaller value that used to sit above where it lands has already been popped off. Anything still below it in the stack is therefore guaranteed to be bigger — that invariant is exactly what "monotonic decreasing stack" means.
Because every value is pushed onto the stack exactly once and popped at most once across the entire walk through nums2, no matter how the pops are distributed across iterations. The total number of pushes plus pops is at most 2·m, so the work adds up to O(m), not O(m²).
Scanning a metrics time series or a resource-usage log for "the next reading that's higher than this one" — the first spike after a given point — is exactly this pattern, and it comes up whenever a system needs to react to the next threshold breach instead of re-scanning the whole series every time.
Because nums1 is answered one value at a time, but the monotonic-stack sweep processes nums2 exactly once no matter how many queries there are. Computing every answer up front turns each individual nums1 lookup into O(1), which pays for itself the moment there's more than a single query.