Number of NGEs to the Right

Last Updated on September 13, 2022 by Gokul Kannan

Problem Statement

You will be given an array of N integers. You will also be given an Integer Q denoting the number of queries.
Then, you will have Q queries denoting the indices of the array. You have to return Q integers for those Q queries depicting the number of elements that are greater than the index mentioned in the query and are to the right of the index in the array i.e. Number of NGEs to the Right where NGE stands for “Next Greater Element”.

Example

Let us take an array and the queries as shown below

Q=2 , means 2 queries.
Let us say they are 2 and 1.

1. For index =2, answer is 2, because there are two elements in right of index 2 with value greater than array[2]=4 {6 and 7}
2. For index =1, answer is 0, because there is no element on right of index 1 with value greater than array[1] = 9.

Also, you might notice that the count of NGEs to the right of the element present at the last index in the array will always be 0. This is because there will not be any element at the right of it and thus NGEs to its right won’t exist.

Approach (Brute Force)

The approach is very simple. Let us consider the array shown below and let us say we want to find the number of next greater elements for index 2.

• Let us keep a counter variable initialised to 0.
• Let us also keep a variable (pointer) i at index = query index + 1.
• So, we keep i at index = 3.
• Now, iterate till we reach the end of the array and for each index, if array[i] > array[query index], then increment the value of the counter variable.

This is how one query will be solved. Since there are multiple queries, we have to repeat this procedure for all those queries where each query can have a different index.

The image below shows the dry run for one Query where index = 2.

So, two elements were found greater than array[2] = 4, which are array[3] = 6 and array[5] = 7. So, the answer to this query is 2.

The same procedure will be followed for any other query as well.

Corner Case: If the query index = size of the array -1, in this case, we will not iterate as i+1 will not be less than the size of the array rather it will be equal to it. So, the counter will remain 0 only and without iterating, we will get the answer correctly.

Now that we have understood the procedure, let us write the code for the same.

Code Implementation:

#include 
using namespace std;

int countNGE(vector& a, int index)
{
	int count = 0, N = a.size();
	for (int i = index + 1; i < N; i++)
		if (a[i] > a[index])
			count++;

	return count;
}

int main()
{
	int N;
	cin >> N;

    vector arr(N);
	
	for(int i=0;i> arr[i];
	}
	
	int Q;
	cin >> Q;
	
	while(Q--) {
	    int idx;
	    cin >> idx;
	    
	    int res = countNGE(arr,idx);
	    cout<< res << "\n";
	}
}

import java.util.*;

public class Main {
    
    public static int countNGE(int[] arr, int idx) {
        
        int count = 0;
        
        for(int i=idx + 1;i<arr.length;i++) {
            if(arr[i] > arr[idx]) count++;
        }
        
        return count;
    }
    
    public static void main(String[] args) {
        Scanner scn = new Scanner(System.in);
        int n = scn.nextInt();
        int[] arr = new int[n];
        
        for(int i=0;i<n;i++) {
            arr[i] = scn.nextInt();
        }
        
        int Q = scn.nextInt();
        
        while(Q-- > 0) {
            int idx = scn.nextInt();
            int res = countNGE(arr,idx);
            System.out.println(res);
        }
        
        scn.close();
    }
}

Time Complexity: The time complexity of this approach is O(N) in the average and the worst case for one query because we have to traverse every element to the right of the input index. In the best case, the time complexity for 1 query will be O(1), when the query index = size of array -1.
However, for Q queries, the worst and average case time complexity is O(N * Q).

Space Complexity: Since we have not used any extra space, the auxiliary space is O(1).

So, this is how we can find out the number of NGEs to the right of an element.

This article tried to discuss Number of NGEs to the Right. Hope this blog helps you understand and solve the problem. To practice more problems you can check out MYCODE | Competitive Programming at PrepBytes.