Open In App

Maximum product of indexes of next greater on left and right

Last Updated : 24 Apr, 2025
Comments
Improve
Suggest changes
Like Article
Like
Report

Given an array arr[1..n], for each element at position i (1 <= i <= n), define the following:

  • left(i) is the closest index j such that j < i and arr[j] > arr[i]. If no such j exists, then left(i) = 0.
  • right(i) is the closest index k such that k > i and arr[k] > arr[i]. If no such k exists, then right(i) = 0.
  • LRproduct(i) = left(i) * right(i).

The task is to find the maximum LR product of the given array.

Examples:

Input: arr[] = [1, 1, 1, 1, 0, 1, 1, 1, 1, 1]
Output: 24
Explanation: All elements are equal except 0. Only for 0, greater elements exist. On the left half, the closest greater element is at index 4 and on the right half, it is at index 6. The maximum product is 4 × 6 = 24.

Input: arr[] = [5, 4, 3, 4, 5]
Output: 8
Explanation: For [5, 4, 3, 4, 5]: left[] = [0, 1, 2, 1, 0], right[] = [0, 5, 4, 5, 0]
LRproduct[] = [0, 5, 8, 5, 0]. The maximum value in LRproduct is 8.

Please note indexes are considered from 1 to n and 0 is used for filling in cases when left(i) and/or right(i) do not exist.

Table of Content

Using Monotonic Stack With 2 Arrays – O(n) Time and O(n) Space

The idea is to find the closest greater elements on both left and right for each element. Using a monotonic stack, we efficiently compute left(i) and right(i) in linear time. The key observation is that elements are processed in increasing order, ensuring each element is pushed and popped at most once. Finally, we compute LRproduct for all indices and return the maximum value.

C++ 
// C++ program to find the maximum LR product 
// using stack and 2 Arrays
#include <bits/stdc++.h>
using namespace std;

// Function to find the maximum LR product
int findMaxLRProduct(vector<int>& arr) {
    
    int n = arr.size();
    vector<int> left(n, 0), right(n, 0);
    stack<int> stk;

    // Compute left(i) using a monotonic stack
    for (int i = 0; i < n; i++) {

        while (!stk.empty() && arr[stk.top()] <= arr[i]) {
            stk.pop();
        }

        if (!stk.empty()) {
            
            // Store 1-based index
            left[i] = stk.top() + 1; 
        }

        stk.push(i);
    }

    // Clear stack to reuse for right(i)
    while (!stk.empty()) {
        stk.pop();
    }

    // Compute right(i) using a monotonic stack
    for (int i = n - 1; i >= 0; i--) {

        while (!stk.empty() && arr[stk.top()] <= arr[i]) {
            stk.pop();
        }

        if (!stk.empty()) {
            
            // Store 1-based index
            right[i] = stk.top() + 1; 
        }

        stk.push(i);
    }

    int maxProduct = 0;

    // Compute the maximum LR product
    for (int i = 0; i < n; i++) {
        maxProduct = max(maxProduct, left[i] * right[i]);
    }

    return maxProduct;
}

// Driver code
int main() {

    vector<int> arr = {1, 1, 1, 1, 0, 1, 1, 1, 1, 1};

    cout << findMaxLRProduct(arr) << endl;

    return 0;
}
Java 
// Java program to find the maximum LR product 
// using stack and 2 Arrays
import java.util.*;

class GfG {

    // Function to find the maximum LR product
    static int findMaxLRProduct(int[] arr) {
        
        int n = arr.length;
        int[] left = new int[n], right = new int[n];
        Stack<Integer> stk = new Stack<>();

        // Compute left(i) using a monotonic stack
        for (int i = 0; i < n; i++) {

            while (!stk.isEmpty() && arr[stk.peek()] <= arr[i]) {
                stk.pop();
            }

            if (!stk.isEmpty()) {
                
                // Store 1-based index
                left[i] = stk.peek() + 1; 
            }

            stk.push(i);
        }

        // Clear stack to reuse for right(i)
        stk.clear();

        // Compute right(i) using a monotonic stack
        for (int i = n - 1; i >= 0; i--) {

            while (!stk.isEmpty() && arr[stk.peek()] <= arr[i]) {
                stk.pop();
            }

            if (!stk.isEmpty()) {
                
                // Store 1-based index
                right[i] = stk.peek() + 1; 
            }

            stk.push(i);
        }

        int maxProduct = 0;

        // Compute the maximum LR product
        for (int i = 0; i < n; i++) {
            maxProduct = Math.max(maxProduct, left[i] * right[i]);
        }

        return maxProduct;
    }

