2454. Next Greater Element IV
Problem Description
The given problem presents us with an array of non-negative integers nums
. Our task is to calculate the "second greater" integer for each element in the array. The "second greater" integer for nums[i]
is the integer nums[j]
that satisfies three conditions:
- The index
j
is greater than indexi
. - The value at
nums[j]
is greater than the value atnums[i]
. - There exists exactly one index
k
, such thati < k < j
, and the valuenums[k]
is greater thannums[i]
but less thannums[j]
.
If no such nums[j]
exists, then we should mark the second greater integer as -1
.
For example, in the array [1, 2, 4, 3]
, the second greater integer for the value 1
at index 0
is 4
at index 2
, since it's the only value that satisfies all the conditions (greater than 1
, comes after 1
, and there is exactly one value between 1
and 4
which is also greater than 1
). Following the same rules, the second greater integer for 2
is 3
, and for 4
and 3
it is -1
since no suitable integers follow them.
The goal is to generate and return an array answer
where answer[i]
is the second greater integer of nums[i]
.
Intuition
The intuition for solving this problem is to make use of a stack (stk
) and a heap queue (q
) to efficiently track the greater elements. The approach can be broken down into the following steps:
-
Initialize two support structures: a stack (
stk
) to keep indices of the elements fromnums
for potential candidates of the "first greater" integer, and a min-heap (q
) to keep track of potential candidates for the "second greater" integer. -
Traverse through the elements of
nums
and use the two data structures to check and assign the "second greater" integer for the current element if applicable. -
When a new element
v
is found that is greater than the element of the top index instk
, we need to check if it can be the "second greater" for previous elements. Thus, we move such indices fromstk
toq
because we've found their "first greater" and are now looking for their "second greater". -
While encountering a new element
v
that is greater than the items inq
, we update the answer for those indices becausev
now acts as their "second greater" integer. We can do this safely because the heap ensures the smallest element is always at the top, so we will encounter the "second greater" in the correct order. -
Append the current index
i
tostk
, because we've yet to find even the "first greater" for this element. -
After traversing all elements, we return the
ans
array that contains the "second greater" integers or-1
for each corresponding index.
This approach allows us to effectively find the necessary "second greater" integer for each element in a single pass throughout the array.
Learn more about Stack, Binary Search, Sorting, Monotonic Stack and Heap (Priority Queue) patterns.
Solution Approach
The solution makes clever use of a stack and a heap queue (min-heap) to keep track of the potential "first greater" and "second greater" elements for each item in the nums
array respectively. Here's a step-by-step explanation of the implementation details:
-
Initialize Helper Structures: We utilize a stack
stk
and a min-heapq
.stk
holds indices of elements for which we have not yet encountered any greater elements, andq
maintains a pair(value, index)
of potential "second greater" elements in ascending value order due to its heap structure. -
Iterate Through Elements:
- We iterate over each element
v
innums
array using its indexi
. We comparev
with the elements represented by indices instk
andq
to find and set their "second greater" elements.
- We iterate over each element
-
Update Answer for Elements in the Heap Queue:
- While the min-heap is not empty and the smallest element (at the heap's top) is less than
v
, we set the answer for that index (the second element of the heap's top pair) tov
, asv
is their "second greater" element. We then remove this top element from the heap withheappop(q)
.
- While the min-heap is not empty and the smallest element (at the heap's top) is less than
-
Move Indices from Stack to Heap:
- For every element in
stk
where the corresponding value innums
is less thanv
, we push a pair(value, index)
onto the min-heap and pop it from the stack. We do this because we've found their "first greater" element, which isv
, and now we're interested in finding their "second greater" element.
- For every element in
-
Maintain Stack:
- After dealing with the heap queue, we add the current index
i
to thestk
. This is because for the current element at indexi
, either no greater element has been found yet, or it's potentially the "first greater" for upcoming elements.
- After dealing with the heap queue, we add the current index
-
Final Answer:
- The array
ans
is initialized with-1
for all indices to cover scenarios where no "second greater" element is found. Upon completion of the iteration,ans
is updated with the "second greater" elements wherever applicable and is ready to be returned.
- The array
Using a stack and a min-heap like this allows us to maintain the invariant that stk
contains indices strictly in increasing order of their corresponding values in nums
. Simultaneously, the min-heap maintains the potential "second greater" candidates in the order in which they should be considered, ensuring that we can efficiently update ans
as we traverse nums
.
This algorithm effectively collapses nested loops that would otherwise be needed to find the "second greater" element for each item, thus improving the overall running time, especially for large arrays.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a small example to illustrate the solution approach:
Assume our input array is nums = [2, 7, 3, 5, 4]
.
-
Initialize Helper Structures: We start with an empty stack (
stk
) and min-heap (q
), and an answer arrayans
initialized to-1
for each index. -
Iterate Through Elements:
- For
i = 0
,v = 2
. Since bothstk
andq
are empty, we just push index0
ontostk
. - For
i = 1
,v = 7
.7
is greater than2
(nums[stk[-1]]
), so we move index0
fromstk
toq
with value2
, and push index1
ontostk
. - For
i = 2
,v = 3
. It's greater than2
(value at top of theq
) but less than7
(nums[stk[-1]]
) so we pop(2, 0)
fromq
and updateans[0]
to3
, then push index2
ontostk
.
- For
-
Update Answer for Elements in the Heap Queue:
- The heap queue
q
currently has no elements less than the currentv
, so we skip this for index2
.
- The heap queue
-
Move Indices from Stack to Heap:
- Index
1
stays instk
as7
is greater than3
, so we do not modifyq
for index2
.
- Index
-
Maintain Stack:
- We simply add index
2
tostk
.
- We simply add index
-
Repeat Iteration:
- For
i = 3
,v = 5
. It's greater than3
(nums[stk[-1]]
), so we move index2
fromstk
toq
with value3
. Sinceq
is now non-empty and the value at the top(3, 2)
is less thanv = 5
, we pop(3, 2)
fromq
and updateans[2]
to5
. Index3
is pushed ontostk
. - For
i = 4
,v = 4
. It's less than5
(nums[stk[-1]]
), so index4
is pushed ontostk
.
- For
-
Final Answer:
- After iterating through the array, we have
ans = [-1, -1, 5, -1, -1]
. We have not updatedans[1]
because7
was never popped fromstk
, indicating no second greater element was found for7
. The same reasoning applies toans[3]
andans[4]
.
- After iterating through the array, we have
In summary, we performed an iterative approach where we maintained a stack for indices of potential first greater elements and a heap queue for indices of potential second greater elements, popping from and pushing to these structures as needed while traversing the array. This allowed us to efficiently find and update the second greater element for each item, giving us ans = [-1, -1, 5, -1, -1]
as our result.
Solution Implementation
1from typing import List
2from heapq import heappop, heappush
3
4class Solution:
5 def secondGreaterElement(self, nums: List[int]) -> List[int]:
6 # stack to keep track of indexes of elements in decreasing order
7 stack = []
8 # min-heap to store the pair (element, index) for the potential second greater elements
9 min_heap = []
10 # initialize the answer list with -1 for each element
11 answer = [-1] * len(nums)
12
13 # Iterate over the indices and values of nums.
14 for index, value in enumerate(nums):
15 # If the current value is greater than the element pointed by the current index
16 # of the queue, pop elements from the heap and update their answer to the current value.
17 while min_heap and min_heap[0][0] < value:
18 answer[min_heap[0][1]] = value
19 heappop(min_heap)
20
21 # While the stack is not empty and the current value is greater than the top
22 # element of the stack, push the pair (element of the stack, index) into the heap.
23 while stack and nums[stack[-1]] < value:
24 heappush(min_heap, (nums[stack[-1]], stack.pop()))
25
26 # Append the current index to the stack.
27 stack.append(index)
28
29 # The stack now contains indexes of elements for which no second greater element exists
30 # and therefore their corresponding values in the answer list remain -1
31
32 return answer
33# The rewritten code now uses Python 3 syntax, has standardized variable naming,
34# and includes comments explaining the functionality of the code.
35
1class Solution {
2 public int[] secondGreaterElement(int[] nums) {
3 // Stack to keep indexes of elements in a descending order
4 Deque<Integer> stack = new ArrayDeque<>();
5
6 // Priority Queue to store the elements and their corresponding indexes which are waiting for the second greater element
7 PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> a[0] - b[0]);
8
9 // Length of the input array
10 int length = nums.length;
11
12 // Array to hold the final answer, initialized to -1 as default value
13 int[] answer = new int[length];
14 Arrays.fill(answer, -1);
15
16 // Iterating over input array elements
17 for (int i = 0; i < length; ++i) {
18 int value = nums[i];
19
20 // Process elements in the priority queue with value smaller than the current element
21 while (!queue.isEmpty() && queue.peek()[0] < value) {
22 answer[queue.peek()[1]] = value; // Assign the current element as second greater
23 queue.poll(); // Remove from priority queue
24 }
25
26 // Process elements in the stack with value smaller than the current element
27 while (!stack.isEmpty() && nums[stack.peek()] < value) {
28 // Add elements to the priority queue with their value and index
29 queue.offer(new int[] {nums[stack.peek()], stack.pop()});
30 }
31
32 // Push current index onto the stack
33 stack.push(i);
34 }
35
36 // Return the answer array containing the second greater element for each position
37 return answer;
38 }
39}
40
1// Including the necessary headers
2#include <vector>
3#include <stack>
4#include <queue>
5#include <utility>
6using namespace std;
7
8// Aliasing the `pair<int, int>` as `Pair`.
9using Pair = pair<int, int>;
10
11class Solution {
12public:
13 // This function finds the 'next greater element' for each element.
14 // The 'next greater element' is defined as the first element to the right which is larger.
15 // If no such element exists, -1 is recorded.
16 vector<int> secondGreaterElement(vector<int>& nums) {
17 // Stack used to keep track of elements indices for which we haven't found a greater element.
18 stack<int> indexStack;
19 // Priority queue used to store values with their indices, where the smallest is at the top.
20 priority_queue<Pair, vector<Pair>, greater<Pair>> minHeap;
21
22 int n = nums.size(); // Number of elements in the input vector.
23
24 // Vector to store the answers, initialized with -1 for each element.
25 vector<int> results(n, -1);
26
27 // Iterate over each element in `nums`.
28 for (int i = 0; i < n; ++i) {
29 int currentValue = nums[i];
30
31 // Check if the top element of the min-heap is smaller than `currentValue`.
32 // If it is, the `currentValue` is the next greater element for the index at the top of the heap.
33 while (!minHeap.empty() && minHeap.top().first < currentValue) {
34 // Assign `currentValue` as the result for the corresponding index.
35 results[minHeap.top().second] = currentValue;
36 // Remove the element from the heap since it has been processed.
37 minHeap.pop();
38 }
39
40 // Check if the elements remaining in the stack have a smaller value than `currentValue`.
41 while (!indexStack.empty() && nums[indexStack.top()] < currentValue) {
42 // Push these elements onto the min-heap with their index.
43 minHeap.push({nums[indexStack.top()], indexStack.top()});
44 // Remove the element from the stack.
45 indexStack.pop();
46 }
47
48 // Add the current index to the stack for future comparisons.
49 indexStack.push(i);
50 }
51
52 // Return the final result vector.
53 return results;
54 }
55};
56
1// The type alias for a pair of numbers where the first is the element and the second is the index.
2type Pair = [number, number];
3
4// The stack used to keep track of elements' indices for which we haven't found a greater element.
5let indexStack: number[] = [];
6
7// Simulating the priority queue (min-heap) using an array and a sort function.
8let minHeap: Pair[] = [];
9
10// The function to find the 'next greater element' for each element in the array.
11// The 'next greater element' is the first larger element to the right; -1 if none exists.
12function secondGreaterElement(nums: number[]): number[] {
13 const n: number = nums.length; // Number of elements in the input array.
14 let results: number[] = new Array(n).fill(-1); // Initialize the result array with -1s.
15
16 // Function to simulate the `pop` functionality on the minHeap.
17 function popMinHeap() {
18 minHeap.sort(([valA,], [valB,]) => valA - valB); // Ensure the smallest value is on top.
19 return minHeap.shift(); // Remove and return the first element (top of the heap).
20 }
21
22 // Iterate over each element in `nums`.
23 for (let i = 0; i < n; ++i) {
24 const currentValue = nums[i];
25
26 // While there's a smaller element at the 'top' of the minHeap, update `results`.
27 while (minHeap.length > 0 && minHeap[0][0] < currentValue) {
28 const [, index] = popMinHeap(); // `pop` the minHeap and get the index.
29 results[index] = currentValue; // Assign `currentValue` as the result for the index.
30 }
31
32 // While elements remaining in the stack have smaller values, add them to the minHeap.
33 while (indexStack.length > 0 && nums[indexStack[indexStack.length - 1]] < currentValue) {
34 const idx = indexStack.pop(); // Pop the stack.
35 minHeap.push([nums[idx!], idx!]); // Add the element to the minHeap.
36 }
37
38 // Add the current index to the stack.
39 indexStack.push(i);
40 }
41
42 // Return the final result array.
43 return results;
44}
45
Time and Space Complexity
The given algorithm finds the second greater element for each element in the list nums
. It utilizes a stack (stk
) and a priority queue (q
, implemented as a min-heap using the heapq module in python).
Time Complexity:
- The algorithm traverses through each element in the list exactly once, which gives us a linear component of
O(n)
. - Inside the loop, there are a couple of operations involving the stack and heap:
- The
while stk and nums[stk[-1]] < v
loop can push a number of elements into the heapq
, however, each element is pushed at most once, because once an element is popped fromstk
and pushed intoq
, it is not handled by this loop again. - The
while q and q[0][0] < v
loop pops elements from the heap until a number greater than the current numberv
is not found. Each element in the list could be popped at most once during the entire traversal. Heap operations (push and pop) areO(log k)
wherek
is the number of elements in the heap. However, since we can perform at mostn
such operations in total (as the heap can never contain more elements than the number in the list), the complexity for heap operations over the traversal isO(n log n)
.
- The
- Therefore, the total time complexity for the algorithm combines the linear traversal of the list and the
O(n log n)
complexity of heap operations, which gives usO(n log n)
.
Space Complexity:
- The stack
stk
and the heapq
both store indices of elements. In the worst case, they could store all indices. Hence, the space complexity of these data structures isO(n)
. - An additional list
ans
is created to store the result, which also takesO(n)
space. - Thus, combining the space required for the stack, heap, and the results list, the overall space complexity of the algorithm is
O(n)
, as the constants are dropped in Big O notation.
Learn more about how to find time and space complexity quickly using problem constraints.
What's the output of running the following function using input [30, 20, 10, 100, 33, 12]
?
1def fun(arr: List[int]) -> List[int]:
2 import heapq
3 heapq.heapify(arr)
4 res = []
5 for i in range(3):
6 res.append(heapq.heappop(arr))
7 return res
8
1public static int[] fun(int[] arr) {
2 int[] res = new int[3];
3 PriorityQueue<Integer> heap = new PriorityQueue<>();
4 for (int i = 0; i < arr.length; i++) {
5 heap.add(arr[i]);
6 }
7 for (int i = 0; i < 3; i++) {
8 res[i] = heap.poll();
9 }
10 return res;
11}
12
1class HeapItem {
2 constructor(item, priority = item) {
3 this.item = item;
4 this.priority = priority;
5 }
6}
7
8class MinHeap {
9 constructor() {
10 this.heap = [];
11 }
12
13 push(node) {
14 // insert the new node at the end of the heap array
15 this.heap.push(node);
16 // find the correct position for the new node
17 this.bubble_up();
18 }
19
20 bubble_up() {
21 let index = this.heap.length - 1;
22
23 while (index > 0) {
24 const element = this.heap[index];
25 const parentIndex = Math.floor((index - 1) / 2);
26 const parent = this.heap[parentIndex];
27
28 if (parent.priority <= element.priority) break;
29 // if the parent is bigger than the child then swap the parent and child
30 this.heap[index] = parent;
31 this.heap[parentIndex] = element;
32 index = parentIndex;
33 }
34 }
35
36 pop() {
37 const min = this.heap[0];
38 this.heap[0] = this.heap[this.size() - 1];
39 this.heap.pop();
40 this.bubble_down();
41 return min;
42 }
43
44 bubble_down() {
45 let index = 0;
46 let min = index;
47 const n = this.heap.length;
48
49 while (index < n) {
50 const left = 2 * index + 1;
51 const right = left + 1;
52
53 if (left < n && this.heap[left].priority < this.heap[min].priority) {
54 min = left;
55 }
56 if (right < n && this.heap[right].priority < this.heap[min].priority) {
57 min = right;
58 }
59 if (min === index) break;
60 [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61 index = min;
62 }
63 }
64
65 peek() {
66 return this.heap[0];
67 }
68
69 size() {
70 return this.heap.length;
71 }
72}
73
74function fun(arr) {
75 const heap = new MinHeap();
76 for (const x of arr) {
77 heap.push(new HeapItem(x));
78 }
79 const res = [];
80 for (let i = 0; i < 3; i++) {
81 res.push(heap.pop().item);
82 }
83 return res;
84}
85
Recommended Readings
Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.