Next Greater Element I
Last Updated: March 29, 2026
Understanding the Problem
We have two arrays. nums1 is a subset of nums2, meaning every element in nums1 exists somewhere in nums2. For each element in nums1, we need to find it in nums2, then look to the right in nums2 for the first element that's larger. If nothing larger exists to the right, we return -1.
The important thing to notice is that we're not looking for the next greater element in nums1. We're finding each element's position in nums2 and then scanning right within nums2. So the problem really boils down to: "For every element in nums2, what's its next greater element?" Once we have that mapping, answering queries from nums1 is just a lookup.
Key Constraints:
1 <= nums1.length <= nums2.length <= 1000→ With n up to 1000, even O(n^2) is only 1 million operations, which is very fast. But O(n) is achievable and worth learning since it introduces the monotonic stack pattern.All integers in nums1 and nums2 are unique.→ No duplicates. This is critical because it means we can use a hash map to map values to their next greater element without worrying about collisions.nums1 is a subset of nums2→ Every query innums1is guaranteed to exist innums2. No need for "not found" handling when locating elements.
Approach 1: Brute Force
Intuition
The most direct approach is to 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, return -1.
Since all elements are unique, finding an element in nums2 is straightforward. And with n up to 1000, scanning to the right for each query is cheap.
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 re-scanning nums2 from scratch for each query, even though the "next greater element" relationship is a property of nums2 alone.
What if we precomputed the next greater element for every value in nums2 in a single pass, and then just looked up the answers?
Approach 2: Monotonic Stack + Hash Map
Intuition
Here's the key insight: the "next greater element" relationship is entirely determined by nums2. It has nothing to do with nums1. So we can precompute a mapping of "element -> its next greater element in nums2" for every element in nums2, and then answering queries from nums1 becomes a simple hash map lookup.
The question is: how do we efficiently compute the next greater element for every element in nums2? This is the classic monotonic stack problem.
Think about it this way. Imagine you're walking through nums2 from left to right. You maintain a stack of elements that haven't found their "next greater" yet. These elements are in decreasing order on the stack (that's the monotonic property). When you encounter a new element that's larger than the top of the stack, you've found the answer for that stack top. You pop it, record the mapping, and check the new top. You keep popping until the stack is empty or the top is no longer smaller than the current element. Then you push the current element onto the stack.
After processing all of nums2, any elements still on the stack never found a greater element to their right, so their answer is -1.
The monotonic stack maintains a decreasing sequence of elements that haven't yet found their next greater element. When a new element comes along that's larger than the stack top, it must be the next greater element for that top because nothing between them was larger (if something was, the top would have been popped already).
This is an elegant example of amortized analysis. Each element is pushed onto the stack exactly once and popped at most once. So even though there's a while loop inside the for loop, the total number of push and pop operations across all iterations is at most 2n, giving us O(n) time.
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.