# Print Next Greater Number of Q queries

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

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].

## 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 »