Open In App

Print next greater number of Q queries

Last Updated : 23 May, 2024
Improve
Improve
Like Article
Like
Save
Share
Report

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++
// C++ program to print next
//greater number of Q queries
#include <bits/stdc++.h>
using namespace std;

// Function to print next greater
// of Q query
void next_greater(int arr[],int query[], int n,int q)
{
    //Loop for traversing each query
    for(int i=0;i<q;i++){
   //Take every query one by one
   int k=query[i];
   //To detect next greater element is present or not
   bool val=false;
   //Loop for checking next greater of each query
   for(int j=k+1;j<n;j++){
       if(arr[j]>arr[k]){
           cout<<arr[j]<<" ";
           //Make val true when there exist a next greater element
           val=true;
           break;
       }
   }
   
   //If next greater element is not present
   if(val==false){
      cout<<-1<<" ";    
   }
}
}


// Driver Code
int main()
{
//Given Numbers
int arr[] = {3, 4, 2, 7,5, 8, 10, 6 };
//Queries
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 {
    // Function to print the next greater elements for Q queries
    public static void nextGreater(int[] arr, int[] query) {
        int n = arr.length;
        int q = query.length;

        // Loop for traversing each query
        for (int i = 0; i < q; i++) {
            // Take every query one by one
            int k = query[i];
            // To detect if the next greater element is present or not
            boolean val = false;

            // Loop for checking the next greater element for each query
            for (int j = k + 1; j < n; j++) {
                if (arr[j] > arr[k]) {
                    System.out.print(arr[j] + " ");
                    // Set val to true when there exists a next greater element
                    val = true;
                    break;
                }
            }

            // If the next greater element is not present
            if (!val) {
                System.out.print(-1 + " ");
            }
        }
    }

    public static void main(String[] args) {
        // Given numbers
        int[] arr = { 3, 4, 2, 7, 5, 8, 10, 6 };
        // Queries
        int[] query = { 3, 6, 1 };

        int n = arr.length;
        int q = query.length;

        nextGreater(arr, query);
    }
}
Python
def next_greater_elements(arr, query):
    # Initialize a list to store results as strings
    results = []
    
    # Loop through each query
    for k in query:
        # Initialize a flag to detect if the next greater element is found
        val = False
        
        # Loop to check for the next greater element
        for j in range(k + 1, len(arr)):
            if arr[j] > arr[k]:
                results.append(str(arr[j]))
                # Set the flag to True when a next greater element is found
                val = True
                break
        
        # If no next greater element is found, push "-1" to the results list
        if not val:
            results.append("-1")
    
    # Print the results as a space-separated string
    print(" ".join(results))

# Given numbers
arr = [3, 4, 2, 7, 5, 8, 10, 6]
# Queries
query = [3, 6, 1]
next_greater_elements(arr, query)
C#
using System;

class GFG {
    // Function to print next greater of Q queries
    static void NextGreater(int[] arr, int[] query, int n,
                            int q)
    {
        // Loop for traversing each query
        for (int i = 0; i < q; i++) {
            // Take every query one by one
            int k = query[i];
            // To detect next greater element is present or
            // not
            bool val = false;
            // Loop for checking next greater of each query
            for (int j = k + 1; j < n; j++) {
                if (arr[j] > arr[k]) {
                    Console.Write(arr[j] + " ");
                    // Make val true when there exists a
                    // next greater element
                    val = true;
                    break;
                }
            }

            // If next greater element is not present
            if (val == false) {
                Console.Write(-1 + " ");
            }
        }
    }

    // Driver Code
    static void Main(string[] args)
    {
        // Given Numbers
        int[] arr = { 3, 4, 2, 7, 5, 8, 10, 6 };
        // Queries
        int[] query = { 3, 6, 1 };

        int n = arr.Length;
        int q = query.Length;

        NextGreater(arr, query, n, q);
    }
}
Javascript
function GFG(arr, query) {
    // Initialize an array to store results as a string
    const results = [];
    // Loop through each query
    for (let i = 0; i < query.length; i++) {
        // Take each query one by one
        const k = query[i];
        // Initialize a flag to detect if the next 
        // greater element is found
        let val = false;
        // Loop to check for the next greater element
        for (let j = k + 1; j < arr.length; j++) {
            if (arr[j] > arr[k]) {
                results.push(arr[j].toString());
                // Set the flag to true when a next 
                // greater element is found
                val = true;
                break;
            }
        }
        // If no next greater element is found
        // push "-1" to the results array
        if (!val) {
            results.push("-1");
        }
    }
    // Print the results as a space-separated string
    console.log(results.join(" "));
}
// Given numbers
const arr = [3, 4, 2, 7, 5, 8, 10, 6];
// Queries
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++
// C++ program to print 
// next greater number 
// of Q queries
#include <bits/stdc++.h>
using namespace std;

// array to store the next
// greater element index
void next_greatest(int next[], 
                   int a[], int n)
{
    // use of stl 
    // stack in c++
    stack<int> s;

    // push the 0th 
    // index to the stack
    s.push(0);

    // traverse in the 
    // loop from 1-nth index
    for (int i = 1; i < n; i++)
    {

        // iterate till loop is empty
        while (!s.empty()) {

            // get the topmost 
            // index in the stack
            int cur = s.top();

            // if the current element is  
            // greater than the top indexth 
            // element, then this will be 
            // the next greatest index 
            // of the top indexth element
            if (a[cur] < a[i])
            {
                
                // initialise the cur 
                // index position's 
                // next greatest as index
                next[cur] = i;

                // pop the cur index 
                // as its greater 
                // element has been found
                s.pop();
            }

            // if not greater
            // then break
            else
                break;
        }
        // push the i index so that its 
        // next greatest can be found
        s.push(i);
    }

    // iterate for all other 
    // index left inside stack
    while (!s.empty()) 
    {
        int cur = s.top();

        // mark it as -1 as no 
        // element in greater
        // then it in right
        next[cur] = -1;

        s.pop();
    }
}

// answers all 
// queries in O(1)
int answer_query(int a[], int next[], 
                 int n, int index)
{
    // stores the next greater
    // element positions
    int position = next[index];

    // if position is -1 then no 
    // greater element is at right.
    if (position == -1)
        return -1;

    // if there is a index that
    // has greater element 
    // at right then return its
    // value as a[position]
    else
        return a[position];
}

// Driver Code
int main()
{

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

    int n = sizeof(a) / sizeof(a[0]);

    // initializes the
    // next array as 0
    int next[n] = { 0 };

    // calls the function
    // to pre-calculate 
    // the next greatest 
    // element indexes
    next_greatest(next, a, n);

    // query 1 answered
    cout << answer_query(a, next, n, 3) << " ";

    // query 2 answered
    cout << answer_query(a, next, n, 6) << " ";

    // query 3 answered
    cout << answer_query(a, next, n, 1) << " ";
}
Java
// Java program to print 
// next greater number 
// of Q queries
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;
    }
    // Driver Code    
    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);

        // getting output array 
        // with next greatest elements
        for(int i = 0; i < query.length; i++) {
            // displaying the next greater
            // element for given set of queries
            System.out.print(ans[query[i]] + " ");
        }
    }
}

