Last Updated on October 10, 2022 by Gokul Kannan
Problem Statement
You are given an array A. Let us say that the array has indices from 1 to N. For each index i in the array:
- The quantity L(i) is the closest index (say j) to the left of the index i i.e. j < i such that a[j] > a[i]. This means that L(i) represents the index of the Next Greater Element (NGE) to the left for index i. If there is no NGE to the left of index i, L(i) = 0.
- The quantity R(i) is the closest index (say k) to the right of the index i i.e. i < k such that a[k] > a[i]. This means that R(i) represents the index of the Next Greater Element (NGE) to the right of index i. If there is no NGE to the right of index i, R(i) = 0.
- The quantity LRProduct(i) for each index i of the array is the product of L(i) and R(i) i.e. LRProduct(i) = L(i) R(i) = j k. Thus, it is the maximum product of indexes of next greater on left and right.
You have to return the index that has the maximum value of LRProduct. Please note that the array has 1-based indexing.
Example
Consider the example shown below.
So, in the above example, we see that we have the array L that stores the index of NGE to the left for every index. For all those indexes where there is no NGE to the left, we have stored 0. Similarly, the array R stores the index of the NGE to the right for every index of the array and we have stored 0 for all those indexes that do not have any NGE to the right.
The maximum product is for index 5. Hence the answer will be 5.
Approach
We have to fill 2 arrays, one with the next greater element (NGE) to the left and the other with NGE to the right. Let us first see how to fill the L array.
Next Greater Element (NGE) to the Left
Consider the array shown below.
So, we have an empty L array that we have to fill. Let us take a Stack and let us take a pointer at index 0 as shown below.
For index 0, there is no element to the left. Hence, there will not be any NGE to the left. So, L[0] = 0, and we push the index 0 into the stack.
Now, array[i] = array[1] = 8 is less than array[top of stack]. So, the top of the stack will become the next greater element (NGE) to the left for index 1. Hence, L[1] = 0.
However, in the question, since we are given 1-based indexing, L[1] = top of stack + 1. Hence, L[1] = 0+1 = 1.
We will also push the current index into the stack because the element at our index can be an NGE for some other index moving forward.
So, we can establish the following conclusion from above.
So, using this conclusion, we can fill our answers till index 3 as shown below.
Now, at index 4, arr[i] > arr[top]. So, we have to pop from the stack till the stack is not empty and arr[i] > arr[top].
So, after popping the elements from the stack, the next step is same as above.
So, the conclusion that we derive from here is shown below.
One thing is left to discuss. What if we keep popping from the stack and it becomes empty? Consider the case when i moves to the next index i.e. index 5.
In this case, value at index 5 is greater than all the other values. So, the stack becomes empty. In this case, stack being empty means that there is no NGE to the left. Hence, L[i] = 0. Also, we will push the current index into the stack.
So, the conclusion derived from here is shown below.
Now, try filling the last index of L array yourself. It is as shown below.
So, we have completely filled the L array. Now, we have to fill the R array. Let us discuss it.
Next Greater Element (NGE) to the Right
This process is a little bit different from the previous one. Here, let us assume that we have once filled the array with all 0s and have already pushed the 0 index into the stack as shown below.
We start iterating from index 1. Since arr[i] = arr[1] = 8 < arr[top], i cannot be the NGE index for the top of the stack i.e. index 0. However, it can be an NGE index for some other index moving forward. Hence, we will push it into the stack.
The conclusion that we devise from here is given below.
So, with this conclusion, we will move till index 3 and no change will take place in the R array.
Now, arr[i] = arr[4] = 4 is greater than arr[top] = arr[3] = 3. So, i=4 will be the NGE index for the top of the stack. Hence, we pop it from the stack, and R[top] = i + 1. We have done plus 1 because the indices in the question are 1-based.
Also, we will do this till the stack is not empty and arr[i] > arr[top].
The conclusion that we draw from here is shown below.
So, when we are at index = 5, we can see this better as shown below.
Finally, the R array gets completely filled.
So, we have learnt the Next Greater Element to the Right.
After filling both these arrays, we will take a variable maximum that can initially be assigned minus infinity. Also, we will assign a variable maxIndex, that will tell us the index of the maximum product.
Now, we can traverse the left and right arrays, calculate the product at each index and find the maximum product. Also, we will keep on updating the maxIndex. This is shown below.
So, the final answer is maxIdx + 1 = 4 + 1 = 5. (Since the indices are 1-based).
Now that we have discussed the complete procedure, let us write the code for the same.
Code Implementation:
#include<bits/stdc++.h>
using namespace std;
void NGELeft(int arr[], int L[], int n) {
stack<int> stk;
for(int i=0;i<n;i++) {
while(stk.size() > 0 && arr[stk.top()] < arr[i]) {
stk.pop();
}
if(stk.size() == 0) {
L[i] = 0;
} else {
L[i] = stk.top() + 1;
}
stk.push(i);
}
}
void NGERight(int arr[], int R[],int n) {
for(int i=0;i<n;i++) {
R[i] = 0;
}
stack<int> stk;
stk.push(0);
for(int i=0;i<n;i++) {
if(arr[i] < arr[stk.top()]) {
stk.push(i);
} else {
while(stk.size() > 0 && arr[stk.top()] < arr[i]) {
int idx = stk.top();
stk.pop();
R[idx] = i + 1;
}
stk.push(i);
}
}
}
int solve(int L[], int R[],int n) {
int max = INT_MIN;
int maxIdx = -1;
for(int i=0;i<n;i++) {
if(max < L[i] * R[i]) {
max = L[i] * R[i];
maxIdx = i;
}
}
return maxIdx;
}
int main() {
int arr[] = {9,8,6,3,4,10,2};
int n = sizeof(arr)/sizeof(arr[0]);
int L[n];
NGELeft(arr,L,n);
int R[n];
NGERight(arr,R,n);
int res = solve(L,R,n) + 1;
cout<<res;
}
// "static void main" must be defined in a public class.
import java.util.*;
public class Main {
public static void NGELeft(int[] arr, int[] L) {
Stack<Integer> stk = new Stack<>();
for(int i=0;i<arr.length;i++) {
while(stk.size() > 0 && arr[stk.peek()] < arr[i]) {
stk.pop();
}
if(stk.size() == 0) {
L[i] = 0;
} else {
L[i] = stk.peek() + 1;
}
stk.push(i);
}
}
public static void NGERight(int[] arr, int[] R) {
Arrays.fill(R,0);
Stack<Integer> stk = new Stack<>();
stk.push(0);
for(int i=0;i<arr.length;i++) {
if(arr[i] < arr[stk.peek()]) {
stk.push(i);
} else {
while(stk.size() > 0 && arr[stk.peek()] < arr[i]) {
int idx = stk.pop();
R[idx] = i + 1;
}
stk.push(i);
}
}
}
public static int solve(int[] L, int[] R) {
int max = Integer.MIN_VALUE;
int maxIdx = -1;
for(int i=0;i<L.length;i++) {
if(max < L[i] * R[i]) {
max = L[i] * R[i];
maxIdx = i;
}
}
return maxIdx;
}
public static void main(String[] args) {
int[] arr = {9,8,6,3,4,10,2};
int[] L = new int[arr.length];
NGELeft(arr,L);
int[] R = new int[arr.length];
NGERight(arr,R);
System.out.println(solve(L,R) + 1);
}
}
Time Complexity
The time complexity is O(N) for calculating the NGE to the left and right.
Space Complexity
The space complexity is O(N) as we have used 2 auxiliary arrays L and R.
Follow up: We can also solve this problem using 1 array only. The time complexity will still be O(N) and the space complexity will also be O(N) only. However, instead of 2 arrays L and R, we can just use any 1 array. How? Let us say we first fill up the L array. Now, when we find NGE to the right, we don’t fill it in a separate array, but rather multiply it with the L[i] and store it at L[i] only. Try to code this yourself.
This article tried to discuss the Maximum Product of Indexes of next greater on Left and Right. Hope this blog helps you understand and solve the problem. To Practice more problems you can check out MYCODE | Competitive Programming at PrepBytes.