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].
Table of Contents
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
- Initialize an array a[ ] of size n and an array q[ ] of size m representing queries.
- 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[ ].
- 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
- Initialize an array a[ ] of size n and an array q[ ] of size m representing queries.
- Create an array next[ ] to store the next element a stack and push 0 in it.
- Traverse through 1 to n-1 and check if the stack is empty push current index or value of i in it.
- 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.
- 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.
- 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[ ].