Next Greater Element [GeeksforGeeks]

Given an array, print the Next Greater Element (NGE) for every element. The Next greater Element for an element x is the first greater element on the right side of x in array. Elements for which no greater element exist, consider itself as it next greater element.

Solution: the straightforward way is brute force, i.e, find the NGE for each element A[i] by scanning A[i+1:]. The time and space complexities of this method are O(N^2) and O(1) respectively. The more elegant way is to employ a stack. The basic idea is processing each element A[i] one by one by following the rules below:

1. If the stack is empty, simply push index i into stack;
2. If not, compare A[i] and the element of A with index of top-most element, say s,  of the stack, i.e., A[s]: 
• If A[s] \ge A[i], simply push i into stack;
• If A[s]<A[i], then it means that A[i] is NGE of A[s], thus we pop s, and repeatedly process the rest elements of stack until we got A[s] \ge A[i] or stack become empty; then we push i into stack. 

Since each element is pushed into stack exactly once, thus the time complexity is O(n). The space complexity is also O(n).

#include<iostream>
#include<stack>
#include<vector>
#include<ctime> //time()
#include<cstdlib> //srand() and rand()

std::vector<int> nextLargerEle(std::vector<int> arr){
    if(arr.size()<=1)
        return arr;
    std::vector<int> ret(arr.size(), 0);
    std::stack<int> s;
    for(size_t i=0; i<arr.size(); ++i){
        while(!s.empty()&&arr[s.top()]<arr[i]){
            ret[s.top()]=arr[i];
            s.pop();
        }
        s.push(i);
    }
    while(!s.empty()){
        ret[s.top()]=arr[s.top()];
        s.pop();
    }
    return ret;
}

int main(){
    std::vector<int> ret;
    ret.reserve(10);
    srand(time(NULL));
    for(int i=0; i<10; ++i)
        ret.push_back(rand()%9);
        
    std::cout<<"Input: ";
    for(size_t i=0; i<ret.size(); ++i)
        std::cout << ret[i] <<" ";
    std::cout<< std::endl;
    ret = nextLargerEle(ret);
    
    std::cout<<"Output: ";
    for(size_t i=0; i<ret.size(); ++i)
        std::cout << ret[i] <<" ";
    std::cout<< std::endl;
    return 0;
}