# Maximum Product of Indexes of Next Greater on Left and Right

Difficulty Level Medium
Frequently asked in Factset Fourkites InfoEdge
Array Stack

Given an array a[ ] of size n. For each element at position, i find the L[i] and R[i] where – L[i] = the closest index to i where L[closest index] > L[i] and closest index < i. R[i] = the closest index to i where R[closest index] > R[i] and closest index > i. If no such index exists for L[i] or R[i] update it at 0. Find the maximum of product of L and R where – LR Product [i] = L[i] * R[i].

## Example

Input : a[ ] = {5, 4, 3, 4, 5}

Output : 8

Input : a[ ] = {1, 1, 1, 1, 0, 1, 1, 1, 1, 1}

Output : 24

## Algorithm

1. Initialize an array a[ ] of size n.
2. Initialize two other arrays to store the left and right index of the closest greater element.
3. Create a stack. Traverse from n-1 to 0 and while stack is not empty and a[current index] is greater than a[stack.top() – 1]), update the left array at index stack.top() – 1 as current index + 1. Pop the top.
4. Insert the current index+1 in the stack.
5. For right array create a stack. Traverse from 0 to n-1 and while stack is not empty and a[current index] is greater than a[stack.top() – 1]), update the right array at index stack.top() – 1 as current index+1. Pop the top.
6. Insert the current index+1 in the stack.
7. Create a variable to store answers and initialize it as -1. Traverse from 0 to n-1 and update the answer variable as a maximum of answer variable and product of values at current index in the left array and right array.
Reverse a Number Using Stack

## C++ Program to find the maximum product of indexes of next greater on left and right

```#include <bits/stdc++.h>
using namespace std;
#define MAX 1000

vector<int> nextGreaterInLeft(int a[], int n){
vector<int> left_index(MAX, 0);
stack<int> s;

for(int i = n - 1; i >= 0; i--){

while(!s.empty() && a[i] > a[s.top() - 1]){
int r = s.top();
s.pop();

left_index[r - 1] = i + 1;
}

s.push(i + 1);
}
return left_index;
}

vector<int> nextGreaterInRight(int a[], int n){
vector<int> right_index(MAX, 0);
stack<int> s;

for(int i = 0; i < n; ++i){

while(!s.empty() && a[i] > a[s.top() - 1]){
int r = s.top();
s.pop();

right_index[r - 1] = i + 1;
}

s.push(i + 1);
}
return right_index;
}

int Product(int a[], int n){

vector<int> left = nextGreaterInLeft(a, n);

vector<int> right = nextGreaterInRight(a, n);
int ans = -1;

for(int i = 1; i <= n; i++){
ans = max(ans, left[i] * right[i]);
}

return ans;
}

int main(){
int a[] = {5, 4, 3, 4, 5};
int n = sizeof(a)/sizeof(a[1]);

cout<<Product(a, n);

return 0;
}```
`8`

## Java Program to find the maximum product of indexes of next greater on left and right

```import java.io.*;
import java.util.*;

class LRProduct{
static int MAX = 1000;

static int[] nextGreaterInLeft(int []a, int n){
int []left_index = new int[MAX];
Stack<Integer> s = new Stack<Integer>();

for(int i = n-1; i >= 0; i--){

while (s.size() != 0 && a[i] > a[s.peek() - 1]){
int r = s.peek();
s.pop();

left_index[r - 1] = i + 1;
}

s.push(i + 1);
}
return left_index;
}

static int[] nextGreaterInRight(int []a, int n){

int []right_index = new int[MAX];
Stack<Integer> s = new Stack<Integer>();

for(int i = 0; i < n; ++i){

while (s.size() != 0 && a[i] > a[s.peek() - 1]){
int r = s.peek();
s.pop();

right_index[r - 1] = i + 1;
}

s.push(i + 1);
}
return right_index;
}

static int Product(int []a, int n){

int []left = nextGreaterInLeft(a, n);

int []right = nextGreaterInRight(a, n);
int ans = -1;

for(int i = 1; i <= n; i++){
ans = Math.max(ans, left[i] * right[i]);
}

return ans;
}

public static void main(String args[]){

int []a = new int[]{5, 4, 3, 4, 5};
int n = a.length;

System.out.print(Product(a, n));
}
}
```
`8`

## Complexity Analysis for finding the maximum product of indexes of next greater on left and right

Time Complexity: O(n*n) where n is the number of elements in the array a[ ].