Print Next Greater Number of Q queries

Difficulty Level Medium
Frequently asked in Amazon Factset Fanatics
Array StackViews 1249

In Print Next Greater Number of Q queries problem we have given an array a[ ] of size n containing numbers and another array q[ ] of size m representing queries. Each query represents the index in array a[ ]. For each query, i print the number from the array a[ ]  that is next greater to the number at index q[i].

Print Next Greater Number of Q queries

Example

Input 

a[ ] = {3, 4, 2, 7, 5, 8, 10, 6}

q[ ] = {3, 6, 1}

Output

8 -1 7

Input 

a[ ] = {4, 7, 9, 8}

q[ ] = {1, 2}

Output

9 -1

Naive Method

Algorithm

  1. Initialize an array a[ ] of size n and an array q[ ] of size m representing queries.
  2. Traverse from 0 to m-1 and create an inner loop from q[i]+1 to n-1. Check if element at current index of array a[ ] is greater than element at index equal to q[i], print the element at current index in array a[ ].
  3. If there is no greater element left in the array after the element at query index print -1.

C++ Program to print next greater number of Q queries

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

void next_greatest(int a[], int n, int q[], int m){ 
    
    for(int i=0; i<m; i++){
        
        for(int j=q[i]+1; j<n; j++){
            
            if(a[j]>a[q[i]]){
                cout<<a[j]<<" ";
                break;
            }
            
            if(j==n-1){
                cout<<"-1 ";
            }
        }
    }
} 

int main(){ 
    int a[] = {3, 4, 2, 7, 5, 8, 10, 6}; 
    int n = sizeof(a) / sizeof(a[0]); 
    
    int q[] = {3, 6, 1}; 
    int m = sizeof(q) / sizeof(q[0]); 
    
    next_greatest(a, n, q, m);
    
    return 0;
}
8 -1 7

Java Program to print next greater number of Q queries

import java.util.*;

class nextGreatest{
    
    static void next_greatest(int[] a, int n, int[] q, int m){ 
    
        for(int i=0; i<m; i++){
            
            for(int j=q[i]+1; j<n; j++){
                
                if(a[j]>a[q[i]]){
                    System.out.print(a[j]+" ");
                    break;
                }
                
                if(j==n-1){
                    System.out.print("-1 ");
                }
            }
        }
    } 

  public static void main (String[] args){
      
    int[] a = {3, 4, 2, 7, 5, 8, 10, 6}; 
        int n = a.length; 
        
        int[] q = {3, 6, 1}; 
        int m = q.length; 
        
        next_greatest(a, n, q, m);
  }
}
8 -1 7

Complexity Analysis

Time Complexity: O(m*n) where n is the number of elements in the array a[ ] and m is the number of elements in array q[ ].

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

Efficient Method

Algorithm

  1. Initialize an array a[ ] of size n and an array q[ ] of size m representing queries.
  2. Create an array next[ ] to store the next element a stack and push 0 in it.
  3. Traverse through 1 to n-1 and check if the stack is empty push current index or value of i in it.
  4. Else while the stack is not empty check if the element in array a[ ] at current index is greater than or equal to the element at index top of the stack, update-index equals to top of the stack of array next[ ] as a current index and pop the top, else break the loop.
  5. Traverse again while the stack is not empty update-index equals to top of a stack of array next[ ] as -1 and pop the top.
  6. Traverse from 0 to m-1 and print the element from array a[ ] corresponding to the index stored in array next[ ] at position equals to q[i].

C++ Program to print next greater number of Q queries

#include <bits/stdc++.h> 
using namespace std; 
void next_greatest(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 answer_query(int a[], int next[], int n, int q[], int m){ 
    for(int i=0; i<m; i++){
        int position = next[q[i]]; 
      
        if(position == -1){ 
            cout<<-1<<" "; 
        }    
      
        else{
            cout<<a[position]<<" ";
        }    
    }
} 
  
int main(){ 
  
    int a[] = {3, 4, 2, 7, 5, 8, 10, 6}; 
    int n = sizeof(a) / sizeof(a[0]); 
    
    int q[] = {3, 6, 1};
    int m = sizeof(q) / sizeof(q[0]); 
  
    int next[n] = { 0 }; 
  
    next_greatest(next, a, n); 
  
    answer_query(a, next, n, q, m); 
 
    return 0; 
}
8 -1 7

Java Program to print next greater number of Q queries

import java.util.*; 

class NextGreatest{ 
    public static int[] next_greatest(int a[], int q[]){ 
        int ans[] = new int[a.length];
        
        Stack<Integer> s = new Stack<>(); 
        s.push(a[0]); 
        int j = 0; 
        for(int i = 1; i < a.length; i++){ 
            int next = a[i]; 
            
            if(!s.isEmpty()){ 
                int element = s.pop(); 
                
                while(next > element){ 
                    ans[j] = next; 
                    j++; 
                    if(s.isEmpty()) 
                        break; 
                    element = s.pop(); 
                } 
                
                if(element > next) 
                    s.push(element); 
            } 
            s.push(next); 
        }
        
        while(!s.isEmpty()){ 
            int element = s.pop(); 
            ans[j] = -1; 
            j++; 
        } 
        
        return ans; 
    } 
    
    public static void main(String[] args){ 
        int a[] = {3, 4, 2, 7, 5, 8, 10, 6}; 
        int q[] = {3, 6, 1}; 
        int ans[] = next_greatest(a,q); 
        
        for(int i = 0; i<q.length; i++){ 
            System.out.print(ans[q[i]] + " "); 
        } 
    } 
}
8 -1 7

Complexity Analysis

Time Complexity: max(O(n), O(m)),  O(n) to pre-process the array for next elements and each query requires constant time i.e. O(1).

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

References

Translate »