// This code was contributed
// by Raj Suvariya
Python
# Python3 program to print 
# next greater number 
# of Q queries

# array to store the next
# greater element index
def next_greatest(next, a, n):

    # use of stl 
    # stack in c++
    s = []

    # push the 0th 
    # index to the stack
    s.append(0);

    # traverse in the 
    # loop from 1-nth index
    for  i in range(1, n):

        # iterate till loop is empty
        while (len(s) != 0):

            # get the topmost 
            # index in the stack
            cur = s[-1]

            # if the current element is  
            # greater than the top indexth 
            # element, then this will be 
            # the next greatest index 
            # of the top indexth element
            if (a[cur] < a[i]):
                
                # initialise the cur 
                # index position's 
                # next greatest as index
                next[cur] = i;

                # pop the cur index 
                # as its greater 
                # element has been found
                s.pop();

            # if not greater
            # then break
            else:
                break;
        
        # push the i index so that its 
        # next greatest can be found
        s.append(i);

    # iterate for all other 
    # index left inside stack
    while(len(s) != 0):
        cur = s[-1]

        # mark it as -1 as no 
        # element in greater
        # then it in right
        next[cur] = -1;
        s.pop();
    
# answers all 
# queries in O(1)
def answer_query(a, next, n, index):

    # stores the next greater
    # element positions
    position = next[index];

    # if position is -1 then no 
    # greater element is at right.
    if(position == -1):
        return -1;

    # if there is a index that
    # has greater element 
    # at right then return its
    # value as a[position]
    else:
        return a[position];

