## Introduction

In this blog, we will look at the approach to print the number of next greater elements to the right of the given index element.

### Problem Statement

**Given: **An array of n integers and q queries.

**Problem: **Print the number of next greater elements to the right of the given index element.

### Sample Example

Let us look at the following example to understand the requirements of the problem.

**Input: **ar[ ] = {1, 3, 6, 5, 8, 9, 13, 4}, q = 3, index = 0, index = 1 and index = 5

**Output: **7 6 1

**Explanation:** The next greater elements to the right of 1, index = 0 are { 3, 6, 5, 8, 9, 13, 4}. The next greater elements to the right of 3, index = 1 are {6, 5, 8, 9, 13, 4}. The next greater elements to the right of 9, index = 5 is {13}.

## Brute Force Approach

In this approach, we will iterate for every query from index to the end and find out the number of next greater elements to the right.

### Algorithm

The algorithm for the problem is:

- Run a loop for every query q and start iterating over the array.
- Start comparing the present index with the next index element.
- Count the number of elements greater than the present index element and store the count value.
- Repeat the same iteration for all the number of queries and print the count values.

### Implementation in C++

```
#include <bits/stdc++.h>
using namespace std;
int count(vector<int> &a, int n, int index){
int count = 0;
for(int i=index+1; i<n; i++){
if(a[i] > a[index]) count++;
}
return count;
}
int main(){
vector<int> a = {1, 3, 6, 5, 8, 9, 13, 4};
int n = a.size();
vector<int> q = {0, 1, 5};
for(int i=0; i<q.size(); i++){
cout<<count(a, n, q[i])<<" ";
}
return 0;
}
```

### Implementation in Java

```
import java.util.ArrayList;
import java.util.List;
public class Main {
public static int count(List<Integer> a, int n, int index) {
int count = 0;
for (int i = index + 1; i < n; i++) {
if (a.get(i) > a.get(index))
count++;
}
return count;
}
public static void main(String[] args) {
List<Integer> a = new ArrayList<>();
a.add(1);
a.add(3);
a.add(6);
a.add(5);
a.add(8);
a.add(9);
a.add(13);
a.add(4);
int n = a.size();
List<Integer> q = new ArrayList<>();
q.add(0);
q.add(1);
q.add(5);
for (int i = 0; i < q.size(); i++) {
System.out.print(count(a, n, q.get(i)) + " ");
}
}
}
```

**Output:**

`7 6 1`

### Complexity Analysis

**Time Complexity:** Here, we have used two loops, one to iterate over all the queries and the other to find greater elements to the right of each query index. Hence the time complexity is O(n*q).

**Space complexity:** The auxiliary space used is O(1).