Introduction
This article will discuss the problem of finding the maximum product of indexes of the next greater on left and right among all the given elements. To solve this problem, there is a prerequisite, and you must understand finding the next greater Element. To study more about this, you can refer to this blog of coding ninjas.
Problem Statement
The problem states that we are given an array of size N, and for each i (1<=i<=N), we define L(i) and R(i), and we need to calculate the maximum L(i)*R(i) among all the elements.
L(i) is defined as the nearest element in the left, i.e. for any j<i arr[j]>arr[i]. If there is no element satisfying the above condition, L(i) = 0.
R(i) is defined as the nearest element in the right, i.e. for any j>i arr[j]>arr[i]. If there is no element satisfying the above condition R(i) = 0.
Sample Examples
Input 1:
arr[] = {5, 4, 3, 4, 5, 2, 4}
Output 1:
The maximum product is : 35
Explanation
Left maximum Array Indexes = {0, 5, 4, 5, 0, 7, 0}
Right maximum Array indexes = {0, 1, 2, 1, 0, 5, 5}
Product array = {0, 5, 8, 5, 0, 35, 0}
Therefore maximum product is 35.
Input 2:
arr[] = {5, 5, 2, 6, 8, 8, 5}
Output 2:
The maximum product is: 8
Explanation
Left maximum Array Indexes = {4, 4, 4, 5, 0, 0, 0}
Right maximum Array indexes = {0, 0, 2, 0, 0, 0, 6}
Product array = {0, 0, 8, 0, 0, 0, 0}
Therefore maximum product is 8.
Approach 1
Prerequisite: Next greater Element
We need to calculate the nearest greatest Element to the left and the nearest greatest Element to the right. To find the nearest to the left and right, we will use two stacks, one from the left and one from the right.
Steps of Algorithm
- Initialize two stacks, one for finding the left maximum and one for the right maximum.
-
Do the following while traversing the array:
- If the stack is empty, push the current index into the stack.
- If the current element is greater than the top of the stack element, then store the index of the current Element on top of the stack.
- Do this for both the sides, once traverse from left to right and once from right to left.
- Now traverse both left and right arrays, and multiply to find the maximum among all the elements.
Implementation in C++
// c++ program to calulcate the maximum product
#include <bits/stdc++.h>
using namespace std;
// finding the next greater element to the left
vector<int> nextGreaterToLeft(vector<int> &arr)
{
// intiliazing the empty stack for calulating the next greater element to the left
stack<int> st;
int n = arr.size();
vector<int> ans(n);
for (int i = arr.size() - 1; i >= 0; i--)
{
while (!st.empty() && arr[st.top() - 1] <= arr[i])
st.pop();
if (st.empty())
{
ans[i] = 0;
}
else
{
ans[i] = st.top();
}
st.push(i + 1);
}
// returning the ans vector containing the indexes of all left greater elements
return ans;
}
vector<int> nextGreaterToRight(vector<int> &arr)
{
// intiliazing the empty stack for calulating the next greater element to the left
stack<int> st;
int n = arr.size();
vector<int> ans(n);
for (int i = 0; i < n; i++)
{
while (!st.empty() && arr[st.top() - 1] <= arr[i])
st.pop();
if (st.empty())
{
ans[i] = 0;
}
else
{
ans[i] = st.top();
}
st.push(i + 1);
}
// returning the ans vector containing the indexes of all right greater elements
return ans;
}
int main()
{
vector<int> arr = {5, 4, 3, 4, 5, 2, 4};
vector<int> left = nextGreaterToLeft(arr);
vector<int> right = nextGreaterToRight(arr);
int ans = 0;
// calulating the maximum product of left and right maxixmum indexes
for (int i = 0; i < arr.size(); i++){
ans = max(ans, left[i] * right[i]);
}
// printing the maximum product
cout << "The maximum product is : " << ans << endl;
}
Output:
The maximum product is: 35
Complexity Analysis
Time Complexity: O(N)
We are only doing linear traversal of the arrays, so time complexity is linear to find the maximum product of the indexes.
Space Complexity: O(N)
We are creating two temporary stacks and two temporary arrays to store the indexes of the next greater elements, so the time complexity is O(N).
245+ registered 
