Find all elements in an array which are greater than all elements present to its right

Given an array with n elements, find all the elements which are greater than all the elements to their right.

Test Cases

Example Input 1

Input: 10, 2, 4, 5, 8
Output: 10, 8
Explanation: In the above array only elements 10 and 8 are such that they are greater than all the elements to their right.

Example Input 2

Input: 20 10 5
Output: 20 10 5
Explanation: Since the above array is in descending order, all the elements are such that they are greater than all the elements to the right.

Solution

These kind of problems are easy to solve using a stack.
The idea is to store only the numbers which can be answers into the stack.

When we are iterating over the array, only one of the following three cases will be there :

1. The stack is empty: If stack is empty, we can directly push the current element to the top of the stack.
2. Current Top Of Stack > current element: In this case, the current top element of the stack is greater than our current element. Therefore, we push the current element onto the stack.
3. Current Top Of Stack <= current element: In this case, keep popping elements from the stack until either the stack becomes empty or the top of the stack becomes larger than current element

This algorithm can be implemented as follows :

#include <bits/stdc++.h>
using namespace std;

int main() {
    stack<int> st;
    vector<int> vec = { 10, 2, 4, 5, 8 };
    for(int i = 0; i < vec.size(); i++) {
        if (st.size() == 0 || st.top() > vec[i]) {
            st.push(vec[i]);
        }
        else {
            while (st.size() > 0 && st.top() <= vec[i]) {
                st.pop();
            }
            st.push(vec[i]);
        }
    }

    vector<int> ans;
    while (!st.empty()) {
        ans.push_back(st.top());
        st.pop();
    }
    for(int i = 0; i < ans.size(); i++) cout << ans[i] << " ";
    cout << "\n";
}