# Number of NGEs to the right

Given an array of n integers and q queries, print the number of next greater elements to the right of the given index element.

Examples:

```Input : a[] = {3, 4, 2, 7, 5, 8, 10, 6}
q = 2
index = 0,
index = 5
Output: 4
1
Explanation: the next greater elements
to the right of 3(index 0) are 4, 7, 8,
10. The next greater elements to the right
of 8(index 5) are 10.```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

A naive approach is to iterate for every query from index to end, and find out the number of next greater elements to the right. This won’t be efficient enough as we run two nested loops .

Time complexity: O(n) to answer a query.
Auxiliary space: O(1)

Better approach is to store the next greater index of every element and run a loop for every query that iterates from index and keeping the increasing counter as j = next[i]. This will avoid checking all elements and will directly jump to the next greater element of every element. But this won’t be efficient enough in cases like 1 2 3 4 5 6, where the next greater elements are sequentially increasing, ending it up in taking O(n) for every query.

Time complexity : O(n) to answer a query.
Auxiliary space : O(n) for next greater element.

Efficient approach is to store the next greater elements index using next greater element in a next[] array. Then create a dp[] array that starts from n-2, as n-1th index will have no elements to its right and dp[n-1] = 0. While traversing from back we use dynamic programming to count the number of elements to the right where we use memoization as dp[next[i]] which gives us a count of the numbers to the right of the next greater element of the current element, hence we add 1 to it. If next[i]=-1 then we do not have any element to the right hence dp[i]=0. dp[index] stores the count of the number of next greater elements to the right.

Below is the implementation of the above approach.

## C++

 `#include ` `using` `namespace` `std; ` ` `  `// array to store the next greater element index ` `void` `fillNext(``int` `next[], ``int` `a[], ``int` `n) ` `{ ` `    ``// use of stl stack in c++ ` `    ``stack<``int``> s; ` ` `  `    ``// push the 0th index to the stack ` `    ``s.push(0); ` ` `  `    ``// traverse in the loop from 1-nth index ` `    ``for` `(``int` `i = 1; i < n; i++) { ` ` `  `        ``// iterate till loop is empty ` `        ``while` `(!s.empty()) { ` ` `  `            ``// get the topmost index in the stack ` `            ``int` `cur = s.top(); ` ` `  `            ``// if the current element is greater ` `            ``// then the top index-th element, then ` `            ``// this will be the next greatest index ` `            ``// of the top index-th element ` `            ``if` `(a[cur] < a[i]) { ` ` `  `                ``// initialize the cur index position's ` `                ``// next greatest as index ` `                ``next[cur] = i; ` ` `  `                ``// pop the cur index as its greater ` `                ``// element has been found ` `                ``s.pop(); ` `            ``} ` ` `  `            ``// if not greater then break ` `            ``else` `                ``break``; ` `        ``} ` ` `  `        ``// push the i index so that its next greatest ` `        ``// can be found ` `        ``s.push(i); ` `    ``} ` ` `  `    ``// iterate for all other index left inside stack ` `    ``while` `(!s.empty()) { ` ` `  `        ``int` `cur = s.top(); ` ` `  `        ``// mark it as -1 as no element in greater ` `        ``// then it in right ` `        ``next[cur] = -1; ` ` `  `        ``s.pop(); ` `    ``} ` `} ` ` `  `// function to count the number of next greater numbers to the right ` `void` `count(``int` `a[], ``int` `dp[], ``int` `n) ` `{ ` `    ``// initializes the next array as 0 ` `    ``int` `next[n]; ` `    ``memset``(next, 0, ``sizeof``(next)); ` ` `  `    ``// calls the function to pre-calculate ` `    ``// the next greatest element indexes ` `    ``fillNext(next, a, n); ` ` `  `    ``for` `(``int` `i = n - 2; i >= 0; i--) { ` ` `  `        ``// if the i-th element has no next ` `        ``// greater element to right ` `        ``if` `(next[i] == -1) ` `            ``dp[i] = 0; ` ` `  `        ``// Count of next greater numbers to right. ` `        ``else` `            ``dp[i] = 1 + dp[next[i]]; ` `    ``} ` `} ` ` `  `// answers all queries in O(1) ` `int` `answerQuery(``int` `dp[], ``int` `index) ` `{ ` `    ``// returns the number of next greater ` `    ``// elements to the right. ` `    ``return` `dp[index]; ` `} ` ` `  `// driver program to test the above function ` `int` `main() ` `{ ` `    ``int` `a[] = { 3, 4, 2, 7, 5, 8, 10, 6 }; ` `    ``int` `n = ``sizeof``(a) / ``sizeof``(a[0]); ` ` `  `    ``int` `dp[n]; ` ` `  `    ``// calls the function to count the number ` `    ``// of greater elements to the right for ` `    ``// every element. ` `    ``count(a, dp, n); ` ` `  `    ``// query 1 answered ` `    ``cout << answerQuery(dp, 3) << endl; ` ` `  `    ``// query 2 answered ` `    ``cout << answerQuery(dp, 6) << endl; ` ` `  `    ``// query 3 answered ` `    ``cout << answerQuery(dp, 1) << endl; ` ` `  `    ``return` `0; ` `} `

## Java

 `// Java program to print number of NGEs to the right ` `import` `java.util.*; ` ` `  `class` `GFG ` `{ ` ` `  `// array to store the next greater element index ` `static` `void` `fillNext(``int` `next[], ``int` `a[], ``int` `n) ` `{ ` `    ``// Use stack ` `    ``Stack s = ``new` `Stack(); ` ` `  `    ``// push the 0th index to the stack ` `    ``s.push(``0``); ` ` `  `    ``// traverse in the loop from 1-nth index ` `    ``for` `(``int` `i = ``1``; i < n; i++)  ` `    ``{ ` ` `  `        ``// iterate till loop is empty ` `        ``while` `(s.size() > ``0``)  ` `        ``{ ` ` `  `            ``// get the topmost index in the stack ` `            ``int` `cur = s.peek(); ` ` `  `            ``// if the current element is greater ` `            ``// then the top index-th element, then ` `            ``// this will be the next greatest index ` `            ``// of the top index-th element ` `            ``if` `(a[cur] < a[i]) ` `            ``{ ` ` `  `                ``// initialize the cur index position's ` `                ``// next greatest as index ` `                ``next[cur] = i; ` ` `  `                ``// pop the cur index as its greater ` `                ``// element has been found ` `                ``s.pop(); ` `            ``} ` ` `  `            ``// if not greater then break ` `            ``else` `                ``break``; ` `        ``} ` ` `  `        ``// push the i index so that its next greatest ` `        ``// can be found ` `        ``s.push(i); ` `    ``} ` ` `  `    ``// iterate for all other index left inside stack ` `    ``while` `(s.size() > ``0``)  ` `    ``{ ` ` `  `        ``int` `cur = s.peek(); ` ` `  `        ``// mark it as -1 as no element in greater ` `        ``// then it in right ` `        ``next[cur] = -``1``; ` ` `  `        ``s.pop(); ` `    ``} ` `} ` ` `  `// function to count the number of  ` `// next greater numbers to the right ` `static` `void` `count(``int` `a[], ``int` `dp[], ``int` `n) ` `{ ` `    ``// initializes the next array as 0 ` `    ``int` `next[] = ``new` `int``[n]; ` `    ``for``(``int` `i = ``0``; i < n; i++) ` `    ``next[i] = ``0``; ` `     `  `    ``// calls the function to pre-calculate ` `    ``// the next greatest element indexes ` `    ``fillNext(next, a, n); ` ` `  `    ``for` `(``int` `i = n - ``2``; i >= ``0``; i--)  ` `    ``{ ` ` `  `        ``// if the i-th element has no next ` `        ``// greater element to right ` `        ``if` `(next[i] == -``1``) ` `            ``dp[i] = ``0``; ` ` `  `        ``// Count of next greater numbers to right. ` `        ``else` `            ``dp[i] = ``1` `+ dp[next[i]]; ` `    ``} ` `} ` ` `  `// answers all queries in O(1) ` `static` `int` `answerQuery(``int` `dp[], ``int` `index) ` `{ ` `    ``// returns the number of next greater ` `    ``// elements to the right. ` `    ``return` `dp[index]; ` `} ` ` `  `// driver code ` `public` `static` `void` `main(String args[]) ` `{ ` `    ``int` `a[] = { ``3``, ``4``, ``2``, ``7``, ``5``, ``8``, ``10``, ``6` `}; ` `    ``int` `n = a.length; ` ` `  `    ``int` `dp[] = ``new` `int``[n]; ` ` `  `    ``// calls the function to count the number ` `    ``// of greater elements to the right for ` `    ``// every element. ` `    ``count(a, dp, n); ` ` `  `    ``// query 1 answered ` `    ``System.out.println(answerQuery(dp, ``3``)); ` ` `  `    ``// query 2 answered ` `    ``System.out.println( answerQuery(dp, ``6``)); ` `     `  `    ``// query 3 answered ` `    ``System.out.println( answerQuery(dp, ``1``) ); ` ` `  `} ` `} ` ` `  `// This code is contributed by Arnab Kundu `

