Watch 9 video solutions for Next Greater Element IV, a hard level problem involving Array, Binary Search, Stack. This walkthrough by Bro Coders has 4,654 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a 0-indexed array of non-negative integers nums. For each integer in nums, you must find its respective second greater integer.
The second greater integer of nums[i] is nums[j] such that:
j > inums[j] > nums[i]k such that nums[k] > nums[i] and i < k < j.If there is no such nums[j], the second greater integer is considered to be -1.
[1, 2, 4, 3], the second greater integer of 1 is 4, 2 is 3, and that of 3 and 4 is -1.Return an integer array answer, where answer[i] is the second greater integer of nums[i].
Example 1:
Input: nums = [2,4,0,9,6] Output: [9,6,6,-1,-1] Explanation: 0th index: 4 is the first integer greater than 2, and 9 is the second integer greater than 2, to the right of 2. 1st index: 9 is the first, and 6 is the second integer greater than 4, to the right of 4. 2nd index: 9 is the first, and 6 is the second integer greater than 0, to the right of 0. 3rd index: There is no integer greater than 9 to its right, so the second greater integer is considered to be -1. 4th index: There is no integer greater than 6 to its right, so the second greater integer is considered to be -1. Thus, we return [9,6,6,-1,-1].
Example 2:
Input: nums = [3,3] Output: [-1,-1] Explanation: We return [-1,-1] since neither integer has any integer greater than it.
Constraints:
1 <= nums.length <= 1050 <= nums[i] <= 109Problem Overview: You are given an array nums. For each index i, find the second element to the right that is strictly greater than nums[i]. The first greater element is ignored; the answer must be the next greater element that appears after it. If such an element does not exist, return -1 for that position.
Approach 1: Stack-Based Approach (Monotonic Stack) (Time: O(n), Space: O(n))
This approach processes the array from left to right while maintaining two stacks of indices. The first stack tracks elements waiting for their first greater value using a decreasing monotonic stack. When a larger number appears, indices popped from this stack have found their first greater element and move to a second stack. The second stack holds indices that are now waiting for their second greater value.
Whenever the current number is larger than the values represented by indices in the second stack, those elements have found their second greater element and can be resolved immediately. Each index moves through the stacks at most once, so the algorithm runs in linear time. This technique combines ideas from stack processing and array traversal to efficiently track both first and second greater relationships.
Approach 2: Priority Queue (Heap) Approach (Time: O(n log n), Space: O(n))
This approach separates the discovery of the first greater element from the search for the second greater element using a min-heap. While scanning the array, maintain a monotonic stack to identify when an element finds its first greater value. Once that happens, push the index into a priority queue (min-heap) keyed by its value.
As you continue iterating, compare the current value with the smallest values in the heap. If the current number is greater, it becomes the second greater element for those indices, and they are removed from the heap. Heap operations introduce a log n factor, making the complexity O(n log n), but the implementation is often easier to reason about when separating the two phases.
Recommended for interviews: The stack-based monotonic approach is typically expected in interviews because it achieves optimal O(n) time and demonstrates strong understanding of monotonic stack patterns. The heap approach is still valid and easier to derive, but the extra log n factor makes it slightly less optimal.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two Monotonic Stacks | O(n) | O(n) | Best general solution; optimal linear scan using stack transitions |
| Stack + Priority Queue (Heap) | O(n log n) | O(n) | Easier conceptual separation between first and second greater discovery |