Next Greater Element IV
HardPrompt
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]- There exists exactly one index
ksuch thatnums[k] > nums[i]andi < k < j.
If there is no such nums[j], the second greater integer is considered to be -1.
- For example, in the array
[1, 2, 4, 3], the second greater integer of1is4,2is3, and that of3and4is-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] <= 109
Approaches
3 approaches with complexity analysis and trade-offs.
This is the most efficient approach, achieving linear time complexity. It builds upon the idea of using a monotonic stack but employs a second stack instead of a priority queue to manage elements that are waiting for their second greater element. This avoids the logarithmic time complexity of priority queue operations.
Algorithm
- Initialize
answerarray of sizenwith-1. - Initialize two stacks,
s1ands2, to store indices. - For
ifrom0ton-1: - Let
currentNum = nums[i]. - While
s2is not empty andnums[s2.peek()] < currentNum: -
`answer[s2.pop()] = currentNum`. - Initialize a temporary stack
temp. - While
s1is not empty andnums[s1.peek()] < currentNum: -
`temp.push(s1.pop())`. - While
tempis not empty: s2.push(temp.pop()).- Push
iontos1. - Return
answer.
Walkthrough
We use two stacks, s1 and s2. Both will store indices and will be maintained as monotonic stacks (elements with smaller values on top of elements with larger values).
s1: Stores indices of elements for which we are looking for the first greater element.s2: Stores indices of elements for which we have found the first greater element and are now looking for the second. We iterate through the arraynumswith indexi. For eachnums[i]:
- We first process
s2. Whiles2is not empty and the element at its topnums[s2.peek()]is smaller thannums[i], we have found the second greater element fors2.peek(). We pop the index and set its answer tonums[i]. - Then, we process
s1. Whiles1is not empty andnums[s1.peek()]is smaller thannums[i], we have found the first greater element. We pop these indices froms1. Since they now need to find their second greater element, they must be moved tos2. - A crucial detail is how to move elements from
s1tos2. When we pop multiple indices froms1, they come out in increasing order of their corresponding values. To maintains2as a monotonic (decreasing value) stack, we must push these indices ontos2in reverse order. We can use a temporary stack to achieve this reversal. - Finally, we push the current index
iontos1. This single pass through the array correctly identifies the second greater element for all indices in linear time.
import java.util.ArrayDeque;import java.util.Arrays;import java.util.Deque; class Solution { public int[] secondGreaterElement(int[] nums) { int n = nums.length; int[] answer = new int[n]; Arrays.fill(answer, -1); Deque<Integer> s1 = new ArrayDeque<>(); Deque<Integer> s2 = new ArrayDeque<>(); for (int i = 0; i < n; i++) { int currentNum = nums[i]; while (!s2.isEmpty() && nums[s2.peek()] < currentNum) { answer[s2.pop()] = currentNum; } Deque<Integer> tempStack = new ArrayDeque<>(); while (!s1.isEmpty() && nums[s1.peek()] < currentNum) { tempStack.push(s1.pop()); } while(!tempStack.isEmpty()){ s2.push(tempStack.pop()); } s1.push(i); } return answer; }}Complexity
Time
O(N). Each index is pushed and popped from `s1`, `temp`, and `s2` at most once. All operations are amortized O(1), leading to a total linear time complexity.
Space
O(N). In the worst case (e.g., a strictly decreasing array), all indices could be stored in the stacks.
Trade-offs
Pros
Optimal time complexity. It's the most efficient way to solve this problem.
Cons
The logic involving three stacks (including the temporary one) can be slightly more complex to reason about compared to the priority queue approach.
This is the most straightforward approach. We iterate through each element of the array. For each element nums[i], we perform a second iteration from i+1 to the end of the array to find the first and then the second element greater than nums[i].
Algorithm
- Initialize an
answerarray of sizenwith-1. - For
ifrom0ton-1: - Initialize
count = 0. - For
jfromi+1ton-1: -
If `nums[j] > nums[i]`: -
Increment `count`. -
If `count == 2`: -
Set `answer[i] = nums[j]`. -
Break the inner loop. - Return
answer.
Walkthrough
We initialize an answer array of the same size as nums, filling it with -1. This array will store the result.
We loop through the input array nums with an index i from 0 to n-1.
Inside this loop, for each nums[i], we start another loop with index j from i+1 to n-1.
We use a counter, greater_count, initialized to 0, to keep track of how many numbers greater than nums[i] we have found so far to its right.
In the inner loop, if we find an element nums[j] that is greater than nums[i], we increment greater_count.
If greater_count becomes 2, it means nums[j] is the second greater element for nums[i]. We store nums[j] in answer[i] and break out of the inner loop since we've found our answer for nums[i].
If the inner loop completes and greater_count is less than 2, it means there is no second greater element, and answer[i] remains -1.
After iterating through all i, the answer array is returned.
import java.util.Arrays; class Solution { public int[] secondGreaterElement(int[] nums) { int n = nums.length; int[] answer = new int[n]; Arrays.fill(answer, -1); for (int i = 0; i < n; i++) { int count = 0; for (int j = i + 1; j < n; j++) { if (nums[j] > nums[i]) { count++; if (count == 2) { answer[i] = nums[j]; break; } } } } return answer; }}Complexity
Time
O(N^2), where N is the number of elements in `nums`. The nested loops lead to a quadratic time complexity. For each element, we might scan the rest of the array.
Space
O(N) to store the output `answer` array. If the output array is not considered extra space, the complexity is O(1).
Trade-offs
Pros
Simple to understand and implement.
Cons
Inefficient and will likely result in a 'Time Limit Exceeded' (TLE) error for large inputs due to its quadratic time complexity.
This approach improves upon the brute-force method by using data structures to avoid re-scanning. We use a monotonic stack to find the first greater element and a min-priority queue to efficiently find the second greater element.
Algorithm
- Initialize
answerarray of sizenwith-1. - Initialize a monotonic stack
s1(for indices). - Initialize a min-priority queue
pq(for pairs[value, index]sorted by value). - For
ifrom0ton-1: - Let
currentNum = nums[i]. - While
pqis not empty andpq.peek().value < currentNum: -
`idx = pq.poll().index`. -
`answer[idx] = currentNum`. - While
s1is not empty andnums[s1.peek()] < currentNum: idx = s1.pop().- Add
[nums[idx], idx]topq. - Push
iontos1. - Return
answer.
Walkthrough
The core idea is to process the array from left to right. We use a monotonic stack, s1, to keep track of indices of elements for which we haven't yet found a first greater element. The stack maintains indices of elements in decreasing order of their values.
We use a min-priority queue, pq, to store pairs of [value, index] for elements for which we have found the first greater element, but are now waiting for the second. The priority queue is ordered by the element's value.
We iterate through nums with index i. For each nums[i]:
- We first check the priority queue
pq. Any element[val, idx]at the top ofpqwhereval < nums[i]has found its second greater element, which isnums[i]. We poll these elements frompqand updateanswer[idx] = nums[i]. - Next, we check the monotonic stack
s1. Any elementnums[s1.peek()]that is smaller thannums[i]has found its first greater element, which isnums[i]. We pop its indexidxfroms1and add the pair[nums[idx], idx]to the priority queuepq, as it now needs to find its second greater element. - Finally, we push the current index
ionto the stacks1, maintaining its monotonic property. After iterating through the entire array, any indices for which the answer was not found will retain their default-1value.
import java.util.ArrayDeque;import java.util.Arrays;import java.util.Deque;import java.util.PriorityQueue; class Solution { public int[] secondGreaterElement(int[] nums) { int n = nums.length; int[] answer = new int[n]; Arrays.fill(answer, -1); Deque<Integer> s1 = new ArrayDeque<>(); PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]); for (int i = 0; i < n; i++) { int currentNum = nums[i]; while (!pq.isEmpty() && pq.peek()[0] < currentNum) { answer[pq.poll()[1]] = currentNum; } while (!s1.isEmpty() && nums[s1.peek()] < currentNum) { int index = s1.pop(); pq.offer(new int[]{nums[index], index}); } s1.push(i); } return answer; }}Complexity
Time
O(N log N). Each element is pushed and popped from the stack once (O(N)). Each element is offered and polled from the priority queue at most once. Priority queue operations take O(log K) time, where K is the size of the queue (up to N). This gives a total time complexity of O(N log N).
Space
O(N). In the worst case, the stack and the priority queue can store up to N elements.
Trade-offs
Pros
Significantly more efficient than the brute-force approach and can pass the time limits for the given constraints.
Cons
Not the most optimal solution. The
log Nfactor from the priority queue can be eliminated.
Solutions
Solution
class Solution {public int[] secondGreaterElement(int[] nums) { int n = nums.length; int[] ans = new int[n]; Arrays.fill(ans, -1); int[][] arr = new int[n][0]; for (int i = 0; i < n; ++i) { arr[i] = new int[]{nums[i], i}; } Arrays.sort(arr, (a, b)->a[0] == b[0] ? a[1] - b[1] : b[0] - a[0]); TreeSet<Integer> ts = new TreeSet<>(); for (int[] pair : arr) { int i = pair[1]; Integer j = ts.higher(i); if (j != null && ts.higher(j) != null) { ans[i] = nums[ts.higher(j)]; } ts.add(i); } return ans; }}class Solution {public: vector<int> secondGreaterElement(vector<int> &nums) { int n = nums.size(); vector<int> ans(n, -1); vector<pair<int, int>> arr(n); for (int i = 0; i < n; ++i) { arr[i] = {-nums[i], i}; } sort(arr.begin(), arr.end()); set<int> ts; for (auto &[_, i] : arr) { auto it = ts.upper_bound(i); if (it != ts.end() && ts.upper_bound(*it) != ts.end()) { ans[i] = nums[*ts.upper_bound(*it)]; } ts.insert(i); } return ans; }};from sortedcontainers import SortedList class Solution : def secondGreaterElement ( self , nums : List [ int ]) -> List [ int ]: arr = [( x , i ) for i , x in enumerate ( nums )] arr . sort ( key = lambda x : - x [ 0 ]) sl = SortedList () n = len ( nums ) ans = [ - 1 ] * n for _ , i in arr : j = sl . bisect_right ( i ) if j + 1 < len ( sl ): ans [ i ] = nums [ sl [ j + 1 ]] sl . add ( i ) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.