Print next greater number of Q queries
Last Updated :
21 Oct, 2023
Given an array of n elements and q queries, for each query that has index i, find the next greater element and print its value. If there is no such greater element to its right then print -1.
Examples:
Input : arr[] = {3, 4, 2, 7, 5, 8, 10, 6}
query indexes = {3, 6, 1}
Output: 8 -1 7
Explanation :
For the 1st query index is 3, element is 7 and
the next greater element at its right is 8
For the 2nd query index is 6, element is 10 and
there is no element greater than 10 at right,
so print -1.
For the 3rd query index is 1, element is 4 and
the next greater element at its right is 7.
Normal Approach: A normal approach will be for every query to move in a loop from index to n and find out the next greater element and print it, but this in the worst case will take n iterations, which is a lot if the number of queries are high.
Steps to implement-
- Run a loop for taking each query one by one
- Initialize a boolean variable as false to check whether the next greater element for any query exists or not
- Run a loop from the next index as given in the query to the last
- If we will get the next greater element then print that and make the boolean variable true, to indicate next greater element exists and break that inner loop
- After the inner loop, if the boolean variable is false then its next greater element doesn’t exist. So print -1 for that
Code-
C++
#include <bits/stdc++.h>
using namespace std;
void next_greater(int arr[],int query[], int n,int q)
{
for(int i=0;i<q;i++){
int k=query[i];
bool val=false;
for(int j=k+1;j<n;j++){
if(arr[j]>arr[k]){
cout<<arr[j]<<" ";
val=true;
break;
}
}
if(val==false){
cout<<-1<<" ";
}
}
}
int main()
{
int arr[] = {3, 4, 2, 7,5, 8, 10, 6 };
int query[]={3,6,1};
int n = sizeof(arr) / sizeof(arr[0]);
int q= sizeof(query) / sizeof(query[0]);
next_greater(arr,query,n,q);
}
|
Java
import java.util.Arrays;
public class GFG {
public static void nextGreater(int[] arr, int[] query) {
int n = arr.length;
int q = query.length;
for (int i = 0; i < q; i++) {
int k = query[i];
boolean val = false;
for (int j = k + 1; j < n; j++) {
if (arr[j] > arr[k]) {
System.out.print(arr[j] + " ");
val = true;
break;
}
}
if (!val) {
System.out.print(-1 + " ");
}
}
}
public static void main(String[] args) {
int[] arr = { 3, 4, 2, 7, 5, 8, 10, 6 };
int[] query = { 3, 6, 1 };
int n = arr.length;
int q = query.length;
nextGreater(arr, query);
}
}
|
Python
def next_greater_elements(arr, query):
results = []
for k in query:
val = False
for j in range(k + 1, len(arr)):
if arr[j] > arr[k]:
results.append(str(arr[j]))
val = True
break
if not val:
results.append("-1")
print(" ".join(results))
arr = [3, 4, 2, 7, 5, 8, 10, 6]
query = [3, 6, 1]
next_greater_elements(arr, query)
|
C#
using System;
class GFG {
static void NextGreater(int[] arr, int[] query, int n,
int q)
{
for (int i = 0; i < q; i++) {
int k = query[i];
bool val = false;
for (int j = k + 1; j < n; j++) {
if (arr[j] > arr[k]) {
Console.Write(arr[j] + " ");
val = true;
break;
}
}
if (val == false) {
Console.Write(-1 + " ");
}
}
}
static void Main(string[] args)
{
int[] arr = { 3, 4, 2, 7, 5, 8, 10, 6 };
int[] query = { 3, 6, 1 };
int n = arr.Length;
int q = query.Length;
NextGreater(arr, query, n, q);
}
}
|
Javascript
function GFG(arr, query) {
const results = [];
for (let i = 0; i < query.length; i++) {
const k = query[i];
let val = false;
for (let j = k + 1; j < arr.length; j++) {
if (arr[j] > arr[k]) {
results.push(arr[j].toString());
val = true;
break;
}
}
if (!val) {
results.push("-1");
}
}
console.log(results.join(" "));
}
const arr = [3, 4, 2, 7, 5, 8, 10, 6];
const query = [3, 6, 1];
GFG(arr, query);
|
Output-
8 -1 7
Time Complexity: O(n^2) ,because of two nested loops
Auxiliary Space>: O(1) , because no extra space has been used
Efficient Approach:
An efficient approach is based on next greater element. We store the index of the next greater element in an array and for every query process, answer the query in O(1) that will make it more efficient.
But to find out the next greater element for every index in array there are two ways.
One will take o(n^2) and O(n) space which will be to iterate from I+1 to n for each element at index I and find out the next greater element and store it.
But the more efficient one will be to use stack, where we use indexes to compare and store in next[] the next greater element index.
1) Push the first index to stack.
2) Pick rest of the indexes one by one and follow following steps in loop.
….a) Mark the current element as i.
….b) If stack is not empty, then pop an index from stack and compare a[index] with a[I].
….c) If a[I] is greater than the a[index], then a[I] is the next greater element for the a[index].
….d) Keep popping from the stack while the popped index element is smaller than a[I]. a[I] becomes the next greater element for all such popped elements
….g) If a[I] is smaller than the popped index element, then push the popped index back.
3) After the loop in step 2 is over, pop all the index from stack and print -1 as next index for them.
C++
#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();
}
}
int answer_query(int a[], int next[],
int n, int index)
{
int position = next[index];
if (position == -1)
return -1;
else
return a[position];
}
int main()
{
int a[] = {3, 4, 2, 7,
5, 8, 10, 6 };
int n = sizeof(a) / sizeof(a[0]);
int next[n] = { 0 };
next_greatest(next, a, n);
cout << answer_query(a, next, n, 3) << " ";
cout << answer_query(a, next, n, 6) << " ";
cout << answer_query(a, next, n, 1) << " ";
}
|
Java
import java.util.*;
class GFG
{
public static int[] findGreaterElements(int arr[]) {
int ans[] = new int[arr.length];
Stack<Integer> s = new Stack<>();
s.push(arr[arr.length - 1]);
ans[arr.length - 1] = -1;
for (int i = arr.length - 2; i >= 0; i--) {
int curr = arr[i];
if (s.isEmpty()) {
ans[i] = -1;
} else {
if (s.peek() <= curr) {
while (s.peek() <= curr) {
s.pop();
if (s.isEmpty()) {
break;
}
}
if (s.isEmpty()) {
ans[i] = -1;
} else {
ans[i] = s.peek();
}
} else {
ans[i] = s.peek();
}
s.push(curr);
}
}
return ans;
}
public static void main(String[] args) {
int arr[] = {3, 4, 2, 7,
5, 8, 10, 6};
int query[] = {3, 6, 1};
int ans[] = findGreaterElements(arr);
for(int i = 0; i < query.length; i++) {
System.out.print(ans[query[i]] + " ");
}
}
}
|
Python3
def next_greatest(next, a, n):
s = []
s.append(0);
for i in range(1, n):
while (len(s) != 0):
cur = s[-1]
if (a[cur] < a[i]):
next[cur] = i;
s.pop();
else:
break;
s.append(i);
while(len(s) != 0):
cur = s[-1]
next[cur] = -1;
s.pop();
def answer_query(a, next, n, index):
position = next[index];
if(position == -1):
return -1;
else:
return a[position];
if __name__=='__main__':
a = [3, 4, 2, 7, 5, 8, 10, 6 ]
n = len(a)
next=[0 for i in range(n)]
next_greatest(next, a, n);
print(answer_query(a, next, n, 3), end = ' ')
print(answer_query(a, next, n, 6), end = ' ')
print(answer_query(a, next, n, 1), end = ' ')
|
C#
using System;
using System.Collections.Generic;
class GFG
{
public static int[] query(int[] arr,
int[] query)
{
int[] ans = new int[arr.Length];
Stack<int> s = new Stack<int>();
s.Push(arr[0]);
int j = 0;
for (int i = 1; i < arr.Length; i++)
{
int next = arr[i];
if (s.Count > 0)
{
int element = s.Pop();
while (next > element)
{
ans[j] = next;
j++;
if (s.Count == 0)
{
break;
}
element = s.Pop();
}
if (element > next)
{
s.Push(element);
}
}
s.Push(next);
}
while (s.Count > 0)
{
int element = s.Pop();
ans[j] = -1;
j++;
}
return ans;
}
public static void Main(string[] args)
{
int[] arr = new int[] {3, 4, 2, 7, 5, 8, 10, 6};
int[] query = new int[] {3, 6, 1};
int[] ans = GFG.query(arr, query);
for (int i = 0; i < query.Length; i++)
{
Console.Write(ans[query[i]] + " ");
}
}
}
|
Javascript
<script>
function next_greatest(next, a, n)
{
var s = [];
s.push(0);
for (var i = 1; i < n; i++)
{
while (s.length!=0) {
var cur = s[s.length-1];
if (a[cur] < a[i])
{
next[cur] = i;
s.pop();
}
else
break;
}
s.push(i);
}
while (s.length!=0)
{
var cur = s[s.length-1];
next[cur] = -1;
s.pop();
}
}
function answer_query(a, next, n, index)
{
var position = next[index];
if (position == -1)
return -1;
else
return a[position];
}
var a = [3, 4, 2, 7,
5, 8, 10, 6];
var n = a.length;
var next = Array(n).fill(0);
next_greatest(next, a, n);
document.write( answer_query(a, next, n, 3) + " ");
document.write( answer_query(a, next, n, 6) + " ");
document.write( answer_query(a, next, n, 1) + " ");
</script>
|
Time complexity: max(O(n), O(q)), O(n) for pre-processing the next[] array and O(1) for every query.
Auxiliary Space: O(n)
Like Article
Suggest improvement
Share your thoughts in the comments
Please Login to comment...