Home » Technical Interview Questions » Stack Interview Questions » Maximum Product of Indexes of Next Greater on Left and Right

Maximum Product of Indexes of Next Greater on Left and Right


Difficulty Level Medium
Array Factset Fourkites InfoEdge 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].

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.
READ  Reverse a Stack Using Recursion

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

READ  Sorting array using Stacks

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

References

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions

AD Blocker Detected !

Advertisements help running this website for free.

To view the content please disable AdBlocker and refresh the page.

Wait !!! You can Crack Technical Interviews of Companies like Amazon, Google, LinkedIn, Facebook, PayPal, Flipkart, etc

Anisha was able to crack Amazon after practicing questions from TutorialCup