Skip to main content
DSA patterns

Next Greater Element I

easyStack and queue Must-doAmazonCiscoTCS

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

Hint 1: For a single array, the next greater element of *every* position can be found in one left-to-right pass using a stack that only ever holds values still waiting for something bigger to show up.

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

  1. Create an empty stack (values from nums2 still waiting for their next greater element) and an empty map from value to its next greater element.
  2. Walk through nums2 left to right. For each value x:
    1. While the stack isn't empty and its top is less than x: pop the top and record next_greater[popped] = x.
    2. Push x onto the stack.
  3. 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.
  4. For each value in nums1, look it up in the map: the answer is the mapped value, or -1 if 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 nums2 from scratch for every nums1 query costs O(n·m) — build the next-greater map once, up front, instead of per-query

Interview follow-ups

  • What if nums1 could contain values that aren't in nums2 at all?

    The map lookup already handles this gracefully — a value that was never seen while walking nums2 was never pushed onto the stack or recorded in the map, so looking it up with a default of -1 (Python's dict.get, Java's getOrDefault) 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 % n for i from 0 up to 2n - 1, while still only ever pushing and popping indices 0 through n - 1 onto 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.