Next Greater Element I
Understanding the Problem
We have two arrays. nums1 is a subset of nums2, so every element in nums1 exists somewhere in nums2. For each element in nums1, we find it in nums2, then look to the right in nums2 for the first element that is larger. If nothing larger exists to the right, the answer is -1.
We are not looking for the next greater element within nums1. We find each element's position in nums2 and scan right within nums2. The problem reduces to: for every element in nums2, what is its next greater element? Once we have that mapping, answering queries from nums1 is a lookup.
Key Constraints:
1 <= nums1.length <= nums2.length <= 1000→ With n up to 1000, an O(m*n) scan is at most a million operations, fast enough to pass. The O(n) monotonic stack solution is the more useful one to know.All integers in nums1 and nums2 are unique.→ No duplicates means we can map each value to its next greater element in a hash map without worrying about two elements colliding on the same key.nums1 is a subset of nums2→ Every value innums1exists innums2, so locating an element never fails.
Approach 1: Brute Force
Intuition
Do exactly what the problem describes. For each element in nums1, find where it sits in nums2, then scan to the right in nums2 until we find something bigger. If we reach the end without finding anything, the answer is -1.
Because all elements are unique, locating an element in nums2 is a single linear scan, and with n up to 1000 the repeated scanning stays within budget.
Algorithm
- Create a result array of the same length as
nums1. - For each element
nums1[i]: - Find the index
jinnums2wherenums2[j] == nums1[i]. - From index
j + 1to the end ofnums2, look for the first element greater thannums1[i]. - If found, store that element in the result. Otherwise, store -1.
- Return the result array.
Example Walkthrough
Code
- Time Complexity: O(m * n). For each of the m elements in
nums1, we scan throughnums2(length n) to find it and then scan further to find the next greater element. - Space Complexity: O(1). We only use the result array and a few variables. The result array is required for output and doesn't count as extra space.
The bottleneck is that we re-scan nums2 from scratch for each query, even though the next greater element relationship is a property of nums2 alone. The next approach precomputes that relationship for every value in nums2 in a single pass, then answers each query with a lookup.
Approach 2: Monotonic Stack + Hash Map
Intuition
The next greater element relationship is determined by nums2 alone. So we precompute a mapping from each element of nums2 to its next greater element, then answer every query from nums1 with a hash map lookup. Computing the next greater element for every element in one pass is the monotonic stack pattern.
Process nums2 from left to right, keeping a stack of elements that have not yet found their next greater element. These elements stay in decreasing order on the stack: any element pushed on top of another is smaller than it, otherwise the one below would have been popped first. When the current element is larger than the stack top, the current element is the next greater element for that top. Pop it, record the mapping, and compare against the new top. Keep popping while the top is smaller than the current element, then push the current element.
After the whole array is processed, any elements left on the stack never found a larger element to their right, so their answer is -1.
When the current element is larger than the stack top, it is the next greater element for that top. Every element between them in the array was smaller than the top, otherwise the top would have already been popped when that larger element was processed. So the current element is the first value to the right that exceeds the top.
The runtime is O(n) by amortized analysis. Each element is pushed exactly once and popped at most once, so across all iterations the while loop runs at most n times in total, even though it is nested inside the for loop.
Algorithm
- Create an empty stack and an empty hash map.
- Iterate through
nums2from left to right: - While the stack is not empty and the current element is greater than the top of the stack:
- Pop the top element.
- Record in the hash map: popped element -> current element (this is its next greater element).
- Push the current element onto the stack.
- Any elements remaining on the stack have no next greater element (they map to -1 by default).
- For each element in
nums1, look up its next greater element in the hash map. If it's not in the map, the answer is -1. - Return the result array.
Example Walkthrough
Code
- Time Complexity: O(m + n). We iterate through
nums2(length n) once. Each element is pushed and popped from the stack at most once, so the stack operations are O(n) total. Then we iterate throughnums1(length m) for lookups, each O(1) with the hash map. - Space Complexity: O(n). The hash map stores at most n entries (one per element in
nums2). The stack holds at most n elements at any point.