LeetCode 496: Next Greater Element I

Problem Restatement

We are given two arrays:

Every value in both arrays is unique, and every value in nums1 appears in nums2.

For each value x in nums1, we need to find the first greater number appearing to the right of x inside nums2.

If no greater value exists, return -1 for that number.

Input and Output

Function shape:

def nextGreaterElement(
    nums1: list[int],
    nums2: list[int],
) -> list[int]:
    ...

Examples

Example 1:

nums1 = [4, 1, 2]
nums2 = [1, 3, 4, 2]

For 4:

No greater value exists to its right.

Answer for 4:

-1

For 1:

The first greater value to the right is 3.

Answer for 1:

3

For 2:

No greater value exists.

Answer for 2:

-1

Final result:

[-1, 3, -1]

Example 2:

nums1 = [2, 4]
nums2 = [1, 2, 3, 4]

For 2, the next greater value is 3.

For 4, no greater value exists.

Answer:

[3, -1]

First Thought: Scan to the Right

For every value in nums1:

1. Find its position in nums2.
2. Scan rightward until finding a larger number.

class Solution:
    def nextGreaterElement(
        self,
        nums1: list[int],
        nums2: list[int],
    ) -> list[int]:
        ans = []

        for x in nums1:
            idx = nums2.index(x)

            next_greater = -1

            for j in range(idx + 1, len(nums2)):
                if nums2[j] > x:
                    next_greater = nums2[j]
                    break

            ans.append(next_greater)

        return ans

This works, but repeated scanning is inefficient.

Problem With Brute Force

For each query number, we may scan most of nums2.

If:

len(nums1) = m
len(nums2) = n

then the worst-case time complexity is:

O(m * n)

We can preprocess nums2 once so every query becomes fast.

Key Insight

We need the next greater element to the right.

This is a classic monotonic stack problem.

Process nums2 from left to right.

Maintain a stack that is strictly decreasing.

For example:

stack top is the most recent unresolved smaller number

When we see a new number num:

So while:

stack[-1] < num

we pop from the stack and record:

next_greater[popped] = num

At the end, remaining stack values have no greater element, so they map to -1.

Example Walkthrough

Consider:

nums2 = [1, 3, 4, 2]

Step 1

Current value:

1

Stack:

[1]

Step 2

Current value:

3

Since:

3 > 1

we pop 1 and record:

1 -> 3

Stack becomes:

[3]

Step 3

Current value:

4

Since:

4 > 3

record:

3 -> 4

Stack becomes:

[4]

Step 4

Current value:

2

Since:

2 < 4

push it.

Final unresolved stack:

[4, 2]

These values have no next greater element.

Algorithm

1. Create:
   • a decreasing stack
   • a hash map next_greater
2. Scan nums2.
3. While the current number is greater than the stack top:
   • pop the stack
   • record the current number as its next greater value
4. Push the current number.
5. Build the final answer for nums1 using the map.
6. Missing values return -1.

Correctness

The stack is maintained in strictly decreasing order.

When processing a value num, every smaller value on top of the stack cannot find a closer greater element than num, because:

1. They were pushed earlier.
2. All values between them and num were smaller than or equal to them, otherwise they would already have been popped.

Therefore, when num pops a value x, num is exactly the first greater value to the right of x.

Every value is pushed once and popped at most once. So every value either:

Thus the map correctly stores the next greater element for every number in nums2.

Finally, since every number in nums1 appears in nums2, looking up the map gives the correct answer for each query.

Complexity

Here:

Implementation

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

        for num in nums2:
            while stack and stack[-1] < num:
                smaller = stack.pop()
                next_greater[smaller] = num

            stack.append(num)

        return [
            next_greater.get(num, -1)
            for num in nums1
        ]

Code Explanation

The stack stores unresolved values:

stack = []

The hash map stores answers:

next_greater = {}

As we scan nums2:

for num in nums2:

we resolve all smaller stack values:

while stack and stack[-1] < num:

The current number becomes their next greater value:

smaller = stack.pop()
next_greater[smaller] = num

Then the current number waits for its own next greater value:

stack.append(num)

Finally, build answers for nums1:

return [
    next_greater.get(num, -1)
    for num in nums1
]

If a number was never resolved, its answer is -1.

Testing

def run_tests():
    s = Solution()

    assert s.nextGreaterElement(
        [4, 1, 2],
        [1, 3, 4, 2],
    ) == [-1, 3, -1]

    assert s.nextGreaterElement(
        [2, 4],
        [1, 2, 3, 4],
    ) == [3, -1]

    assert s.nextGreaterElement(
        [1],
        [1],
    ) == [-1]

    assert s.nextGreaterElement(
        [1, 3],
        [3, 1, 4],
    ) == [4, 4]

    assert s.nextGreaterElement(
        [2],
        [2, 1, 3],
    ) == [3]

    print("all tests passed")

run_tests()

Test meaning: