DSA
Number of NGEs
Solution - 2 Stacks approach. Optimal — Time O(n), Space O(n).
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.
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)