In the Number of NGEs to the right problem we have given an array a[ ] of size n and q number of queries representing the index of the array. For each query, i print the total number of next greater elements to it’s right.
Table of Contents
Example
Input
a[ ] = {3, 4, 2, 7, 5, 8, 10, 6}
q1 = 0
q2 = 5
Output
4
1
Input
a[ ] = {1, 2, 3, 4, 5, 6, 7}
q1 = 0
Output
6
Naive Method
Algorithm
- Initialize an array a[ ] of size n.
- Create a variable c to count the NGEs and initialize it as 0.
- Create a variable lastEle and store the value of array a[ ] at index q i.e. query in it.
- Traverse from q+1 to n-1 and check if the value of array a[ ] at current index is greater than lastEle, update lastEle as the value of array a[ ] at the current index. Increment the count.
- Print the count.
C++ Program to count the number of NGEs to the right
#include <bits/stdc++.h>
using namespace std;
void count(int a[], int n, int q){
int c = 0;
int lastEle = a[q];
for(int i=q+1; i<n; i++){
if(a[i]>lastEle){
lastEle = a[i];
c++;
}
}
cout<<c<<endl;
}
int main(){
int a[] = {3, 4, 2, 7, 5, 8, 10, 6};
int n = sizeof(a) / sizeof(a[0]);
count(a, n, 0);
count(a, n, 5);
return 0;
}4 1
Java Program to count the number of NGEs to the right
import java.util.*;
class NGE{
static void count(int a[], int n, int q){
int c = 0;
int lastEle = a[q];
for(int i=q+1; i<n; i++){
if(a[i]>lastEle){
lastEle = a[i];
c++;
}
}
System.out.println(c);
}
public static void main(String args[]){
int a[] = {3, 4, 2, 7, 5, 8, 10, 6};
int n = a.length;
count(a, n, 0);
count(a, n, 5);
}
}4 1
Complexity Analysis
Time Complexity: O(n) where n is the size of array a[ ].
Auxiliary Space: O(1) because we used constant extra space.
Efficient Method
Algorithm
- Initialize an array a[ ] of size n containing numbers and a dp array of the same size.
- Create an array next[ ] of size n and set its element as 0.
- Create a stack and push 0 in it.
- Traverse from 1 to n-1 and while the stack is not empty check if the value in array a[ ] at the index equal to the top of the stack is less than the value in array a[ ] at current index, update the value in array next at the index equal to the top of the stack as a current index. Pop the top of the stack.
- Else break the loop.
- Push the current index in the stack.
- While stack is not empty update the value in array next at the index equal to the top of the stack as -1. Pop the top of the stack.
- Traverse through n-2 to 0 and check value in array next at current index is -1, update the value in array dp at current index as 0. Else update value in array next at current index as 1 + dp[next[i]].
- For each query equals to i print dp[I].
C++ Program to count the number of NGEs to the right
#include <bits/stdc++.h>
using namespace std;
void computeNext(int next[], int a[], int n){
stack<int> s;
s.push(0);
for(int i = 1; i < n; i++){
while(!s.empty()){
int cur = s.top();
if(a[cur] < a[i]){
next[cur] = i;
s.pop();
}
else{
break;
}
}
s.push(i);
}
while(!s.empty()){
int cur = s.top();
next[cur] = -1;
s.pop();
}
}
void count(int a[], int dp[], int n){
int next[n];
memset(next, 0, sizeof(next));
computeNext(next, a, n);
for(int i = n-2; i >= 0; i--){
if(next[i] == -1){
dp[i] = 0;
}
else{
dp[i] = 1 + dp[next[i]];
}
}
}
int answerQuery(int dp[], int index){
return dp[index];
}
int main(){
int a[] = {3, 4, 2, 7, 5, 8, 10, 6};
int n = sizeof(a) / sizeof(a[0]);
int dp[n];
count(a, dp, n);
cout<<answerQuery(dp, 0)<<endl;
cout<<answerQuery(dp, 5)<<endl;
return 0;
}4 1
Java Program to count the number of NGEs to the right
import java.util.*;
class NGE{
static void computeNext(int next[], int a[], int n){
Stack<Integer> s = new Stack<Integer>();
s.push(0);
for(int i = 1; i < n; i++){
while(s.size() > 0){
int cur = s.peek();
if(a[cur] < a[i]){
next[cur] = i;
s.pop();
}
else{
break;
}
}
s.push(i);
}
while(s.size() > 0){
int cur = s.peek();
next[cur] = -1;
s.pop();
}
}
static void count(int a[], int dp[], int n){
int next[] = new int[n];
for(int i = 0; i < n; i++){
next[i] = 0;
}
computeNext(next, a, n);
for(int i = n-2; i >= 0; i--){
if(next[i] == -1){
dp[i] = 0;
}
else{
dp[i] = 1 + dp[next[i]];
}
}
}
static int answerQuery(int dp[], int index){
return dp[index];
}
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];
count(a, dp, n);
System.out.println(answerQuery(dp, 0));
System.out.println(answerQuery(dp, 5));
}
}4 1
Complexity Analysis
Time Complexity: O(1) because all the queries are taking constant time due to pre-computations.
Auxiliary Space: O(n) where n is the size of array a[ ].