DSA

Number of NGEs

Solution - 2 Stacks approach. Optimal — Time O(n), Space O(n).

August 8, 2026
PatternMonotonic StackOptimalO(n) time · O(n) space
Solve on GeeksforGeeks
Key insighttry it first, then reveal

The intuition is to count how many elements in the "right portion" of the array are strictly greater than the current element.

Practice Link

Given an array of N integers and Q queries of indices. For each query indices[i], determine the count of elements in arr that are strictly greater than arr[indices[i]] to its right (after the position indices[i]).

Solution - 2 Stacks#

The intuition is to count how many elements in the "right portion" of the array are strictly greater than the current element. A monotonically decreasing stack (descStk) holds the right elements in sorted order — its size at any point directly equals the number of elements greater than the current value. However, when inserting a new element, smaller elements that are popped must be preserved (since they are still NGEs for earlier positions), so a second ascending stack (ascStk) temporarily holds them and pushes them back after insertion. For each index i, mp[i] = descStk.size() records the count of NGEs, and queries are answered in O(1) with the map.

cpp
vector<int> count_NGE(int n, vector<int> &arr, int queries, vector<int> &indices){
        stack<int> descStk;
        stack<int> ascStk;
        unordered_map<int,int> mp; // index - numbeer of NGE
        
        for(int i=n-1;i>=0;i--)
        {
            while(!descStk.empty() && descStk.top() <= arr[i])
            {
                ascStk.push(descStk.top());
                descStk.pop();
            }
            mp[i] = descStk.size();
            descStk.push(arr[i]);
            
            while(!ascStk.empty()){
                descStk.push(ascStk.top());
                ascStk.pop();
            }
        }
        vector<int> ans;
        for(int i=0;i<indices.size();i++)
        {
            int idx = indices[i];
            ans.push_back(mp[idx]);
        }
        return ans;
       
    }

Time Complexity: O(n)

Space Complexity: O(n)