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.
This approach involves using two stacks to maintain indices related to the next greater element. First, find the first greater element for each position with the help of a monotonic stack. Then use another pass to determine the second greater element by utilizing the previously built information.
This implementation uses two stacks. As we traverse the array from the end:
1. If an element is greater than the current `i` element, it is pushed to the first stack.
2. For every element processed, its second greater element is popped from the second stack if it exists.
Time Complexity: O(n), where n is the length of the input array. We perform a constant amount of work per element.
Space Complexity: O(n), due to the storage requirements of the stacks used.
Another approach is to use a min-heap (priority queue) to find the second greater element. By iterating from the start and maintaining order in a heap, you can effectively emulate the stack operations by priority ordering.
In this C implementation, we simulate the behavior of a min-heap. The array `heap` is restructured as needed to maintain the heap property. Each insertion involves heapify operation to maintain the max heap order.
Time Complexity: O(n log n), where n is the size of input array due to heap operations. Space Complexity: O(n) from heap usage.
We can convert the elements in the array into pairs (x, i), where x is the value of the element and i is the index of the element. Then sort by the value of the elements in descending order.
Next, we traverse the sorted array, maintaining an ordered set that stores the indices of the elements. When we traverse to the element (x, i), the indices of all elements greater than x are already in the ordered set. We only need to find the index j of the next element after i in the ordered set, then the element corresponding to j is the second largest element of x. Then, we add i to the ordered set. Continue to traverse the next element.
The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the length of the array.
Python
Java
C++
TypeScript
| Approach | Complexity |
|---|---|
| Stack-Based Approach | Time Complexity: O(n), where n is the length of the input array. We perform a constant amount of work per element. |
| Priority Queue (Heap) Approach | Time Complexity: O(n log n), where n is the size of input array due to heap operations. Space Complexity: O(n) from heap usage. |
| Sorting + Ordered Set | — |
| 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 |
2454. Next Greater Element IV | Leetcode BiWeekly 90 | LeetCode 2454 • Bro Coders • 4,654 views views
Watch 8 more video solutions →Practice Next Greater Element IV with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor