Last Updated on September 13, 2022 by Gokul Kannan
Problem statement
You are given an integer array of size n and q queries. Your task is to find the next greater element for each query. Each query consists of an integer representing an index. If there is no greater element for any index, then print -1.
Input: Two integer arrays of size n and q.
Output: Integer array of size q.
Test cases:
Input:
Arr = [9, 4, 2, 3, 8, 6, 10, 1]
Queries = [1, 2, 5, 6]
Output:
[8, 3, 10, -1]
Explanation:
- Output[0] = 8 because the next element greater than arr[1] = 4 is 8.
- Output[1] = 3 because the next element greater than arr[2] = 2 is 3.
- Output[2] = 10 because the next element greater than arr[5] = 6 is 10.
- Output[3] = -1 because there is no element greater than arr[6] on its left side.
Naive Approach – Brute Force
For each query, we will iterate the right side of the input array, starting from the index represented by this query. The answer of any query will be the first element greater than itself. If we don’t find any greater element than the answer of that element will be -1.
Algorithm
1. Initialize an empty array
2. For each i in 0 to length(queries):
a. index = queries[i]
b. For each j in index + 1 to length(arr)
i. If arr[j] > arr[index], then ans[i] = arr[j]
c. If we does not found the greater element, then ans[i] = -1
3. Return ans array.Code Implementation:
import java.io.*;
import java.util.*;
import java.lang.*;
class Prepbytes {
// This function will find the next greater element for each element
public static int[] nextGreaterElement(int arr[], int queries[])
{
int n = arr.length;
int q = queries.length;
int ans[] = new int[q];
// Iterate through each query
for(int i = 0; i < q; i++){
int index = queries[i];
boolean found = false;
// Check all elements to the right of the index
for(int j = index + 1; j < n; j++){
if(arr[j] > arr[index]){
ans[i] = arr[j];
found = true;
break;
}
}
if(!found){
ans[i] = -1;
}
}
return ans;
}
public static void main(String[] args) {
int arr[] = new int[]{9, 4, 2, 3, 8, 6, 10, 1};
int queries[] = new int[]{1, 2, 5, 6};
int ans[] = nextGreaterElement(arr, queries);
for(int e : ans){
System.out.print(e+" ");
}
}
}
Output:
8 3 10 -1
Time complexity: O(n q). It takes O(n) to solve one query because we are doing a linear scan of all the elements on the right side, and we have to solve q queries. Hence, the time complexity will be O(n q).
Space Complexity: O(n + q). The space required is only for the input and output array. The auxiliary space complexity is O(1).
Efficient Approach – Using Stack
As seen in the naive approach, we were iterating the array over and over again for each new query. What if we just pre-compute the next greater element for each index of the given array. Then we can answer each query, in constant time.
To find the next greater element we will use a stack data structure. The idea is to use the LIFO(Last-in-first-out) property of the stack.The stack will be used to store the elements in a monotonically increasing order.
We will iterate every element in the given array. For each element, while the stack is not empty and the current element is greater than the top of the stack, we will keep removing the top of the stack. After the while loop terminates, there could be two possible cases:
Case 1: The stack is empty. If the stack is empty it means that there were no greater elements than the current element. Hence, we will set next[i] as -1.
Case 2: We found an element greater than the current element. Then we will set next[i] as the top of the stack.
Once we have generated the next array, the answer for query q, will be just next[index]. Here, index is the integer represented by the current query. We will iterate over the queries array and find the answer for each query in constant time using the next array.
Algorithm
1. Initialize an empty stack and an array.
2. Iterate i from 0 to length(arr).
a. while stack is not empty and the current element is
greater than the top of the stack
i. Remove the top the stack
b. if the stack is empty, then it mean there is no next
greater element for this element
i. next[i] = -1.
c. Otherwise, next[i] = top of the stack
d. Push the current element to the stack
e. Iterate i in 0 to length(queries)
i. index = queries[i]
ii. ans[i] = next[index]
3. Return ans array.Dry Run:
Code Implementation:
import java.io.*;
import java.util.*;
import java.lang.*;
import java.util.Stack;
class Prepbytes {
public static int[] nextGreaterElement(int arr[], int queries[])
{
int n = arr.length;
Stack<Integer> st = new Stack<>();
int next[] = new int[n];
// Iterate over the given array
for(int i = n - 1; i>= 0; i--){
// While stack is not empty and the current
// element is greater than the top of the
// stack, keeping removing the top of the stack
while(!st.isEmpty() && arr[i] >= st.peek()){
st.pop();
}
// If the stack is empty, then it mean there is no next greater
// element for this element
if(st.isEmpty()){
next[i] = -1;
}
// Otherwise, the top of the stack is the next greater
// element for this element
else {
next[i] = st.peek();
}
// Push the current element to the stack
st.push(arr[i]);
}
int q = queries.length;
int ans[] = new int[q];
// Iterate through each query
for(int i = 0; i < q; i++){
int index = queries[i];
ans[i] = next[index];
}
return ans;
}
public static void main(String[] args) {
int arr[] = new int[]{9, 4, 2, 3, 8, 6, 10, 1};
int queries[] = new int[]{1, 2, 5, 6};
int ans[] = nextGreaterElement(arr, queries);
for(int e : ans){
System.out.print(e+" ");
}
}
}
Output:
8 3 10 -1
Time complexity: O(n + q). During precomputation, we can observe that every element is pushed and removed from the stack only once. Hence, the total operations being performed is 2n and O(2n) = O(n) because we don’t consider constant terms during asymptotic analysis of time complexity. We can solve each query in O(1) time and we have to solve q queries. Hence, the time taken will be O(q). The total time will be O(n + q).
Space Complexity: O(n). O(n) space is required for the input and output array. The auxiliary space complexity is O(n) as we are using a stack. At any point of time the stack can contain at most n elements.
This article tried to discuss the most efficient way to print the next greater number of Q queries.. Hope this blog helps you understand and solve the problem. To practice more problems you can check out MYCODE | Competitive Programming at PrepBytes.