# Driver Code
if __name__=='__main__':

    a = [3, 4, 2, 7, 5, 8, 10, 6 ]
    n = len(a)

    # initializes the
    # next array as 0
    next=[0 for i in range(n)]

    # calls the function
    # to pre-calculate 
    # the next greatest 
    # element indexes
    next_greatest(next, a, n);

    # query 1 answered
    print(answer_query(a, next, n, 3), end = ' ')

    # query 2 answered
    print(answer_query(a, next, n, 6), end = ' ')

    # query 3 answered
    print(answer_query(a, next, n, 1), end = ' ')

# This code is contributed by rutvik_56.
C#
// C# program to print next greater 
// number of Q queries 
using System;
using System.Collections.Generic;

class GFG
{
public static int[] query(int[] arr,
                          int[] query)
{
    int[] ans = new int[arr.Length]; // this array contains
                                     // the next greatest 
                                     // elements of all the elements 
    Stack<int> s = new Stack<int>();
    
    // push the 0th index to the stack 
    s.Push(arr[0]);
    int j = 0;
    
    // traverse rest of the array 
    for (int i = 1; i < arr.Length; i++)
    {
        int next = arr[i];

        if (s.Count > 0)
        {
            // get the topmost element in the stack 
            int element = s.Pop();

            /* If the popped element is smaller 
            than next, then 
            a) store the pair 
            b) keep popping while 
            elements are smaller and 
            stack is not empty */
            while (next > element)
            {
                ans[j] = next;
                j++;
                if (s.Count == 0)
                {
                    break;
                }
                element = s.Pop();
            }

            /* If element is greater 
            than next, then 
            push the element back */
            if (element > next)
            {
                s.Push(element);
            }
        }
        /* push next to stack so that we 
        can find next greater for it */
        s.Push(next);
    }
    
    /* After iterating over the 
    loop, the remaining elements 
    in stack do not have the next 
    greater element, so -1 for them */
    while (s.Count > 0)
    {
        int element = s.Pop();
        ans[j] = -1;
        j++;
    }

    // return the next greatest array 
    return ans;
}

// Driver Code     
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);

    // getting output array 
    // with next greatest elements 
    for (int i = 0; i < query.Length; i++)
    {
        // displaying the next greater 
        // element for given set of queries 
        Console.Write(ans[query[i]] + " ");
    }
}
}

// This code is contributed by Shrikant13
Javascript
// JavaScript program to print 
// next greater number 
// of Q queries

// array to store the next
// greater element index
function next_greatest(next, a, n)
{
    // use of stl 
    // stack in c++
    var s = [];

    // push the 0th 
    // index to the stack
    s.push(0);

    // traverse in the 
    // loop from 1-nth index
    for (var i = 1; i < n; i++)
    {

        // iterate till loop is empty
        while (s.length!=0) {

            // get the topmost 
            // index in the stack
            var cur = s[s.length-1];

            // if the current element is  
            // greater than the top indexth 
            // element, then this will be 
            // the next greatest index 
            // of the top indexth element
            if (a[cur] < a[i])
            {
                
                // initialise the cur 
                // index position's 
                // next greatest as index
                next[cur] = i;

                // pop the cur index 
                // as its greater 
                // element has been found
                s.pop();
            }

            // if not greater
            // then break
            else
                break;
        }
        // push the i index so that its 
        // next greatest can be found
        s.push(i);
    }

    // iterate for all other 
    // index left inside stack
    while (s.length!=0) 
    {
        var cur = s[s.length-1];

        // mark it as -1 as no 
        // element in greater
        // then it in right
        next[cur] = -1;

        s.pop();
    }
}

// answers all 
// queries in O(1)
function answer_query(a, next, n, index)
{
    // stores the next greater
    // element positions
    var position = next[index];

    // if position is -1 then no 
    // greater element is at right.
    if (position == -1)
        return -1;

    // if there is a index that
    // has greater element 
    // at right then return its
    // value as a[position]
    else
        return a[position];
}

// Driver Code
var a = [3, 4, 2, 7, 
           5, 8, 10, 6];
