Next Greater Element I: Monotonic stack Pattern

Learning Outcome

After this lesson, you should be able to precompute next greater relationships and answer subset queries quickly.

Problem Statement

Given two arrays nums1 and nums2, where nums1 is a subset of nums2, return the next greater element in nums2 for every value in nums1. If no greater value exists, return -1.

Brute Force Approach

For each value in nums1, find it in nums2, then scan right until a greater value appears.

This repeats scans and can cost O(n * m).

Optimized Approach

Scan nums2 once with a decreasing stack. When the current value is greater than the stack top, it becomes the next greater value for that popped number. Store this relationship in a map.

Exact Pseudocode

nextGreater = empty map
stack = empty stack of values
for value in nums2:
  while stack is not empty and value > stack.top:
    smaller = pop stack
    nextGreater[smaller] = value
  push value
for each remaining value in stack:
  nextGreater[value] = -1
answer = []
for value in nums1:
  answer.add(nextGreater[value])
return answer
  

Reference Code

class Solution:
    def nextGreaterElement(self, nums1, nums2):
        next_greater = {}
        stack = []

        for value in nums2:
            while stack and value > stack[-1]:
                next_greater[stack.pop()] = value
            stack.append(value)

        while stack:
            next_greater[stack.pop()] = -1

        return [next_greater[value] for value in nums1]
  

Sample Dry Run

Complexity

Edge Cases

• No greater value exists for some numbers.
• nums1 has one value.
• Values are distinct in the classic problem.

Interview Checklist

• Precompute using nums2, then answer nums1.
• Use a decreasing stack.
• Assign -1 to unresolved values.

FAQs