# Next Greater Element IV
**Difficulty:** HARD
[External](https://leetcode.com/problems/next-greater-element-iv)
Canonical: https://scaleengineer.com/dsa/problems/next-greater-element-iv
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Stack, Heap (Priority Queue), Monotonic Stack
---
## Problem
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 > i`
* `nums[j] > nums[i]`
* There exists **exactly one** index `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`.

* For example, in the array `[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 <= 105`
* `0 <= nums[i] <= 109`

# Approaches
## Brute Force Iteration
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]`.
**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).
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
1. Initialize an `answer` array of size `n` with `-1`.
2. For `i` from `0` to `n-1`:
3.   Initialize `count = 0`.
4.   For `j` from `i+1` to `n-1`:
5.     If `nums[j] > nums[i]`:
6.       Increment `count`.
7.       If `count == 2`:
8.         Set `answer[i] = nums[j]`.
9.         Break the inner loop.
10. Return `answer`.

## Using a Monotonic Stack and a Min-Priority Queue
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.
**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.
**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 N` factor from the priority queue can be eliminated.
### Explanation
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]`:
1. We first check the priority queue `pq`. Any element `[val, idx]` at the top of `pq` where `val < nums[i]` has found its second greater element, which is `nums[i]`. We poll these elements from `pq` and update `answer[idx] = nums[i]`.
2. Next, we check the monotonic stack `s1`. Any element `nums[s1.peek()]` that is smaller than `nums[i]` has found its *first* greater element, which is `nums[i]`. We pop its index `idx` from `s1` and add the pair `[nums[idx], idx]` to the priority queue `pq`, as it now needs to find its second greater element.
3. Finally, we push the current index `i` onto the stack `s1`, maintaining its monotonic property.
After iterating through the entire array, any indices for which the answer was not found will retain their default `-1` value.

```java
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;
    }
}
```
### Algorithm
1. Initialize `answer` array of size `n` with `-1`.
2. Initialize a monotonic stack `s1` (for indices).
3. Initialize a min-priority queue `pq` (for pairs `[value, index]` sorted by value).
4. For `i` from `0` to `n-1`:
5.   Let `currentNum = nums[i]`.
6.   While `pq` is not empty and `pq.peek().value < currentNum`:
7.     `idx = pq.poll().index`.
8.     `answer[idx] = currentNum`.
9.   While `s1` is not empty and `nums[s1.peek()] < currentNum`:
10.    `idx = s1.pop()`.
11.    Add `[nums[idx], idx]` to `pq`.
12.  Push `i` onto `s1`.
13. Return `answer`.

## Optimal Solution with Two Monotonic Stacks
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.
**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.
**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.
### Explanation
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 array `nums` with index `i`. For each `nums[i]`:
1. We first process `s2`. While `s2` is not empty and the element at its top `nums[s2.peek()]` is smaller than `nums[i]`, we have found the second greater element for `s2.peek()`. We pop the index and set its answer to `nums[i]`.
2. Then, we process `s1`. While `s1` is not empty and `nums[s1.peek()]` is smaller than `nums[i]`, we have found the *first* greater element. We pop these indices from `s1`. Since they now need to find their second greater element, they must be moved to `s2`.
3. A crucial detail is how to move elements from `s1` to `s2`. When we pop multiple indices from `s1`, they come out in increasing order of their corresponding values. To maintain `s2` as a monotonic (decreasing value) stack, we must push these indices onto `s2` in reverse order. We can use a temporary stack to achieve this reversal.
4. Finally, we push the current index `i` onto `s1`.
This single pass through the array correctly identifies the second greater element for all indices in linear time.

```java
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;
    }
}
```
### Algorithm
1. Initialize `answer` array of size `n` with `-1`.
2. Initialize two stacks, `s1` and `s2`, to store indices.
3. For `i` from `0` to `n-1`:
4.   Let `currentNum = nums[i]`.
5.   While `s2` is not empty and `nums[s2.peek()] < currentNum`:
6.     `answer[s2.pop()] = currentNum`.
7.   Initialize a temporary stack `temp`.
8.   While `s1` is not empty and `nums[s1.peek()] < currentNum`:
9.     `temp.push(s1.pop())`.
10.  While `temp` is not empty:
11.    `s2.push(temp.pop())`.
12.  Push `i` onto `s1`.
13. Return `answer`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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 ans
```