496. Next Greater Element I (Easy)

Problem

You are given two arrays nums1 and nums2, where nums1 is a subset of nums2. For each element in nums1, find the next greater element in nums2: the first element to its right (in nums2) that is strictly greater. Return -1 if no such element exists.

Examples

• nums1=[4,1,2], nums2=[1,3,4,2] → [-1,3,-1]
  • 4 has nothing greater to its right in nums2: -1
  • 1’s next greater in nums2 is 3
  • 2 has nothing greater to its right: -1
• nums1=[2,4], nums2=[1,2,3,4] → [3,-1]

LeetCode 496 · Link · Easy

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, nested scan

For each element in nums1, find its position in nums2, then scan right for the first greater element.

Python

def next_greater_element(nums1: list[int], nums2: list[int]) -> list[int]:
    result = []
    for x in nums1:                          # L1: m iterations (m = len(nums1))
        idx = nums2.index(x)                 # L2: O(n) linear search
        found = -1
        for j in range(idx + 1, len(nums2)): # L3: up to n steps
            if nums2[j] > x:                 # L4: O(1) compare
                found = nums2[j]
                break
        result.append(found)                 # L5: O(1)
    return result

TypeScript

function nextGreaterElement(nums1: number[], nums2: number[]): number[] {
    const result: number[] = [];
    for (const x of nums1) {                               // L1: m iterations
        const idx = nums2.indexOf(x);                      // L2: O(n) linear search
        let found = -1;
        for (let j = idx + 1; j < nums2.length; j++) {    // L3: up to n steps
            if (nums2[j] > x) { found = nums2[j]; break; } // L4: O(1) compare
        }
        result.push(found);                                // L5: O(1)
    }
    return result;
}

Swift

final class Solution {
    func nextGreaterElement(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
        nums1.map { value in
            guard let start = nums2.firstIndex(of: value) else { return -1 }
            for index in (start + 1)..<nums2.count where nums2[index] > value { return nums2[index] }
            return -1
        }
    }
}

Complexity

• Time: $O(m * n)$, m queries each requiring $O(n)$ to scan nums2.
• Space: $O(1)$ extra.

Approach 2: Monotonic stack precomputation (optimal)

The trick: answer all next-greater queries for nums2 in a single $O(n)$ pass, storing answers in a hash map. Then look up each nums1 element in $O(1)$.

Use a monotonic decreasing stack (values decrease from bottom to top). When a new element is larger than the stack top, the stack top has found its next-greater answer.

Python

def next_greater_element(nums1: list[int], nums2: list[int]) -> list[int]:
    nge = {}                                       # L1: O(1) hash map
    stack = []                                     # L2: O(1) monotonic stack (values)

    for num in nums2:                              # L3: n iterations
        while stack and stack[-1] < num:           # L4: pop elements answered by num
            nge[stack.pop()] = num                 # L5: O(1) amortized: record answer
        stack.append(num)                          # L6: O(1) push current

    for num in stack:                              # L7: remaining have no answer
        nge[num] = -1                              # L8: O(1) mark as -1

    return [nge[x] for x in nums1]                # L9: O(m) lookup

TypeScript

function nextGreaterElement(nums1: number[], nums2: number[]): number[] {
    const nge = new Map<number, number>();          // L1: O(1) hash map
    const stack: number[] = [];                     // L2: O(1) monotonic stack (values)

    for (const num of nums2) {                      // L3: n iterations
        while (stack.length && stack[stack.length - 1] < num)
            nge.set(stack.pop()!, num);             // L4-L5: O(1) amortized: record answer
        stack.push(num);                            // L6: O(1) push current
    }

    for (const num of stack) nge.set(num, -1);     // L7-L8: remaining have no answer

    return nums1.map(x => nge.get(x)!);            // L9: O(m) lookup
}

Swift

final class Solution {
    func nextGreaterElement(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
        var stack: [Int] = []
        var greater: [Int: Int] = [:]
        for value in nums2 {
            while let last = stack.last, value > last { greater[stack.removeLast()] = value }
            stack.append(value)
        }
        return nums1.map { greater[$0] ?? -1 }
    }
}

Where the time goes, line by line

Variables: n = len(nums2), m = len(nums1).

Line	Per-call cost	Times executed	Contribution
L3 (outer loop)	$O(1)$	n	$O(n)$
L4-L6 (stack ops)	$O(1)$ amortized	n total pushes/pops	$O(n)$ ← dominates
L7-L8 (mark remaining)	$O(1)$	at most n	$O(n)$
L9 (lookup)	$O(1)$ per element	m	$O(m)$

Each element of nums2 is pushed once and popped at most once. Total stack work is $O(n)$, not $O(n)$ per element.

Complexity

• Time: $O(m + n)$: $O(n)$ to build the map, $O(m)$ to answer queries.
• Space: $O(n)$ for the hash map and stack.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

How the monotonic stack resolves answers

nums2 = [1, 3, 4, 2]

Process 1: stack empty, push 1.       stack: [1]
Process 3: 3 > 1, pop 1, nge[1]=3.   stack: [], push 3.  stack: [3]
Process 4: 4 > 3, pop 3, nge[3]=4.   stack: [], push 4.  stack: [4]
Process 2: 2 < 4, push 2.            stack: [4, 2]

Remaining [4, 2]: nge[4]=-1, nge[2]=-1.

nums1=[4,1,2] -> [nge[4], nge[1], nge[2]] = [-1, 3, -1]

Key takeaways

• The monotonic stack solves all “next greater” queries for an array in $O(n)$ by letting elements announce themselves as answers when they finally exceed something waiting on the stack.
• Separating precomputation (stack over nums2) from querying (hash map lookup for nums1) is a clean pattern: build once, query many times.
• The stack stores values here (not indices) because nums1 queries are by value. For index-based problems like 503 or 739, store indices instead.
• Elements that are never popped (nothing greater to their right) get marked -1 in the cleanup loop.

Related topics

• Daily Temperatures, same monotonic stack pattern, index-based
• Next Greater Element II, circular variant
• Stacks, underlying data structure

Related concepts

• Monotonic Stack, the ordered stack pattern for nearest greater, nearest smaller, and spans.
• Hash Map Counting, the lookup table pattern for complements, frequencies, and seen items.