Last Updated: Mar 27, 2024

# Number of NGEs to the right

## 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:

1. Run a loop for every query q and start iterating over the array.
2. Start comparing the present index with the next index element.
3. Count the number of elements greater than the present index element and store the count value.
4. 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<>();
int n = a.size();
List<Integer> q = new ArrayList<>();

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).

## Optimized Approach

We can reduce the time complexity to find the number of the next greater elements by using merge sort like in the count inversion problem. For a pair of indexes (i, j), if i < j and arr[i] < arr[j], then the number of elements greater than i can be found through j. Let's see the algorithm in detail.

### Algorithm

The algorithm is as follows:

1. Create a vector, temp of size n, to store the number of next greater elements for each index. Initialize it with 0.

2. Create another vector, v, to store the pair of elements and their original indices. Populate v with elements from a and their indices.

3. Call the function mergesort; Inside the merge sort:
1. Calculate the middle index, mid, if low is less than high.

2. Recursively call the mergesort function for the left and right halves of the subarray.

3. Call the merge function to merge the sorted halves and count the number of the next greater elements.

4. Inside the merge function:
1. Create two arrays, a and b, and copy elements of the left and right halves into them.

2. Iterate through the two arrays and copy the smaller element into the original array.

3. If the element in a is smaller, that is for the case i < j and arr[i] < arr[j], update temp with count size2-j.

4. Do the above steps for the remaining elements of the array a or b.

5. Print the next greater elements of the given indices in the query array.

### Implementation in C++

``````#include <bits/stdc++.h>
using namespace std;

void merge(vector<pair<int, int> >& v, vector<int>& temp, int low, int mid, int high) {

int size1 = mid - low + 1;
int size2 = high - mid;

vector<pair<int, int> > a;
vector<pair<int, int> > b;

for (int i = 0; i < size1; i++) {
a.push_back(v[i + low]);
}

for (int i = 0; i < size2; i++) {
b.push_back(v[i + mid + 1]);
}

int i = 0, j = 0, k = low;

while (i < size1 && j < size2) {
if (a[i].first < b[j].first) {
temp[a[i].second] += size2 - j;
v[k++] = a[i++];
}
else {
v[k++] = b[j++];
}
}

while (i < size1) {
v[k++] = a[i++];
}

while (j < size2) {
v[k++] = b[j++];
}
}

void mergesort(vector<pair<int, int> >& v, vector<int>& temp, int low, int high) {
if (low < high) {
int mid = low + (high - low) / 2;
mergesort(v, temp, low, mid);
mergesort(v, temp, mid + 1, high);
merge(v, temp, low, mid, high);
}
}

int main(){
vector<int> a = {1, 3, 6, 5, 8, 9, 13, 4};
int n = a.size();

vector<int> q = {0, 1, 5};

vector<int> temp(n, 0);
vector<pair<int, int> > v;

for (int i = 0; i < n; i++) {
v.push_back({ a[i], i });
}

mergesort(v, temp, 0, n - 1);

for (int i = 0; i < q.size(); i++) {
int j = q[i];
cout<<temp[j]<<" ";
}

return 0;
}``````

### Implementation in Java

``````import java.util.*;

class Main {

static void merge(List<Map.Entry<Integer, Integer>> v, List<Integer> temp, int low, int mid, int high) {
int size1 = mid - low + 1;
int size2 = high - mid;

List<Map.Entry<Integer, Integer>> a = new ArrayList<>();
List<Map.Entry<Integer, Integer>> b = new ArrayList<>();

for (int i = 0; i < size1; i++) {
}

for (int i = 0; i < size2; i++) {
}

int i = 0, j = 0, k = low;

while (i < size1 && j < size2) {
if (a.get(i).getKey() < b.get(j).getKey()) {
temp.set(a.get(i).getValue(), temp.get(a.get(i).getValue()) + size2 - j);
v.set(k++, a.get(i++));
} else {
v.set(k++, b.get(j++));
}
}

while (i < size1) {
v.set(k++, a.get(i++));
}

while (j < size2) {
v.set(k++, b.get(j++));
}
}

static void mergeSort(List<Map.Entry<Integer, Integer>> v, List<Integer> temp, int low, int high) {
if (low < high) {
int mid = low + (high - low) / 2;
mergeSort(v, temp, low, mid);
mergeSort(v, temp, mid + 1, high);
merge(v, temp, low, mid, high);
}
}

public static void main(String[] args) {
List<Integer> a = Arrays.asList(1, 3, 6, 5, 8, 9, 13, 4);
int n = a.size();

List<Integer> q = Arrays.asList(0, 1, 5);

List<Integer> temp = new ArrayList<>(Collections.nCopies(n, 0));
List<Map.Entry<Integer, Integer>> v = new ArrayList<>();

for (int i = 0; i < n; i++) {
}

mergeSort(v, temp, 0, n - 1);

for (Integer j : q) {
System.out.print(temp.get(j) + " ");
}
}
}
``````

Output:

``7 6 1``

### Complexity Analysis

Time Complexity: Since we are using the merge sort approach to find the count of the next greater element for each index, the time complexity is O(n*logn).

Space complexity: The auxiliary space used is O(n) for n elements.

Also Read - Strong number in c

### What is dynamic programming?

It is the technique to solve a problem by breaking it down into smaller sets of problems and individually handling the smaller problems to achieve the optimal solution.

### What are the approaches of dynamic programming?

Top-down and bottom-up are the two types of approaches in dynamic programming.

### What is the major advantage of applying dynamic programming?

Dynamic programming is used because it can provide a local as well as a total optimal solution for the problem, which means that it chooses the best solution for the broken down problem part as well as for the overall solution.

## Conclusion

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

Check out this problem - Next Smaller Element

Refer to our guided paths on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must have a look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Topics covered
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Example
2.
Brute Force Approach
2.1.
Algorithm
2.2.
Implementation in C++
2.3.
Implementation in Java
2.4.
Complexity Analysis
3.
Optimized Approach
3.1.
Algorithm
3.2.
Implementation in C++
3.3.
Implementation in Java
3.4.
Complexity Analysis
4.