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,
nums1andnums2, wherenums1is a subset ofnums2. - 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
nums1is less than or equal to the length ofnums2. - Each number in
nums1appears innums2.
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
-
Initialize Data Structures:
- Use a dictionary
next_greaterto map each number innums2to its next greater element. - Use a stack to keep track of numbers for which we haven’t found the next greater element yet.
- Use a dictionary
-
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.
-
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-1in thenext_greaterdictionary.
- After processing all numbers in
-
Construct Result for
nums1:- For each number in
nums1, use thenext_greaterdictionary to find its corresponding next greater element.
- For each number in
Complexity Analysis
-
Time Complexity: O(nums1.length + nums2.length)
- We iterate through
nums2once, and each element is pushed and popped from the stack at most once. - Constructing the result for
nums1takes linear time relative to its length.
- We iterate through
-
Space Complexity: O(nums2.length)
- The dictionary
next_greatercan store up to all elements ofnums2. - The stack can also hold up to all elements of
nums2.
- The dictionary
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
nums2have a next greater element: The stack will be emptied completely, and all entries innext_greaterwill have valid values. - No elements in
nums2have a next greater element: All remaining elements in the stack will map to-1. nums1contains elements not present innums2: This scenario is impossible given the problem constraints, but if it were possible, the function would handle it gracefully by returning-1for those elements.