C++ map + monotonic stack, traverse array from right to left, ❌ binary search and priority queue.
IntuitionI have read several different solutions online, the most impressive one so far is this two-stack streamlined algorithm, looping from left to right, to
### Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
I have read several different solutions online, the most impressive one so far is this two-stack streamlined algorithm, looping from left to right, to find the first and second larger value to the right for each value. It is intuitive, yet ingenious as hell:

```cpp []
class Solution {
public:
        vector<int> secondGreaterElement(vector<int>& A) {
        int n = A.size();
        vector<int> res(n, -1), s1, s2, tmp;
        for (int i = 0 ;i < n; ++i) {
            while (!s2.empty() && A[s2.back()] < A[i])
                res[s2.back()] = A[i], s2.pop_back();
            while (!s1.empty() && A[s1.back()] < A[i])
                tmp.push_back(s1.back()), s1.pop_back();
            while (!tmp.empty())
                s2.push_back(tmp.back()), tmp.pop_back();
            s1.push_back(i);
        }
        return res;
    }
};
```
I have also seen other approaches, such as those using sparse table, segment tree, multiset, etc. 

But one particular way to solve it is using binary search, and I do not seem to understand why must it be necessary.

Here is the idea:

![leetcode_2_.png](https://assets.leetcode.com/users/images/7f24dc17-98d2-453c-8f92-4a19df20ab0f_1740638626.8822744.png)


Create a map of vectors **M**, with the key as array indices **i**, such that for each vector **v** at index key i, it stores all the prior index and value pairs **{nums[j],j}**, such that nums[j] < nums[i] and nums[i] is their first greater element to their right.

For example, refer to the diagram above, at index = n-3, the vector $$v_{n-3}$$ will be like : {{**0**,n-4},{**1**,n-5},{**3**,n-6},{**7**,n-8},{**8**,n-9},{**9**,n-10}}

Based on the diagram above, the index keys **i** stored in **M** so far, such that vector M[i]=**v** has >= 1 values are: n-1, n-3, n-6, n-10. (*look at the cells that each of the arrows are pointing at.*)

The method to find the first greater value to the right for each value is using a stack to keep track of the nearest greater value to the right.

Now, here are some more observations:

1. For each vector **v** in map **M**, the value pairs **{nums[?],?}** in **v** must be non-decreasing from left to right, given that the values in array nums are processed from right to left.

    As a counter statement, given index **i**, such that there exist an index **j** and nums[**i**] is **not** the first greater value to the right of nums[**j**], then there exist some value at index **k** that is closer to **j** from it's right, such that **k**<**i** and **j**<**k** and nums[**k**]>nums[**j**]. 

    If now, there exist an index **l**, such that **l**<**j** and nums[**i**] **is** the first greater value to the right of nums[**l**], that means nums[**l**] **must be greater than all possible** nums[**k**] such that **l**<**k**<**i**, and nums[**i**] is **the first value** that is larger than nums[**l**] from the right, such that **l**<**i**.

    So, obviously, you push **{nums[l],l}** to the back of M[**i**]=**v**, and of course it will be the largest value so far. The next value to be pushed back to M[**i**]=**v** will be greater than nums[**l**], and so on. 

2. For each key **i** in map **M**, there is a way to keep track of values to the right of i (values with index > i), such that values are also non-decreasing.

    For each index key **i** in map **M**, we perform a for-loop on vector M[i]=**v** from left to right. 

    For the diagram below, yellow highlighted values are those stored in M[i]=**v** as {{**0**,n-4},{**1**,n-5},{**3**,n-6},{**7**,n-8},{**8**,n-9},{**9**,n-10}}, nums[**i**]=**10**

    ![image.png](https://assets.leetcode.com/users/images/d9e86226-cc62-49dd-b9d3-1b253b73b754_1740640277.0873506.png)


    In the example above, such that i=n-3, the second greatest value for values (highlighted in yellow) 0,1,3,7,8 is 9, and the next greater value (highlighted in yellow) for 9 is 10. The current index **i** will have black background color.

    the next index to be processed after i=n-3 is i=n-6.

    ![image.png](https://assets.leetcode.com/users/images/c93efea0-48ac-4737-93ed-dd8da68e10dc_1740639760.2132795.png)

    the next index to be processed after i=n-6 is i=n-10.

    ![image.png](https://assets.leetcode.com/users/images/3666f22a-062b-4a7a-aa57-8967dc8d3587_1740639907.0318842.png)

    Notice something? For each current index **i**, unless it is the first ever i to be processed, it is guaranteed to have at least one prior greater value to work with. (highlighted in red in several diagrams above.)

    Which can be represented using the diagram below, with cell with background color as blue as non-decreasing values to the right:

    ![image.png](https://assets.leetcode.com/users/images/d44ca50e-2442-4570-a8ca-d33adb577fa2_1740640218.194387.png)

    Since values in **M[i]=v** will be non-decreasing as well (based on observation 1), we can check each value in **v** against values to the right of **i** stored in another stack **V**.

    ![image.png](https://assets.leetcode.com/users/images/6f13a983-fd23-47f1-9cec-d9d9f223e1fc_1740640974.4209144.png)

    If any value in vector **v**, which let it be a value in array nums with index **m**, is >= the top values on stack **V**, pop that value from stack **V** (let this value be **PV**) **permanently**, it will **not be the second greater value for all other values with index < m**. 

    Why? Because, at least value nums[i] at **i** is **already greater than** nums[m], and i must be < the index of **PV**. 

    For values with index < m, 2 cases:

    (a) value <= nums[m]. In this case, nums[i], **or** any value placed to the left of **PV**, must be their second nearest greater value.

    (b) value > nums[m]. In this case, that value is larger than **PV** anyways. 

    Therefore, **PV** can be removed **permanently**.

It is a long-winded essay, but with the two observations mentioned, I have shown that there is **no need** to perform any binary search, or using any priority queue or ordered data structures to maintain the ordering of values or indices. 

### Approach
<!-- Describe your approach to solving the problem. -->
Refer to the code implementation below.

### Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
~O(N log N)
- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
~O(N), a rough estimate.
### Code
```cpp []
typedef pair<int,int> p;
//typedef std::priority_queue<p,vector<p>,std::greater<p>> lq;
class Solution {
public:
    const static int MAX=1e5+4; int R[MAX];
    std::unordered_map<int,vector<p>> RR;
    std::vector<int> RRI;
    std::stack<p> V;
    vector<int> secondGreaterElement(vector<int>& nums) {
        std::stack<p> S={};
        int len=nums.size();
        for (int i=len-1; i>=0; i--) {
            while (!S.empty()&&S.top().first<=nums[i]) {S.pop();}
            if (S.empty()) {R[i]=-1;}
            else {
                R[i]=S.top().second; 
                if (RR.count(S.top().second)==0) {
                    RRI.push_back(S.top().second);
                    RR[S.top().second]={};
                }
                RR[S.top().second].push_back({nums[i],i});
            }
            S.push({nums[i],i});
        } int idx=len-1; vector<int> A(len,-1);
        std::sort(RRI.rbegin(),RRI.rend()); 
        for (int rri:RRI) {
            while (idx>rri&&idx>=0) {
                p curval={nums[idx],idx};
                while (!V.empty()&&V.top().first<=nums[idx]) {V.pop();}
                V.push(curval);
                idx--;
            }
            vector<p> Q=RR[rri];
            //while (!Q.empty()) {
            for (p& ritr : Q) {
                int tmpidx=-1;
                //p ritr=Q.top(); Q.pop();
                int rval=ritr.first;
                while (!V.empty()) {
                    int vval=V.top().first;
                    if (vval>rval) {
                        tmpidx=V.top().second;
                        break;
                    }
                    V.pop();
                }
                if (tmpidx!=-1)
                    A[ritr.second]=nums[tmpidx];
            }
        }
        return A;
    }
};
```
['C++']