    // Driver code
    public static void main(String[] args) {

        int[] arr = {1, 1, 1, 1, 0, 1, 1, 1, 1, 1};

        System.out.println(findMaxLRProduct(arr));
    }
}
Python 
# Python program to find the maximum LR product 
# using stack and 2 lists

def findMaxLRProduct(arr):
    
    n = len(arr)
    left = [0] * n
    right = [0] * n
    stk = []

    # Compute left(i) using a monotonic stack
    for i in range(n):

        while stk and arr[stk[-1]] <= arr[i]:
            stk.pop()

        if stk:
            
            # Store 1-based index
            left[i] = stk[-1] + 1 

        stk.append(i)

    # Clear stack to reuse for right(i)
    stk.clear()

    # Compute right(i) using a monotonic stack
    for i in range(n - 1, -1, -1):

        while stk and arr[stk[-1]] <= arr[i]:
            stk.pop()

        if stk:
            
            # Store 1-based index
            right[i] = stk[-1] + 1 

        stk.append(i)

    max_product = 0

    # Compute the maximum LR product
    for i in range(n):
        max_product = max(max_product, left[i] * right[i])

    return max_product

# Driver code
if __name__ == "__main__":

    arr = [1, 1, 1, 1, 0, 1, 1, 1, 1, 1]

    print(findMaxLRProduct(arr))
C# 
// C# program to find the maximum LR product 
// using stack and 2 Arrays
using System;
using System.Collections.Generic;

class GfG {

    // Function to find the maximum LR product
    public static int FindMaxLRProduct(int[] arr) {
        
        int n = arr.Length;
        int[] left = new int[n], right = new int[n];
        Stack<int> stk = new Stack<int>();

        // Compute left(i) using a monotonic stack
        for (int i = 0; i < n; i++) {

            while (stk.Count > 0 && arr[stk.Peek()] <= arr[i]) {
                stk.Pop();
            }

            if (stk.Count > 0) {
                
                // Store 1-based index
                left[i] = stk.Peek() + 1; 
            }

            stk.Push(i);
        }

        // Clear stack to reuse for right(i)
        stk.Clear();

        // Compute right(i) using a monotonic stack
        for (int i = n - 1; i >= 0; i--) {

            while (stk.Count > 0 && arr[stk.Peek()] <= arr[i]) {
                stk.Pop();
            }

            if (stk.Count > 0) {
                
                // Store 1-based index
                right[i] = stk.Peek() + 1; 
            }

            stk.Push(i);
        }

        int maxProduct = 0;

        // Compute the maximum LR product
        for (int i = 0; i < n; i++) {
            maxProduct = Math.Max(maxProduct, left[i] * right[i]);
        }

        return maxProduct;
    }

    // Driver code
    public static void Main() {

        int[] arr = {1, 1, 1, 1, 0, 1, 1, 1, 1, 1};

        Console.WriteLine(FindMaxLRProduct(arr));
    }
}
JavaScript 
// JavaScript program to find the maximum LR product 
// using stack and 2 Arrays

