Next Greater Element I
Asked at Flipkart
Problem
Next Greater Element I gives you nums1, a subset of nums2, and asks, for each value in nums1, for the first larger value to its right in nums2 (or -1). It is the gateway problem for the monotonic stack pattern.
Asked At
| Company | Difficulty | |
|---|---|---|
| Flipkart | Easy | View all Flipkart questions → |
How to Think About It
Brute force: for each value in nums1, find it in nums2 and scan right for a larger number. That is O(m * n).
Key insight: compute the next greater element for every value of nums2 once, store it in a hash map, then answer nums1 with lookups.
Use a monotonic decreasing stack while scanning nums2. When the current number is larger than the top of the stack, it is the next greater element for that top — pop and record. Then push the current number.
Walkthrough on nums2 = [1,3,4,2]: push 1; 3 > 1 -> next[1] = 3, push 3; 4 > 3 -> next[3] = 4, push 4; 2 < 4, push 2. Leftovers 4 and 2 get -1.
All values are distinct, so a value-keyed map is safe.
Optimal Approach
Step 1: nxt = {}, stack = [].
Step 2: For each x in nums2:
While stack and stack[-1] < x: nxt[stack.pop()] = x.
Push x.
Step 3: Return [nxt.get(v, -1) for v in nums1].
Each element of nums2 is pushed and popped at most once.
Time: O(m + n). Space: O(n).
What Trips People Up in Real Interviews
Searching nums2 for each nums1 value. It works but is quadratic; precompute with the stack instead.
Using an increasing stack. You need a decreasing stack so that a larger value can resolve every smaller value waiting on it.
Forgetting that unresolved values get -1.
Confusing "next greater" (first larger to the right) with "maximum to the right".
Solution Code
def nextGreaterElement(nums1, nums2):
nxt = {}
stack = []
for x in nums2:
while stack and stack[-1] < x:
nxt[stack.pop()] = x
stack.append(x)
return [nxt.get(v, -1) for v in nums1]Frequently Asked Questions
What is the Next Greater Element I problem?
Next Greater Element I gives you `nums1`, a subset of `nums2`, and asks, for each value in `nums1`, for the first larger value to its right in `nums2` (or `-1`). It is the gateway problem for the monotonic stack pattern.
How do you solve Next Greater Element I?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Next Greater Element I?
Next Greater Element I is asked at Flipkart. It is a easy difficulty problem.
What are common mistakes on Next Greater Element I?
- Searching `nums2` for each `nums1` value. It works but is quadratic; precompute with the stack instead.
- Using an increasing stack. You need a decreasing stack so that a larger value can resolve every smaller value waiting on it.
- Forgetting that unresolved values get `-1`.
- Confusing "next greater" (first larger to the right) with "maximum to the right".