Domain 1EasyCORE

Next Greater Element I

The problem requires finding the next greater element for each number in `nums1` within the context of `nums2`. Here are the key points:

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Stack

496. Next Greater Element I

Model: qwen2.5-coder:14b
Topics: Stack
FAANG asked: 1
Acceptance rate: 65.9%


Problem Breakdown

The problem requires finding the next greater element for each number in nums1 within the context of nums2. Here are the key points:

  • Inputs: Two arrays, nums1 and nums2, where nums1 is a subset of nums2.
  • Outputs: An array of integers representing the next greater elements for each element in nums1.
  • Constraints:
    • All elements in both arrays are unique.
    • The length of nums1 is less than or equal to the length of nums2.
    • Each number in nums1 appears in nums2.

Intuition

A brute-force approach would involve iterating over each element in nums1 and then searching for its next greater element in nums2. This would result in a time complexity of O(n^2), which is inefficient given the constraints.

The key insight to improve this is to use a stack to keep track of elements for which we haven’t yet found the next greater element. As we iterate through nums2, we can efficiently determine and store the next greater elements using this stack approach.

Approach

  1. Initialize Data Structures:

    • Use a dictionary next_greater to map each number in nums2 to its next greater element.
    • Use a stack to keep track of numbers for which we haven’t found the next greater element yet.
  2. Iterate through nums2:

    • For each number, pop elements from the stack while the current number is greater than the top of the stack. This indicates that the current number is the next greater element for those popped numbers.
    • Push the current number onto the stack.
  3. Handle Remaining Elements in Stack:

    • After processing all numbers in nums2, any remaining elements in the stack do not have a next greater element, so map them to -1 in the next_greater dictionary.
  4. Construct Result for nums1:

    • For each number in nums1, use the next_greater dictionary to find its corresponding next greater element.

Complexity Analysis

  • Time Complexity: O(nums1.length + nums2.length)

    • We iterate through nums2 once, and each element is pushed and popped from the stack at most once.
    • Constructing the result for nums1 takes linear time relative to its length.
  • Space Complexity: O(nums2.length)

    • The dictionary next_greater can store up to all elements of nums2.
    • The stack can also hold up to all elements of nums2.

Solution

def nextGreaterElement(nums1, nums2):
    # Dictionary to store the next greater element for each number in nums2
    next_greater = {}
    # Stack to keep track of numbers for which we haven't found the next greater element yet
    stack = []
    
    # Iterate through nums2
    for num in nums2:
        # While stack is not empty and current number is greater than the top of the stack
        while stack and num > stack[-1]:
            # The current number is the next greater element for the top of the stack
            next_greater[stack.pop()] = num
        # Push the current number onto the stack
        stack.append(num)
    
    # For remaining elements in the stack, there is no next greater element
    while stack:
        next_greater[stack.pop()] = -1
    
    # Construct the result for nums1 using the next_greater dictionary
    return [next_greater[num] for num in nums1]

Edge Cases Handled

  • Empty nums1: The function will return an empty list since there are no elements to process.
  • All elements in nums2 have a next greater element: The stack will be emptied completely, and all entries in next_greater will have valid values.
  • No elements in nums2 have a next greater element: All remaining elements in the stack will map to -1.
  • nums1 contains elements not present in nums2: This scenario is impossible given the problem constraints, but if it were possible, the function would handle it gracefully by returning -1 for those elements.