LeetCode Solutions Blog

Next Greater Element I

Number: 496

Difficulty: Easy

Paid? No

Problem Description

Given two distinct 0-indexed integer arrays, nums1 (a subset of nums2) and nums2, for each element in nums1, find the first greater element to its right in nums2. If it does not exist, return -1 for that element.

Key Insights

Use a monotonic decreasing stack to precompute the next greater element for every number in nums2.
Use a hash map to store the mapping from element to its next greater element.
For each element in nums1, look up the next greater element from the hash map.
This approach avoids a nested loop by processing nums2 only once.

Space and Time Complexity

Time Complexity: O(n) where n is the length of nums2 (plus O(m) for nums1, overall O(n + m)). Space Complexity: O(n) for the stack and hash map.

Solution

We iterate through nums2 once while maintaining a stack that keeps numbers in decreasing order. When a new number is encountered, it is the next greater element for all numbers in the stack that are smaller than it. These elements are popped from the stack and the mapping is recorded in a hash map. Afterwards, for each element in nums1, we simply fetch the answer from the hash map. This ensures an optimal O(n + m) solution.

Code Solutions

# Python solution for Next Greater Element I

def nextGreaterElement(nums1, nums2):
    # Create a dictionary to hold the next greater element for each number in nums2
    next_greater = {}
    # Initialize an empty stack to keep track of numbers for which we haven't found the next greater element yet
    stack = []
    
    # Iterate over every number in nums2
    for num in nums2:
        # While the current number is greater than the last number in stack,
        # it is the next greater element for that number.
        while stack and num > stack[-1]:
            previous_num = stack.pop()
            next_greater[previous_num] = num
        # Push the current number onto the stack
        stack.append(num)
    
    # For numbers left in the stack, no next greater element exists so assign -1
    while stack:
        previous_num = stack.pop()
        next_greater[previous_num] = -1

    # Build the result array for nums1 using the hash map
    return [next_greater[x] for x in nums1]

# Example usage
nums1 = [4,1,2]
nums2 = [1,3,4,2]
print(nextGreaterElement(nums1, nums2))