## C#

 `// C# program to print number of  ` `// NGEs to the right ` `using` `System; ` `using` `System.Collections; ` ` `  `class` `GFG ` `{ ` ` `  `// array to store the next greater element index ` `static` `void` `fillNext(``int` `[]next, ``int` `[]a, ``int` `n) ` `{ ` `    ``// Use stack ` `    ``Stack s = ``new` `Stack(); ` ` `  `    ``// Push the 0th index to the stack ` `    ``s.Push(0); ` ` `  `    ``// traverse in the loop from 1-nth index ` `    ``for` `(``int` `i = 1; i < n; i++)  ` `    ``{ ` ` `  `        ``// iterate till loop is empty ` `        ``while` `(s.Count > 0)  ` `        ``{ ` ` `  `            ``// get the topmost index in the stack ` `            ``int` `cur = (``int``)s.Peek(); ` ` `  `            ``// if the current element is greater ` `            ``// then the top index-th element, then ` `            ``// this will be the next greatest index ` `            ``// of the top index-th element ` `            ``if` `(a[cur] < a[i]) ` `            ``{ ` ` `  `                ``// initialize the cur index position's ` `                ``// next greatest as index ` `                ``next[cur] = i; ` ` `  `                ``// Pop the cur index as its greater ` `                ``// element has been found ` `                ``s.Pop(); ` `            ``} ` ` `  `            ``// if not greater then break ` `            ``else` `                ``break``; ` `        ``} ` ` `  `        ``// Push the i index so that its next  ` `        ``// greatest can be found ` `        ``s.Push(i); ` `    ``} ` ` `  `    ``// iterate for all other index  ` `    ``// left inside stack ` `    ``while` `(s.Count > 0)  ` `    ``{ ` ` `  `        ``int` `cur =(``int``) s.Peek(); ` ` `  `        ``// mark it as -1 as no element in  ` `        ``// greater then it in right ` `        ``next[cur] = -1; ` ` `  `        ``s.Pop(); ` `    ``} ` `} ` ` `  `// function to count the number of  ` `// next greater numbers to the right ` `static` `void` `count(``int` `[]a, ``int` `[]dp, ``int` `n) ` `{ ` `    ``// initializes the next array as 0 ` `    ``int` `[]next = ``new` `int``[n]; ` `    ``for``(``int` `i = 0; i < n; i++) ` `        ``next[i] = 0; ` `     `  `    ``// calls the function to pre-calculate ` `    ``// the next greatest element indexes ` `    ``fillNext(next, a, n); ` ` `  `    ``for` `(``int` `i = n - 2; i >= 0; i--)  ` `    ``{ ` ` `  `        ``// if the i-th element has no next ` `        ``// greater element to right ` `        ``if` `(next[i] == -1) ` `            ``dp[i] = 0; ` ` `  `        ``// Count of next greater numbers to right. ` `        ``else` `            ``dp[i] = 1 + dp[next[i]]; ` `    ``} ` `} ` ` `  `// answers all queries in O(1) ` `static` `int` `answerQuery(``int` `[]dp, ``int` `index) ` `{ ` `    ``// returns the number of next greater ` `    ``// elements to the right. ` `    ``return` `dp[index]; ` `} ` ` `  `// Driver code ` `public` `static` `void` `Main(String []args) ` `{ ` `    ``int` `[]a = { 3, 4, 2, 7, 5, 8, 10, 6 }; ` `    ``int` `n = a.Length; ` ` `  `    ``int` `[]dp = ``new` `int``[n]; ` ` `  `    ``// calls the function to count the number ` `    ``// of greater elements to the right for ` `    ``// every element. ` `    ``count(a, dp, n); ` ` `  `    ``// query 1 answered ` `    ``Console.WriteLine(answerQuery(dp, 3)); ` ` `  `    ``// query 2 answered ` `    ``Console.WriteLine( answerQuery(dp, 6)); ` `     `  `    ``// query 3 answered ` `    ``Console.WriteLine( answerQuery(dp, 1)); ` `} ` `} ` ` `  `// This code is contributed by Arnab Kundu `

Output:

```2
0
3
```

Time complexity: O(1) to answer a query.
Auxiliary Space: O(n)