Next Greater Element I
Easy · Stack & Strings · Array · Hash Table · Stack · Monotonic Stack
Problem
For a value x in an array, its next greater element is the first value to the right of x that is strictly larger than x.
You are given two arrays of distinct integers, nums1 and nums2, where every value of nums1 also appears in nums2. For each nums1[i], find where it sits in nums2 and take its next greater element there, or -1 if none exists.
Return an array ans of length len(nums1) where ans[i] is the answer for nums1[i]. Aim for O(len(nums1) + len(nums2)) time.
Examples
Input: nums1 = [3,8,5], nums2 = [5,3,8,6,9] Output: [8,9,8]
In nums2, 3 is followed by 8, 8 by 9 (6 is smaller), and 5 by 8 (3 is smaller).
Input: nums1 = [7,2], nums2 = [2,7] Output: [-1,7]
Nothing follows 7, while 2 is followed by the larger 7.
Input: nums1 = [2,4], nums2 = [1,2,3,4] Output: [3,-1]
2 is followed by 3. 4 is last, so it has no answer.
Constraints
- 1 <= len(nums1) <= len(nums2) <= 1000
- 0 <= nums1[i], nums2[i] <= 10^4
- All values in each array are distinct
- Every value of nums1 appears in nums2
Approaches
- Baseline: find each value, scan to its right — time O(n · m), space O(1) beyond the answer
Follow-up
What if nums2 is circular, so the search wraps around to the start? Walk the array twice, pushing only during the first pass. And what if values repeat? Key the answers by index instead of by value.
Related problems
Start free on Cariara · Coding problems · System design studio
