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

In this tutorial, we will write a code to display the greater number of Q queries in an array in C++. What this means is that, say we have an array with elements. The next greater element for a particular element means that if we have a value, say ‘i’, the right side of ‘i in the array, having larger value is the next greater element. If it’s the last element, then the next greater element is -1.

Say we have an array { 3,8,1,10}. The next greater element for 3 is 8, for 8 is 10, for 1 is 10. Since 10 has no next element, it’s next greater is -1.

There are many ways to implement this. One way is by using loops, but it is not very efficient. For an efficient code, we make use of stacks.

Let us see that with a C++ program to execute it using stacks.

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

void nge(int a[], int n) { 
  stack < int > s; 
  
  s.push(a[0]); 
  
  for (int idx = 1; idx < n; idx++) { 
  
    if (s.empty()) { 
      s.push(a[idx]); 
      continue; 
    } 
  

    while (s.empty() == false && s.top() < a[i]) 
    {          
        cout << s.top() << " - next greater is - " << a[i] << endl; 
        s.pop(); 
    } 
  

    s.push(a[i]); 
  } 

  while (s.empty() == false) { 
    cout << s.top() << " --> " << -1 << endl; 
    s.pop(); 
  } 
}

In the above function, we push the first element into the stack. Once done, we start a loop and mark the current element as next. Then we check if any value is there or not. If the stack is not empty, we then compare the top element of stack with next. If found larger than the top element, we pop the element from the stack. We continue this process of array pop. In the end, push the next in the stack.

Once the loop ends, pop all the elements from the stack and print -1 as the next element for the last one. Now, define the main() function.

int main() { 
  int a[] = {3,8,1,10}; 
  int n = sizeof(a) / sizeof(a[0]); 
  nge(a, n); 
  return 0; 
}

We get the output as:

3 – next greater is – 8
1 – next greater is – 10
8 – next greater is – 10
10 –> -1


This is how we print the next greater number of Q queries in an array. I hope this tutorial was helpful.

Leave a Reply

Your email address will not be published. Required fields are marked *