Next Greater Element I: First Larger Value to the Right

Problem

You have two lists of distinct integers, queries and nums, where every value in queries also appears in nums. For each query value q, find where q sits in nums and return the first value to its right that is larger than q, or -1 if there is none. This is widely known as LeetCode 496, Next Greater Element I.

Examples

queries = [6, 2, 9],  nums = [2, 7, 6, 9, 1]   ->  [9, 7, -1]
queries = [3],        nums = [3]               ->  [-1]
queries = [],         nums = [1, 2]            ->  []

Approach 1: brute force

For each query, locate it and scan to the right.

def next_greater_brute(queries, nums):
    out = []
    for q in queries:
        i = nums.index(q)
        ans = -1
        for v in nums[i + 1:]:
            if v > q:
                ans = v
                break
        out.append(ans)
    return out

Complexity: O(m · n) time for m queries and n values, O(1) extra space besides the output.

Approach 2: optimal

Key insight: compute the answer for every value of nums at once with a decreasing stack, then look the queries up. A value waits on the stack until a larger value arrives; the first larger value to arrive is its answer.

Walkthrough on nums = [2, 7, 6, 9, 1]:

Value	Popped (answer)	Stack after
2		2
7	2 → 7	7
6		7 6
9	6 → 9, 7 → 9	9
1		9 1

Map: {2: 7, 6: 9, 7: 9}; 9 and 1 have no answer. Queries [6, 2, 9] give [9, 7, -1].

def next_greater_element(queries, nums):
    greater = {}
    stack = []
    for v in nums:
        while stack and stack[-1] < v:
            greater[stack.pop()] = v
        stack.append(v)
    return [greater.get(q, -1) for q in queries]

Complexity: O(n + m) time, O(n) space for the stack and dictionary.

Tests

import random

for f in (next_greater_element, next_greater_brute):
    assert f([6, 2, 9], [2, 7, 6, 9, 1]) == [9, 7, -1]
    assert f([3], [3]) == [-1]                          # single element
    assert f([], [1, 2]) == []                          # no queries
    assert f([1, 2, 3], [1, 2, 3]) == [2, 3, -1]        # increasing
    assert f([-9, -5], [-5, -9, -3]) == [-3, -3] and f([-3], [-5, -9, -3]) == [-1]   # negatives
    assert f([-9, -5], [-5, -9, -1]) == [-1, -1] and f([-5], [-5, -9, -2]) == [-2]   # negatives
    assert f([0], [0, 10**9]) == [10**9]                # large values

random.seed(39)
for _ in range(400):
    nums = random.sample(range(-10, 11), random.randint(1, 10))
    queries = random.sample(nums, random.randint(0, len(nums)))
    assert next_greater_element(queries, nums) == next_greater_brute(queries, nums)

Edge cases and pitfalls

• The dictionary keys are values, which only works because the values are distinct. With duplicates, key the answers by index instead (as in Daily Temperatures).
• Default missing entries to -1 with get; values still on the stack at the end have no greater element.
• For a circular array, iterate over the array twice (indices 0..2n-1 modulo n) and only push during the first pass.

Where this shows up in data engineering

“The next event with a higher value” over an ordered series, such as the next trade above a given price or the next reading above the current one, is this lookup. In SQL it needs a correlated subquery or a self-join; the stack does it in one ordered pass, which is how you would implement it in a Python or Spark mapPartitions step over sorted data.