Number of NGEs

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.

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)