var n = a.length;
// initializes the
// next array as 0
var next = Array(n).fill(0);
// calls the function
// to pre-calculate 
// the next greatest 
// element indexes
next_greatest(next, a, n);
// query 1 answered
console.log( answer_query(a, next, n, 3) + " ");
// query 2 answered
console.log( answer_query(a, next, n, 6) + " ");
// query 3 answered
console.log( answer_query(a, next, n, 1) + " ");

Output
8 -1 7 

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)


 



Previous Article
Next Article

Similar Reads

Find next Smaller of next Greater in an array
Given array of integer, find the next smaller of next greater element of every element in array. Note : Elements for which no greater element exists or no smaller of greater element exist, print -1. Examples: Input : arr[] = {5, 1, 9, 2, 5, 1, 7} Output: 2 2 -1 1 -1 -1 -1 Explanation : Next Greater -&gt; Right Smaller 5 -&gt; 9 9 -&gt; 2 1 -&gt; 9
14 min read
Binary representation of next greater number with same number of 1's and 0's
Given a binary input that represents binary representation of positive number n, find binary representation of smallest number greater than n with same number of 1's and 0's as in binary representation of n. If no such number can be formed, print "no greater number".The binary input may be and may not fit even in unsigned long long int. Examples: I
12 min read
Find the Next perfect square greater than a given number
Given a number N, the task is to find the next perfect square greater than N.Examples: Input: N = 6Output: 9Explanation: 9 is a greater number than 6 and is also a perfect square Input: N = 9Output: 16 Approach: Find the square root of given N.Calculate its floor value using floor function in C++.Then add 1 to it.Print square of that number. Below
3 min read
Next greater number than N with exactly one bit different in binary representation of N
Given a number N. The task is to find the smallest number which is greater than N and has only one bit different in the binary representation of N. Note: Here N can be very large 10^9 &lt; N &lt; 10^15.Examples: Input : N = 11 Output : The next number is 15 The binary representation of 11 is 1011 So the smallest number greater than 11 with one bit
7 min read
Next greater Number than N with the same quantity of digits A and B
Given a number [Tex]N [/Tex]and two digits [Tex]A [/Tex]and [Tex]B [/Tex]. The task is to find the least number not less than N which contains the equal number of digits A and B.Note: N &lt;= 107Examples: Input : N = 4500, A = 4, B = 7 Output : 4747 The number greater than 4500 which has the same quantity of number '4' and number '7' is 4747.Input
7 min read
Find next greater number formed with exactly two unique digits for each Array element
Given an array arr[] having N integers, the task is to find the next greater number X i.e, X &gt;= arr[i] for each i in the range [0, N) such that the count of unique digits in X is exactly 2. Example: Input: arr[] = {123, 234}Output: 131 242Explanation: For the given array, 131 is the smallest number greater that 123 having exactly 2 unique digits
11 min read
Next greater number on the basis of precedence of digits
Given a number num containing n digits. The problem is to find the next greater number using the same set of digits in num on the basis of the given precedence of digits. For example the precedence of digits is given as 1, 6, 4, 5, 2, 9, 8, 0, 7, 3 which simply means 1 &lt; 6 &lt; 4 &lt; 5 &lt; 2 &lt; 9 &lt; 8 &lt; 0 &lt; 7 &lt; 3. If next greater
10 min read
Find next greater number with same set of digits
Given a number n, find the smallest number that has same set of digits as n and is greater than n. If n is the greatest possible number with its set of digits, then print "not possible". Examples: For simplicity of implementation, we have considered input number as a string. Input: n = "218765" Output: "251678" Input: n = "1234" Output: "1243" Inpu
15+ min read
Closest (or Next) smaller and greater numbers with same number of set bits
Given a positive integer n, print the next smallest and the previous largest number that has the same number of 1 bit in their binary representation. Examples: Input : n = 5 Output : Closest Greater = 6 Closest Smaller = 3 Note that 5, 6 and 3 have same number of set bits. Input : n = 11 Output : Closest Greater = 13 Closest Smaller = 7 The Brute F
15+ min read
Next greater integer having one more number of set bits
Given a positive integer 'n' having 'x' number of set bits in its binary representation. The problem is to find the next greater integer(smallest integer greater than n), having (x+1) number of set bits in its binary representation.Examples : Input : 10 Output : 11 (10)10 = (1010)2 is having 2 set bits. (11)10 = (1011)2 is having 3 set bits and is
6 min read
Article Tags :
Practice Tags :
three90RightbarBannerImg