LeetCode 496 - Next Greater Element I

LeetCode Problem 496

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Stack, Monotonic Stack

Solution

Problem Understanding

The problem is asking us to find the next greater element for each element in nums1 within another array nums2. Formally, for each element in nums1, we need to locate its position in nums2 and then find the first element to its right in nums2 that is greater than itself. If no such element exists, we return -1 for that element.

The input arrays have the following characteristics: nums1 is a subset of nums2, both arrays contain distinct integers, and the lengths are moderate (1 <= nums1.length <= nums2.length <= 1000). This means that all elements in nums1 appear somewhere in nums2, so we do not need to handle missing elements. The constraints also imply that simple algorithms like O(n^2) are feasible for small inputs but inefficient for larger ones.

Key edge cases include when the element in nums1 is the largest element in nums2 (so the next greater element is -1), when the element is at the end of nums2, and when nums1 contains all elements of nums2 or only a single element.

Approaches

Brute Force Approach

The simplest approach is to iterate over each element of nums1, find its index in nums2, and then scan all elements to the right until we find a greater number. If no greater number is found, we assign -1. This approach works because it directly implements the problem's description, but it requires nested loops: one over nums1 and one over a potential slice of nums2. For large arrays, this can be inefficient, reaching O(n1 * n2) time complexity where n1 is the length of nums1 and n2 is the length of nums2.

Optimal Approach Using Monotonic Stack

The key observation for an efficient solution is that we can precompute the next greater element for every number in nums2 in one pass using a monotonic stack. The stack maintains a decreasing sequence of numbers from nums2. When a new number arrives that is greater than the top of the stack, we pop from the stack and record the current number as the next greater element of the popped number. This allows us to construct a mapping from each number in nums2 to its next greater element in O(n2) time. Once this mapping is ready, we can simply look up each number in nums1 in O(n1) time. This yields an overall O(n1 + n2) solution.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n1 * n2)	O(1)	Nested loops to search next greater element for each query
Optimal	O(n1 + n2)	O(n2)	Precompute next greater elements using monotonic stack and hashmap

Algorithm Walkthrough

1. Initialize an empty stack and an empty dictionary next_greater_map.
2. Iterate over each element num in nums2. For each number:

• While the stack is non-empty and the top of the stack is less than num, pop the top element and map it to num in next_greater_map. This means num is the next greater element for the popped number.
• Push num onto the stack. It may have its next greater element later.

3. After processing all elements of nums2, any remaining numbers in the stack do not have a next greater element, so they can remain unmapped, and we will default to -1.
4. Construct the result array for nums1 by looking up each element in next_greater_map. If a number is not in the map, append -1.

Why it works: The monotonic stack ensures that every number in nums2 is compared only to the numbers to its right, and it maintains a strictly decreasing sequence. By popping smaller numbers when a larger number is encountered, we correctly assign the next greater element for each number in linear time.

Python Solution

from typing import List

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        stack = []
        next_greater_map = {}
        
        for num in nums2:
            while stack and stack[-1] < num:
                smaller = stack.pop()
                next_greater_map[smaller] = num
            stack.append(num)
        
        # For remaining elements in stack, there is no next greater element
        result = [next_greater_map.get(num, -1) for num in nums1]
        return result

The code first builds a mapping of next greater elements for all numbers in nums2 using a monotonic stack. Each element is either pushed onto the stack or used to pop smaller elements. Finally, we construct the answer for nums1 using a dictionary lookup.

Go Solution

func nextGreaterElement(nums1 []int, nums2 []int) []int {
    stack := []int{}
    nextGreaterMap := make(map[int]int)
    
    for _, num := range nums2 {
        for len(stack) > 0 && stack[len(stack)-1] < num {
            smaller := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            nextGreaterMap[smaller] = num
        }
        stack = append(stack, num)
    }
    
    result := make([]int, len(nums1))
    for i, num := range nums1 {
        if val, exists := nextGreaterMap[num]; exists {
            result[i] = val
        } else {
            result[i] = -1
        }
    }
    return result
}

In Go, we use a slice as a stack and a map for the next greater elements. We handle lookups carefully with exists to differentiate unmapped elements, and we append the final results for nums1.

Worked Examples

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

Stack operations:

Iteration	Stack	Map Updates
1 (num=1)	[1]	{}
2 (num=3)	[]	{1:3}
3 (num=4)	[]	{1:3,3:4}
4 (num=2)	[4,2]	{}

Result for nums1: [next_greater_map.get(4,-1), next_greater_map.get(1,-1), next_greater_map.get(2,-1)] = [-1,3,-1]

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

Stack operations:

Iteration	Stack	Map Updates
1 (num=1)	[1]	{}
2 (num=2)	[]	{1:2}
3 (num=3)	[]	{1:2,2:3}
4 (num=4)	[]	{1:2,2:3,3:4}

Result for nums1: [3,-1]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n1 + n2)	Precomputing next greater elements in O(n2), then building result array in O(n1)
Space	O(n2)	Stack and map storage for all elements of nums2

The monotonic stack ensures that each element of nums2 is pushed and popped at most once, giving linear time. The additional space for the map is proportional to nums2.

Test Cases

# Provided examples
assert Solution().nextGreaterElement([4,1,2], [1,3,4,2]) == [-1,3,-1]  # Example 1
assert Solution().nextGreaterElement([2,4], [1,2,3,4]) == [3,-1]      # Example 2

# Single element nums1
assert Solution().nextGreaterElement([5], [5,6,7]) == [6]

# All elements in decreasing order
assert Solution().nextGreaterElement([4,3,2,1], [4,3,2,1]) == [-1,-1,-1,-1]

# nums1 equals nums2
assert Solution().nextGreaterElement([1,2,3], [1,2,3]) == [2,3,-1]

# Edge case: last element has no greater
assert Solution().nextGreaterElement([7], [1,3,7]) == [-1]

Test	Why
[4,1,2]	Checks mixed presence of next greater and -1
[2,4]	Checks last element returning -1
[5]	Single element edge case
[4,3,2,1]	All elements decreasing, no next greater
[1,2,3]	nums1 equals nums2, last element