Maximum product of indexes of next greater on left and right
Last Updated :
22 Jun, 2022
Given an array a[1..N]. For each element at position i (1 <= i <= N). Where
- L(i) is defined as closest index j such that j < i and a[j] > a[i]. If no such j exists then L(i) = 0.
- R(i) is defined as closest index k such that k > i and a[k] > a[i]. If no such k exists then R(i) = 0.
LRProduct(i) = L(i)*R(i) .
We need to find an index with maximum LRProduct
Examples:
Input : 1 1 1 1 0 1 1 1 1 1
Output : 24
For {1, 1, 1, 1, 0, 1, 1, 1, 1, 1} all element are same except 0. So only for zero their exist greater element and for others it will be zero. for zero, on left 4th element is closest and greater than zero and on right 6th element is closest and greater. so maximum
product will be 4*6 = 24.
Input : 5 4 3 4 5
Output : 8
For {5, 4, 3, 4, 5}, L[] = {0, 1, 2, 1, 0} and R[]
= {0, 5, 4, 5, 0},
LRProduct = {0, 5, 8, 5, 0} and max in this is 8.
Note: Taking starting index as 1 for finding LRproduct.
This problem is based on Next Greater Element.
From the current position, we need to find the closest greater element on its left and right side.
So to find next greater element, we used stack one from left and one from right.simply we are checking which element is greater and storing their index at specified position.
1- if stack is empty, push current index.
2- if stack is not empty
….a) if current element is greater than top element then store the index of current element on index of top element.
Do this, once traversing array element from left and once from right and form the left and right array, then, multiply them to find max product value.
C++
#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 LRProduct(int arr[], int n)
{
vector<int> left = nextGreaterInLeft(arr, n);
vector<int> right = nextGreaterInRight(arr, n);
int ans = -1;
for (int i = 1; i <= n; i++) {
ans = max(ans, left[i] * right[i]);
}
return ans;
}
int main()
{
int arr[] = { 5, 4, 3, 4, 5 };
int n = sizeof(arr) / sizeof(arr[1]);
cout << LRProduct(arr, n);
return 0;
}
|
Java
import java.io.*;
import java.util.*;
class GFG
{
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 LRProduct(int []arr, int n)
{
int []left = nextGreaterInLeft(arr, n);
int []right = nextGreaterInRight(arr, 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 []arr = new int[]{ 5, 4, 3, 4, 5 };
int n = arr.length;
System.out.print(LRProduct(arr, n));
}
}
|
Python3
def nextGreaterInLeft(a):
left_index = [0] * len(a)
s = []
for i in range(len(a)):
while len(s) != 0 and a[i] >= a[s[-1]]:
s.pop()
if len(s) != 0:
left_index[i] = s[-1]
else:
left_index[i] = 0
s.append(i)
return left_index
def nextGreaterInRight(a):
right_index = [0] * len(a)
s = []
for i in range(len(a) - 1, -1, -1):
while len(s) != 0 and a[i] >= a[s[-1]]:
s.pop()
if len(s) != 0:
right_index[i] = s[-1]
else:
right_index[i] = 0
s.append(i)
return right_index
def LRProduct(arr):
left = nextGreaterInLeft(arr)
right = nextGreaterInRight(arr)
ans = -1
for i in range(1, len(left) - 1):
if left[i] == 0 or right[i] == 0:
ans = max(ans, 0)
else:
temp = (left[i] + 1) * (right[i] + 1)
ans = max(ans, temp)
return ans
arr = [ 5, 4, 3, 4, 5 ]
print(LRProduct(arr))
|
C#
using System;
using System.Collections.Generic;
class GFG {
static int MAX = 1000;
static int[] nextGreaterInLeft(int []a, int n)
{
int []left_index = new int[MAX];
Stack<int> s = new Stack<int>();
for (int i = n - 1; i >= 0; i--) {
while (s.Count != 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<int> s = new Stack<int>();
for (int i = 0; i < n; ++i) {
while (s.Count != 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 LRProduct(int []arr, int n)
{
int []left = nextGreaterInLeft(arr, n);
int []right = nextGreaterInRight(arr, n);
int ans = -1;
for (int i = 1; i <= n; i++) {
ans = Math.Max(ans, left[i] * right[i]);
}
return ans;
}
static void Main()
{
int []arr = new int[]{ 5, 4, 3, 4, 5 };
int n = arr.Length;
Console.Write(LRProduct(arr, n));
}
}
|
Javascript
<script>
let MAX = 1000;
function nextGreaterInLeft(a, n)
{
let left_index = new Array(MAX);
left_index.fill(0);
let s = [];
for (let i = n - 1; i >= 0; i--) {
while (s.length != 0 && a[i] > a[s[s.length - 1] - 1])
{
let r = s[s.length - 1];
s.pop();
left_index[r - 1] = i + 1;
}
s.push(i + 1);
}
return left_index;
}
function nextGreaterInRight(a, n)
{
let right_index = new Array(MAX);
right_index.fill(0);
let s = [];
for (let i = 0; i < n; ++i) {
while (s.length != 0 && a[i] > a[s[s.length - 1] - 1])
{
let r = s[s.length - 1];
s.pop();
right_index[r - 1] = i + 1;
}
s.push(i + 1);
}
return right_index;
}
function LRProduct(arr, n)
{
let left = nextGreaterInLeft(arr, n);
let right = nextGreaterInRight(arr, n);
let ans = -1;
for (let i = 1; i <= n; i++) {
ans = Math.max(ans, left[i] * right[i]);
}
return ans;
}
let arr = [ 5, 4, 3, 4, 5 ];
let n = arr.length;
document.write(LRProduct(arr, n));
</script>
|
Complexity Analysis:
Time Complexity: O(n)
Space Complexity: O(n)
Method 2: Reducing the space used by using only one array to store both left and right max.
Approach:
Prerequisite: https://www.geeksforgeeks.org/next-greater-element/
- To find the next greater element to left, we used a stack from the left, and the same stack is used for multiplying the right greatest element index with the left greatest element index.
- Function maxProduct( ) is used for returning the max product by iterating the resultant array.
C++
#include <bits/stdc++.h>
using namespace std;
stack<int> mystack;
void nextGreaterToLeft(int arr[], int res[], int N) {
mystack.push(0);
res[0] = 0;
for(int i = 1; i < N; i++) {
while(mystack.size() > 0 && arr[mystack.top()] <= arr[i])
mystack.pop();
res[i] = (mystack.size() == 0) ? 0 : mystack.top()+1;
mystack.push(i);
}
}
void nextGreaterToRight(int arr[], int res[], int N) {
mystack = stack<int>();
int n = N;
mystack.push(n-1);
res[n-1] *= 0;
for(int i=n - 2 ; i >= 0; i--) {
while(mystack.size() > 0 && arr[mystack.top()] <= arr[i])
mystack.pop();
res[i] = (mystack.size() == 0) ? res[i]*0 : res[i]*(mystack.top()+1);
mystack.push(i);
}
}
int maxProduct(int arr[], int res[], int N) {
nextGreaterToLeft(arr,res, N);
nextGreaterToRight(arr,res, N);
int Max = res[0];
for(int i = 1; i < N; i++){
Max = max(Max, res[i]);
}
return Max;
}
int main()
{
int arr[] = {5, 4, 3, 4, 5};
int N = sizeof(arr) / sizeof(arr[0]);
int res[N];
int maxprod = maxProduct(arr, res, N);
cout << maxprod << endl;
return 0;
}
|
Java
import java.util.*;
public class GFG {
Stack<Integer> mystack = new Stack<>();
void nextGreaterToLeft(int[] arr,int[] res) {
mystack.push(0);
res[0] = 0;
for(int i=1;i<arr.length;i++) {
while(!mystack.isEmpty() && arr[mystack.peek()] <= arr[i])
mystack.pop();
res[i] = (mystack.isEmpty()) ? 0 : mystack.peek()+1;
mystack.push(i);
}
}
void nextGreaterToRight(int[] arr,int[] res) {
mystack.clear();
int n = arr.length;
mystack.push(n-1);
res[n-1] *= 0;
for(int i=n-2;i>=0;i--) {
while(!mystack.isEmpty() && arr[mystack.peek()] <= arr[i])
mystack.pop();
res[i] = (mystack.isEmpty()) ? res[i]*0 : res[i]*(mystack.peek()+1);
mystack.push(i);
}
}
int maxProduct(int[] arr,int[] res) {
nextGreaterToLeft(arr,res);
nextGreaterToRight(arr,res);
int max = res[0];
for(int i = 1;i<res.length;i++){
max = Math.max(max, res[i]);
}
return max;
}
public static void main(String args[]) {
GFG obj = new GFG();
int arr[] = {5, 4, 3, 4, 5};
int res[] = new int[arr.length];
int maxprod = obj.maxProduct(arr, res);
System.out.println(maxprod);
}
}
|
Python3
mystack = []
def nextGreaterToLeft(arr, res):
mystack.append(0)
res[0] = 0
for i in range(1, len(arr)):
while(len(mystack) > 0 and arr[mystack[-1]] <= arr[i]):
mystack.pop()
if (len(mystack) == 0):
res[i] = 0
else:
res[i] = mystack[-1]+1
mystack.append(i)
def nextGreaterToRight(arr, res):
mystack = []
n = len(arr)
mystack.append(n-1)
res[n-1] *= 0
for i in range(n - 2, -1, -1):
while(len(mystack) > 0 and arr[mystack[-1]] <= arr[i]):
mystack.pop()
if (len(mystack) == 0):
res[i] = res[i]*0
else :
res[i] = res[i]*(mystack[-1]+1)
mystack.append(i)
def maxProduct(arr, res):
nextGreaterToLeft(arr,res)
nextGreaterToRight(arr,res)
Max = res[0]
for i in range(1, len(res)):
Max = max(Max, res[i])
return Max
arr = [5, 4, 3, 4, 5]
res = [0]*(len(arr))
maxprod = maxProduct(arr, res)
print(maxprod)
|
C#
using System;
using System.Collections;
class GFG {
static Stack mystack = new Stack();
static void nextGreaterToLeft(int[] arr,int[] res) {
mystack.Push(0);
res[0] = 0;
for(int i=1;i<arr.Length;i++) {
while(mystack.Count > 0 && arr[(int)mystack.Peek()] <= arr[i])
mystack.Pop();
res[i] = (mystack.Count == 0) ? 0 : (int)mystack.Peek()+1;
mystack.Push(i);
}
}
////To find greater element to right
static void nextGreaterToRight(int[] arr,int[] res) {
mystack = new Stack();
int n = arr.Length;
mystack.Push(n-1);
res[n-1] *= 0;
for(int i = n - 2; i >= 0; i--) {
while(mystack.Count == 0 && arr[(int)mystack.Peek()] <= arr[i])
mystack.Pop();
res[i] = (mystack.Count == 0) ? res[i]*0 : res[i]*((int)mystack.Peek()+1);
mystack.Push(i);
}
}
static int maxProduct(int[] arr,int[] res) {
nextGreaterToLeft(arr, res);
nextGreaterToRight(arr, res);
int max = res[0];
for(int i = 1; i < res.Length; i++){
max = Math.Max(max, res[i]);
}
return max;
}
static void Main() {
int[] arr = {5, 4, 3, 4, 5};
int[] res = new int[arr.Length];
int maxprod = maxProduct(arr, res);
Console.WriteLine(maxprod);
}
}
|
Javascript
<script>
let mystack = [];
function nextGreaterToLeft(arr, res) {
mystack.push(0);
res[0] = 0;
for(let i = 1; i < arr.length; i++) {
while(mystack.length > 0 && arr[mystack[mystack.length - 1]] <= arr[i])
mystack.pop();
res[i] = (mystack.length == 0) ? 0 : mystack[mystack.length - 1]+1;
mystack.push(i);
}
}
function nextGreaterToRight(arr, res) {
mystack = [];
let n = arr.length;
mystack.push(n-1);
res[n-1] *= 0;
for(let i = n - 2; i >= 0; i--) {
while(mystack.length > 0 && arr[mystack[mystack.length - 1]] <= arr[i])
mystack.pop();
res[i] = (mystack.length == 0) ? res[i]*0 : res[i]*(mystack[mystack.length - 1]+1);
mystack.push(i);
}
}
function maxProduct(arr, res) {
nextGreaterToLeft(arr,res);
nextGreaterToRight(arr,res);
let max = res[0];
for(let i = 1;i<res.length;i++){
max = Math.max(max, res[i]);
}
return max;
}
let arr = [5, 4, 3, 4, 5];
let res = new Array(arr.length);
let maxprod = maxProduct(arr, res);
document.write(maxprod);
</script>
|
Complexity Analysis:
Time Complexity: O(n)
Space Complexity: O(n)
Please Login to comment...