function findMaxLRProduct(arr) {
    
    let n = arr.length;
    let left = new Array(n).fill(0);
    let right = new Array(n).fill(0);
    let stk = [];

    // Compute left(i) using a monotonic stack
    for (let i = 0; i < n; i++) {

        while (stk.length > 0 && arr[stk[stk.length - 1]] <= arr[i]) {
            stk.pop();
        }

        if (stk.length > 0) {
            
            // Store 1-based index
            left[i] = stk[stk.length - 1] + 1; 
        }

        stk.push(i);
    }

    // Clear stack to reuse for right(i)
    stk = [];

    // Compute right(i) using a monotonic stack
    for (let i = n - 1; i >= 0; i--) {

        while (stk.length > 0 && arr[stk[stk.length - 1]] <= arr[i]) {
            stk.pop();
        }

        if (stk.length > 0) {
            
            // Store 1-based index
            right[i] = stk[stk.length - 1] + 1; 
        }

        stk.push(i);
    }

    let maxProduct = 0;

    // Compute the maximum LR product
    for (let i = 0; i < n; i++) {
        maxProduct = Math.max(maxProduct, left[i] * right[i]);
    }

    return maxProduct;
}

// Driver code
let arr = [1, 1, 1, 1, 0, 1, 1, 1, 1, 1];

console.log(findMaxLRProduct(arr));

Output
24

Using a Single Array – O(n) Time and O(n) Space

The idea is 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.

C++ 
// C++ program to find the maximum LR product 
// using a single stack
#include <bits/stdc++.h>
using namespace std;

// Function to find the maximum LR product
int findMaxLRProduct(vector<int>& arr) {
    
    int n = arr.size();
    vector<int> left(n, 0);
    stack<int> stk;
    int maxProduct = 0;

    // Compute left(i) and right(i) using a single stack
    for (int i = 0; i < n; i++) {

        while (!stk.empty() && arr[stk.top()] <= arr[i]) {
            stk.pop();
        }

        if (!stk.empty()) {
            
            // Store 1-based index for left
            left[i] = stk.top() + 1;
        }

        stk.push(i);
    }

    // Clear stack to reuse for right(i)
    while (!stk.empty()) {
        stk.pop();
    }

    // Compute right(i) and calculate max LR product
    for (int i = n - 1; i >= 0; i--) {

        while (!stk.empty() && arr[stk.top()] <= arr[i]) {
            stk.pop();
        }

        if (!stk.empty()) {
            
            // Compute LR product on the fly
            maxProduct = max(maxProduct, left[i] * (stk.top() + 1));
        }

        stk.push(i);
    }

    return maxProduct;
}

// Driver code
int main() {

    vector<int> arr = {1, 1, 1, 1, 0, 1, 1, 1, 1, 1};

    cout << findMaxLRProduct(arr) << endl;

    return 0;
}
Java 
// Java program to find the maximum LR product 
// using a single stack
import java.util.*;

class GfG {

    // Function to find the maximum LR product
    static int findMaxLRProduct(int[] arr) {
        
        int n = arr.length;
        int[] left = new int[n];
        Stack<Integer> stk = new Stack<>();
        int maxProduct = 0;

        // Compute left(i) and right(i) using a single stack
        for (int i = 0; i < n; i++) {

            while (!stk.isEmpty() && arr[stk.peek()] <= arr[i]) {
                stk.pop();
            }

            if (!stk.isEmpty()) {
                
                // Store 1-based index for left
                left[i] = stk.peek() + 1;
            }

            stk.push(i);
        }

        // Clear stack to reuse for right(i)
        stk.clear();

        // Compute right(i) and calculate max LR product
        for (int i = n - 1; i >= 0; i--) {

            while (!stk.isEmpty() && arr[stk.peek()] <= arr[i]) {
                stk.pop();
            }

            if (!stk.isEmpty()) {
                
                // Compute LR product on the fly
                maxProduct = Math.max(maxProduct, left[i] * (stk.peek() + 1));
            }

            stk.push(i);
        }

        return maxProduct;
    }

    // Driver code
    public static void main(String[] args) {

        int[] arr = {1, 1, 1, 1, 0, 1, 1, 1, 1, 1};

        System.out.println(findMaxLRProduct(arr));
    }
}
Python 
# Python program to find the maximum LR product 
# using a single stack

