DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Next Greater Element I

easyStack and queue

Problem statement

You get two arrays of distinct integers, nums1 and nums2, where every value in nums1 also appears somewhere in nums2.

For each value x in nums1, find where x sits in nums2, then look to the right of that spot for the first value that is strictly larger than x. That value is the next greater element of x. If nothing to the right is larger, the answer for x is -1.

Return an array with one answer per value of nums1, in the same order as nums1.

Examples

Example 1

Input: nums1 = [3, 1, 6] nums2 = [5, 3, 6, 1, 7]

Output: [6, 7, 7]

Explanation: Right of 3 the first bigger value is 6. Right of 1 there is only 7. Right of 6 the values are 1 and 7, so 7.

Example 2

Input: nums1 = [8, 2] nums2 = [2, 9, 8]

Output: [-1, 9]

Explanation: 8 is the last value in nums2, so nothing is to its right. The first value after 2 is 9, which is bigger.

Hints

Approach

Precompute the next greater element for every value in nums2 with a monotonic stack, then answer each query from a dictionary.

  1. Keep a stack of values that are still waiting for something bigger. Because a value is popped as soon as something bigger arrives, the stack is always decreasing from bottom to top.
  2. For each value y in nums2: while the top of the stack is smaller than y, pop it and record y as its next greater element. Then push y.
  3. Anything left on the stack at the end has no bigger value to its right.
  4. For each x in nums1, look up its answer, defaulting to -1.

Every value is pushed once and popped at most once, so the whole pass is linear.

ComplexityTime O(m + n)Space O(n)
Python
class Solution:
def nextGreaterElement(self, nums1: list[int], nums2: list[int]) -> list[int]:
next_greater = {} # value -> first bigger value to its right
stack = [] # values still waiting for a bigger one (decreasing)
for y in nums2:
while stack and stack[-1] < y:
next_greater[stack.pop()] = y
stack.append(y)
return [next_greater.get(x, -1) for x in nums1]

Follow-up questions

  • Treat nums2 as circular, so the search can wrap around to the start (Next Greater Element II).
  • Return the distance to the next greater element instead of its value.

Frequently asked questions

A value only stays on the stack while nothing to its right has been bigger. The moment a bigger value arrives it pops every smaller value, so whatever remains underneath is larger than whatever sits on top.

So a value maps to exactly one position in nums2, and a dictionary keyed by value is enough. With duplicates you would key the dictionary by index instead of value.

Any "when is the next time the metric goes above this point?" question over a time series, such as finding the next sample where disk usage or latency exceeds the current reading. The same stack also powers Daily Temperatures.