Maximum Product of Indexes of Next Greater on Left and Right

Difficulty Level Medium
Frequently asked in Factset Fourkites InfoEdge
Array StackViews 2279

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].

Maximum Product of Indexes of Next Greater on Left and Right

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.
  8. Return the answer variable.

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[ ].

Auxiliary Space: O(n) because we used n extra space.

References

Translate »