def find_max_lr_product(arr):
    
    n = len(arr)
    left = [0] * n
    stk = []
    max_product = 0

    # Compute left(i) and right(i) using a single stack
    for i in range(n):

        while stk and arr[stk[-1]] <= arr[i]:
            stk.pop()

        if stk:
            
            # Store 1-based index for left
            left[i] = stk[-1] + 1

        stk.append(i)

    # Clear stack to reuse for right(i)
    stk.clear()

    # Compute right(i) and calculate max LR product
    for i in range(n - 1, -1, -1):

        while stk and arr[stk[-1]] <= arr[i]:
            stk.pop()

        if stk:
            
            # Compute LR product on the fly
            max_product = max(max_product, left[i] * (stk[-1] + 1))

        stk.append(i)

    return max_product

# Driver code
if __name__ == "__main__":
    
    arr = [1, 1, 1, 1, 0, 1, 1, 1, 1, 1]

    print(find_max_lr_product(arr))
C# 
// C# program to find the maximum LR product 
// using a single stack
using System;
using System.Collections.Generic;

class GfG {

    // Function to find the maximum LR product
    public static int FindMaxLRProduct(int[] arr) {
        
        int n = arr.Length;
        int[] left = new int[n];
        Stack<int> stk = new Stack<int>();
        int maxProduct = 0;

        // Compute left(i) and right(i) using a single stack
        for (int i = 0; i < n; i++) {

            while (stk.Count > 0 && arr[stk.Peek()] <= arr[i]) {
                stk.Pop();
            }

            if (stk.Count > 0) {
                
                // Store 1-based index for left
                left[i] = stk.Peek() + 1;
            }

            stk.Push(i);
        }

        // Clear stack to reuse for right(i)
        stk.Clear();

        // Compute right(i) and calculate max LR product
        for (int i = n - 1; i >= 0; i--) {

            while (stk.Count > 0 && arr[stk.Peek()] <= arr[i]) {
                stk.Pop();
            }

            if (stk.Count > 0) {
                
                // Compute LR product on the fly
                maxProduct = Math.Max(maxProduct, left[i] * (stk.Peek() + 1));
            }

            stk.Push(i);
        }

        return maxProduct;
    }

    // Driver code
    public static void Main() {

        int[] arr = {1, 1, 1, 1, 0, 1, 1, 1, 1, 1};

        Console.WriteLine(FindMaxLRProduct(arr));
    }
}
JavaScript 
// JavaScript program to find the maximum LR product 
// using a single stack

function findMaxLRProduct(arr) {
    
    let n = arr.length;
    let left = new Array(n).fill(0);
    let stk = [];
    let maxProduct = 0;

    // Compute left(i) and right(i) using a single stack
    for (let i = 0; i < n; i++) {

        while (stk.length > 0 && arr[stk[stk.length - 1]] <= arr[i]) {
            stk.pop();
        }

        if (stk.length > 0) {
            
            // Store 1-based index for left
            left[i] = stk[stk.length - 1] + 1;
        }

        stk.push(i);
    }

    // Clear stack to reuse for right(i)
    stk = [];

    // Compute right(i) and calculate max LR product
    for (let i = n - 1; i >= 0; i--) {

        while (stk.length > 0 && arr[stk[stk.length - 1]] <= arr[i]) {
            stk.pop();
        }

        if (stk.length > 0) {
            
            // Compute LR product on the fly
            maxProduct = Math.max(maxProduct, left[i] * (stk[stk.length - 1] + 1));
        }

        stk.push(i);
    }

    return maxProduct;
}

// Driver code
let arr = [1, 1, 1, 1, 0, 1, 1, 1, 1, 1];

console.log(findMaxLRProduct(arr));

Output
24


We can further optimize this using a single for loop. Please refer Largest Area in a Histogram and try to solve this problem using single stack and single loop,




Next Article
Iterative Tower of Hanoi

R
Ravi_Maurya
Improve
Article Tags :

Similar Reads

We use cookies to ensure you have the best browsing experience on our website. By using our site, you acknowledge that you have read and understood our Cookie Policy & Privacy Policy
Lightbox
  翻译：