Home » Interview » Stack » Number of NGEs to the Right

Number of NGEs to the Right


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.

Number of NGEs to the Right

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

  1. Initialize an array a[ ] of size n.
  2. Create a variable c to count the NGEs and initialize it as 0.
  3. Create a variable lastEle and store the value of array a[ ] at index q i.e. query in it.
  4. 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.
  5. 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[ ].

READ  Check if an Array is Stack Sortable

Auxiliary Space: O(1) because we used constant extra space.

Efficient Method

Algorithm

  1. Initialize an array a[ ] of size n containing numbers and a dp array of the same size.
  2. Create an array next[ ] of size n and set its element as 0.
  3. Create a stack and push 0 in it.
  4. 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.
  5. Else break the loop.
  6. Push the current index in the stack.
  7. 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.
  8. 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]].
  9. 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.

READ  Find Maximum Sum Possible Equal Sum of Three Stacks

Auxiliary Space: O(n) where n is the size of array a[ ].

References