Largest Rectangular Area in a Histogram using Stack

Last Updated : 11 Sep, 2023

Find the largest rectangular area possible in a given histogram where the largest rectangle can be made of a number of contiguous bars whose heights are given in an array. For simplicity, assume that all bars have the same width and the width is 1 unit.

Example:

Input: histogram = {6, 2, 5, 4, 5, 1, 6}

Output: 12

Input: histogram = {3, 5, 1, 7, 5, 9}
Output: 15

To solve the problem follow the below idea:

For every bar ‘x’, we calculate the area with ‘x’ as the smallest bar in the rectangle. If we calculate the such area for every bar ‘x’ and find the maximum of all areas, our task is done.

How to calculate the area with ‘x’ as the smallest bar?

We need to know the index of the first smaller (smaller than ‘x’) bar on the left of ‘x’ and the index of the first smaller bar on the right of ‘x’. Let us call these indexes as ‘left index’ and ‘right index’ respectively. We traverse all bars from left to right and maintain a stack of bars. Every bar is pushed to stack once. A bar is popped from the stack when a bar of smaller height is seen. When a bar is popped, we calculate the area with the popped bar as the smallest bar.

How do we get the left and right indexes of the popped bar?

The current index tells us the right index and the index of the previous item in the stack is the left index

Follow the given steps to solve the problem:

Create an empty stack.
Start from the first bar, and do the following for every bar hist[i] where ‘i‘ varies from 0 to n-1
1. If the stack is empty or hist[i] is higher than the bar at top of the stack, then push ‘i‘ to stack.
2. If this bar is smaller than the top of the stack, then keep removing the top of the stack while the top of the stack is greater.
3. Let the removed bar be hist[tp]. Calculate the area of the rectangle with hist[tp] as the smallest bar.
4. For hist[tp], the ‘left index’ is previous (previous to tp) item in stack and ‘right index’ is ‘i‘ (current index).
If the stack is not empty, then one by one remove all bars from the stack and do step (2.2 and 2.3) for every removed bar

Below is the implementation of the above approach.

C++

// C++ program to find maximum rectangular area in 
// linear time 
#include <bits/stdc++.h> 
using namespace std; 
  
// The main function to find the maximum rectangular 
// area under given histogram with n bars 
int getMaxArea(int hist[], int n) 
{ 
    // Create an empty stack. The stack holds indexes 
    // of hist[] array. The bars stored in stack are 
    // always in increasing order of their heights. 
    stack<int> s; 
  
    int max_area = 0; // Initialize max area 
    int tp; // To store top of stack 
    int area_with_top; // To store area with top bar 
                       // as the smallest bar 
  
    // Run through all bars of given histogram 
    int i = 0; 
    while (i < n) { 
        // If this bar is higher than the bar on top 
        // stack, push it to stack 
        if (s.empty() || hist[s.top()] <= hist[i]) 
            s.push(i++); 
  
        // If this bar is lower than top of stack, 
        // then calculate area of rectangle with stack 
        // top as the smallest (or minimum height) bar. 
        // 'i' is 'right index' for the top and element 
        // before top in stack is 'left index' 
        else { 
            tp = s.top(); // store the top index 
            s.pop(); // pop the top 
  
            // Calculate the area with hist[tp] stack 
            // as smallest bar 
            area_with_top 
                = hist[tp] 
                  * (s.empty() ? i : i - s.top() - 1); 
  
            // update max area, if needed 
            if (max_area < area_with_top) 
                max_area = area_with_top; 
        } 
    } 
  
    // Now pop the remaining bars from stack and calculate 
    // area with every popped bar as the smallest bar 
    while (s.empty() == false) { 
        tp = s.top(); 
        s.pop(); 
        area_with_top 
            = hist[tp] * (s.empty() ? i : i - s.top() - 1); 
  
        if (max_area < area_with_top) 
            max_area = area_with_top; 
    } 
  
    return max_area; 
} 
  
// Driver code 
int main() 
{ 
    int hist[] = { 6, 2, 5, 4, 5, 1, 6 }; 
    int n = sizeof(hist) / sizeof(hist[0]); 
  
    // Function call 
    cout << "Maximum area is " << getMaxArea(hist, n); 
    return 0; 
}

Java

// Java program to find maximum rectangular area in linear 
// time 
  
import java.util.Stack; 
  
public class RectArea { 
    // The main function to find the maximum rectangular 
    // area under given histogram with n bars 
    static int getMaxArea(int hist[], int n) 
    { 
        // Create an empty stack. The stack holds indexes of 
        // hist[] array The bars stored in stack are always 
        // in increasing order of their heights. 
        Stack<Integer> s = new Stack<>(); 
  
        int max_area = 0; // Initialize max area 
        int tp; // To store top of stack 
        int area_with_top; // To store area with top bar as 
                           // the smallest bar 
  
        // Run through all bars of given histogram 
        int i = 0; 
        while (i < n) { 
            // If this bar is higher than the bar on top 
            // stack, push it to stack 
            if (s.empty() || hist[s.peek()] <= hist[i]) 
                s.push(i++); 
  
            // If this bar is lower than top of stack, then 
            // calculate area of rectangle with stack top as 
            // the smallest (or minimum height) bar. 'i' is 
            // 'right index' for the top and element before 
            // top in stack is 'left index' 
            else { 
                tp = s.peek(); // store the top index 
                s.pop(); // pop the top 
  
                // Calculate the area with hist[tp] stack as 
                // smallest bar 
                area_with_top 
                    = hist[tp] 
                      * (s.empty() ? i : i - s.peek() - 1); 
  
                // update max area, if needed 
                if (max_area < area_with_top) 
                    max_area = area_with_top; 
            } 
        } 
  
        // Now pop the remaining bars from stack and 
        // calculate area with every popped bar as the 
        // smallest bar 
        while (s.empty() == false) { 
            tp = s.peek(); 
            s.pop(); 
            area_with_top 
                = hist[tp] 
                  * (s.empty() ? i : i - s.peek() - 1); 
  
            if (max_area < area_with_top) 
                max_area = area_with_top; 
        } 
  
        return max_area; 
    } 
  
    // Driver code 
    public static void main(String[] args) 
    { 
        int hist[] = { 6, 2, 5, 4, 5, 1, 6 }; 
  
        // Function call 
        System.out.println("Maximum area is "
                           + getMaxArea(hist, hist.length)); 
    } 
} 
// This code is Contributed by Sumit Ghosh

Python3

# Python3 program to find maximum 
# rectangular area in linear time 
  
  
def max_area_histogram(histogram): 
  
    # This function calculates maximum 
    # rectangular area under given 
    # histogram with n bars 
  
    # Create an empty stack. The stack 
    # holds indexes of histogram[] list. 
    # The bars stored in the stack are 
    # always in increasing order of 
    # their heights. 
    stack = list() 
  
    max_area = 0  # Initialize max area 
  
    # Run through all bars of 
    # given histogram 
    index = 0
    while index < len(histogram): 
  
        # If this bar is higher 
        # than the bar on top 
        # stack, push it to stack 
  
        if (not stack) or (histogram[stack[-1]] <= histogram[index]): 
            stack.append(index) 
            index += 1
  
        # If this bar is lower than top of stack, 
        # then calculate area of rectangle with 
        # stack top as the smallest (or minimum 
        # height) bar.'i' is 'right index' for 
        # the top and element before top in stack 
        # is 'left index' 
        else: 
            # pop the top 
            top_of_stack = stack.pop() 
  
            # Calculate the area with 
            # histogram[top_of_stack] stack 
            # as smallest bar 
            area = (histogram[top_of_stack] *
                    ((index - stack[-1] - 1) 
                     if stack else index)) 
  
            # update max area, if needed 
            max_area = max(max_area, area) 
  
    # Now pop the remaining bars from 
    # stack and calculate area with 
    # every popped bar as the smallest bar 
    while stack: 
  
        # pop the top 
        top_of_stack = stack.pop() 
  
        # Calculate the area with 
        # histogram[top_of_stack] 
        # stack as smallest bar 
        area = (histogram[top_of_stack] *
                ((index - stack[-1] - 1) 
                 if stack else index)) 
  
        # update max area, if needed 
        max_area = max(max_area, area) 
  
    # Return maximum area under 
    # the given histogram 
    return max_area 
  
  
# Driver Code 
if __name__ == '__main__': 
    hist = [6, 2, 5, 4, 5, 1, 6] 
  
    # Function call 
    print("Maximum area is", 
          max_area_histogram(hist)) 
  
# This code is contributed 
# by Jinay Shah 

C#

// C# program to find maximum 
// rectangular area in linear time 
using System; 
using System.Collections.Generic; 
  
class GFG { 
    // The main function to find the 
    // maximum rectangular area under 
    // given histogram with n bars 
    public static int getMaxArea(int[] hist, int n) 
    { 
        // Create an empty stack. The stack 
        // holds indexes of hist[] array 
        // The bars stored in stack are always 
        // in increasing order of their heights. 
        Stack<int> s = new Stack<int>(); 
  
        int max_area = 0; // Initialize max area 
        int tp; // To store top of stack 
        int area_with_top; // To store area with top 
                           // bar as the smallest bar 
  
        // Run through all bars of 
        // given histogram 
        int i = 0; 
        while (i < n) { 
            // If this bar is higher than the 
            // bar on top stack, push it to stack 
            if (s.Count == 0 || hist[s.Peek()] <= hist[i]) { 
                s.Push(i++); 
            } 
  
            // If this bar is lower than top of stack, 
            // then calculate area of rectangle with 
            // stack top as the smallest (or minimum 
            // height) bar. 'i' is 'right index' for 
            // the top and element before top in stack 
            // is 'left index' 
            else { 
                tp = s.Peek(); // store the top index 
                s.Pop(); // pop the top 
  
                // Calculate the area with hist[tp] 
                // stack as smallest bar 
                area_with_top 
                    = hist[tp] 
                      * (s.Count == 0 ? i 
                                      : i - s.Peek() - 1); 
  
                // update max area, if needed 
                if (max_area < area_with_top) { 
                    max_area = area_with_top; 
                } 
            } 
        } 
  
        // Now pop the remaining bars from 
        // stack and calculate area with every 
        // popped bar as the smallest bar 
        while (s.Count > 0) { 
            tp = s.Peek(); 
            s.Pop(); 
            area_with_top 
                = hist[tp] 
                  * (s.Count == 0 ? i : i - s.Peek() - 1); 
  
            if (max_area < area_with_top) { 
                max_area = area_with_top; 
            } 
        } 
  
        return max_area; 
    } 
  
    // Driver Code 
    public static void Main(string[] args) 
    { 
        int[] hist = new int[] { 6, 2, 5, 4, 5, 1, 6 }; 
  
        // function call 
        Console.WriteLine("Maximum area is "
                          + getMaxArea(hist, hist.Length)); 
    } 
} 
  
// This code is contributed by Shrikant13

Javascript

<script> 
  
// JavaScript program to find maximum 
// rectangular area in linear time 
  
function max_area_histogram(histogram){ 
      
    // This function calculates maximum 
    // rectangular area under given 
    // histogram with n bars 
  
    // Create an empty stack. The stack 
    // holds indexes of histogram[] list. 
    // The bars stored in the stack are 
    // always in increasing order of 
    // their heights. 
    let stack = [] 
  
    let max_area = 0 // Initialize max area 
  
    // Run through all bars of 
    // given histogram 
    let index = 0 
    while(index < histogram.length){ 
          
        // If this bar is higher 
        // than the bar on top 
        // stack, push it to stack 
  
        if(stack.length == 0 || histogram[stack[stack.length-1]] <= histogram[index]){ 
            stack.push(index) 
            index += 1 
        } 
  
        // If this bar is lower than top of stack, 
        // then calculate area of rectangle with 
        // stack top as the smallest (or minimum 
        // height) bar.'i' is 'right index' for 
        // the top and element before top in stack 
        // is 'left index' 
        else{ 
            // pop the top 
            let top_of_stack = stack.pop() 
  
            // Calculate the area with 
            // histogram[top_of_stack] stack 
            // as smallest bar 
            let area = (histogram[top_of_stack] * 
                (stack.length > 0 ? (index - stack[stack.length-1] - 1) : index)) 
  
            // update max area, if needed 
            max_area = Math.max(max_area, area) 
        } 
    } 
    // Now pop the remaining bars from 
    // stack and calculate area with 
    // every popped bar as the smallest bar 
    while(stack.length > 0){ 
          
        // pop the top 
        let top_of_stack = stack.pop() 
  
        // Calculate the area with 
        // histogram[top_of_stack] 
        // stack as smallest bar 
        let area = (histogram[top_of_stack] * 
            (stack.length > 0 ? (index - stack[stack.length-1] - 1) : index)) 
  
        // update max area, if needed 
        max_area = Math.max(max_area, area) 
    } 
  
    // Return maximum area under 
    // the given histogram 
    return max_area 
} 
  
// Driver Code 
let hist = [6, 2, 5, 4, 5, 1, 6] 
document.write("Maximum area is", max_area_histogram(hist)) 
  
// This code is contributed 
// by shinjanpatra 
  
</script>

Output

Maximum area is 12

Time Complexity: O(N), Since every bar is pushed and popped only once
Auxiliary Space: O(N)

Largest Rectangular Area in a Histogram by finding the next and the previous smaller element:

To solve the problem follow the below idea:

Find the previous and the next smaller element for every element of the histogram, as this would help to calculate the length of the subarray in which this current element is the minimum element. So we can create a rectangle of size (current element * length of the subarray) using this element. Take the maximum of all such rectangles.

Follow the given steps to solve the problem:

First, we will take two arrays left_smaller[] and right_smaller[] and initialize them with -1 and n respectively
For every element, we will store the index of the previous smaller and next smaller element in left_smaller[] and right_smaller[] arrays respectively
Now for every element, we will calculate the area by taking this i^th element as the smallest in the range left_smaller[i] and right_smaller[i] and multiplying it with the difference of left_smaller[i] and right_smaller[i]
We can find the maximum of all the areas calculated in step 3 to get the desired maximum area

Below is the implementation of the above approach.

C++

// C++ code for the above approach 
  
#include <bits/stdc++.h> 
using namespace std; 
  
// Function to find largest rectangular area possible in a 
// given histogram. 
int getMaxArea(int arr[], int n) 
{ 
    // Your code here 
    // we create an empty stack here. 
    stack<int> s; 
    // we push -1 to the stack because for some elements 
    // there will be no previous smaller element in the 
    // array and we can store -1 as the index for previous 
    // smaller. 
    s.push(-1); 
    int area = arr[0]; 
    int i = 0; 
    // We declare left_smaller and right_smaller array of 
    // size n and initialize them with -1 and n as their 
    // default value. left_smaller[i] will store the index 
    // of previous smaller element for ith element of the 
    // array. right_smaller[i] will store the index of next 
    // smaller element for ith element of the array. 
    vector<int> left_smaller(n, -1), right_smaller(n, n); 
    while (i < n) { 
        while (!s.empty() && s.top() != -1 
               && arr[s.top()] > arr[i]) { 
            // if the current element is smaller than 
            // element with index stored on the top of stack 
            // then, we pop the top element and store the 
            // current element index as the right_smaller 
            // for the popped element. 
            right_smaller[s.top()] = i; 
            s.pop(); 
        } 
        if (i > 0 && arr[i] == arr[i - 1]) { 
            // we use this condition to avoid the 
            // unnecessary loop to find the left_smaller. 
            // since the previous element is same as current 
            // element, the left_smaller will always be the 
            // same for both. 
            left_smaller[i] = left_smaller[i - 1]; 
        } 
        else { 
            // Element with the index stored on the top of 
            // the stack is always smaller than the current 
            // element. Therefore the left_smaller[i] will 
            // always be s.top(). 
            left_smaller[i] = s.top(); 
        } 
        s.push(i); 
        i++; 
    } 
    for (int j = 0; j < n; j++) { 
        // here we find area with every element as the 
        // smallest element in their range and compare it 
        // with the previous area. 
        // in this way we get our max Area form this. 
        area = max(area, arr[j] 
                             * (right_smaller[j] 
                                - left_smaller[j] - 1)); 
    } 
    return area; 
} 
  
// Driver code 
int main() 
{ 
    int hist[] = { 6, 2, 5, 4, 5, 1, 6 }; 
    int n = sizeof(hist) / sizeof(hist[0]); 
  
    // Function call 
    cout << "maxArea = " << getMaxArea(hist, n) << endl; 
    return 0; 
} 
  
// This code is Contributed by Arunit Kumar.

Java

// Java code for the above approach 
  
import java.io.*; 
import java.lang.*; 
import java.util.*; 
  
public class RectArea { 
  
    // Function to find largest rectangular area possible in 
    // a given histogram. 
    public static int getMaxArea(int arr[], int n) 
    { 
        // your code here 
        // we create an empty stack here. 
        Stack<Integer> s = new Stack<>(); 
        // we push -1 to the stack because for some elements 
        // there will be no previous smaller element in the 
        // array and we can store -1 as the index for 
        // previous smaller. 
        s.push(-1); 
        int max_area = arr[0]; 
        // We declare left_smaller and right_smaller array 
        // of size n and initialize them with -1 and n as 
        // their default value. left_smaller[i] will store 
        // the index of previous smaller element for ith 
        // element of the array. right_smaller[i] will store 
        // the index of next smaller element for ith element 
        // of the array. 
        int left_smaller[] = new int[n]; 
        int right_smaller[] = new int[n]; 
        for (int i = 0; i < n; i++) { 
            left_smaller[i] = -1; 
            right_smaller[i] = n; 
        } 
  
        int i = 0; 
        while (i < n) { 
            while (!s.empty() && s.peek() != -1
                   && arr[i] < arr[s.peek()]) { 
                // if the current element is smaller than 
                // element with index stored on the top of 
                // stack then, we pop the top element and 
                // store the current element index as the 
                // right_smaller for the popped element. 
                right_smaller[s.peek()] = (int)i; 
                s.pop(); 
            } 
            if (i > 0 && arr[i] == arr[(i - 1)]) { 
                // we use this condition to avoid the 
                // unnecessary loop to find the 
                // left_smaller. since the previous element 
                // is same as current element, the 
                // left_smaller will always be the same for 
                // both. 
                left_smaller[i] 
                    = left_smaller[(int)(i - 1)]; 
            } 
            else { 
                // Element with the index stored on the top 
                // of the stack is always smaller than the 
                // current element. Therefore the 
                // left_smaller[i] will always be s.top(). 
                left_smaller[i] = s.peek(); 
            } 
            s.push(i); 
            i++; 
        } 
  
        for (i = 0; i < n; i++) { 
            // here we find area with every element as the 
            // smallest element in their range and compare 
            // it with the previous area. in this way we get 
            // our max Area form this. 
            max_area = Math.max( 
                max_area, arr[i] 
                              * (right_smaller[i] 
                                 - left_smaller[i] - 1)); 
        } 
  
        return max_area; 
    } 
  
    // Driver code 
    public static void main(String[] args) 
    { 
        int hist[] = { 6, 2, 5, 4, 5, 1, 6 }; 
  
        // Function call 
        System.out.println("Maximum area is "
                           + getMaxArea(hist, hist.length)); 
    } 
} 
// This code is Contributed by Arunit Kumar.

Python3

# Python3 code for the above approach 
  
  
def getMaxArea(arr): 
    s = [-1] 
    n = len(arr) 
    area = 0
    i = 0
    left_smaller = [-1]*n 
    right_smaller = [n]*n 
    while i < n: 
        while s and (s[-1] != -1) and (arr[s[-1]] > arr[i]): 
            right_smaller[s[-1]] = i 
            s.pop() 
        if((i > 0) and (arr[i] == arr[i-1])): 
            left_smaller[i] = left_smaller[i-1] 
        else: 
            left_smaller[i] = s[-1] 
        s.append(i) 
        i += 1
    for j in range(0, n): 
        area = max(area, arr[j]*(right_smaller[j]-left_smaller[j]-1)) 
    return area 
  
  
# Driver code 
if __name__ == '__main__': 
    hist = [6, 2, 5, 4, 5, 1, 6] 
  
    # Function call 
    print("maxArea = ", getMaxArea(hist)) 
  
# This code is contributed by Arunit Kumar 

C#

// C# code for the above approach 
  
using System; 
using System.Collections.Generic; 
public class RectArea { 
  
    // Function to find largest rectangular area possible in 
    // a given histogram. 
    public static int getMaxArea(int[] arr, int n) 
    { 
  
        // your code here 
        // we create an empty stack here. 
        Stack<int> s = new Stack<int>(); 
  
        // we push -1 to the stack because for some elements 
        // there will be no previous smaller element in the 
        // array and we can store -1 as the index for 
        // previous smaller. 
        s.Push(-1); 
        int max_area = arr[0]; 
  
        // We declare left_smaller and right_smaller array 
        // of size n and initialize them with -1 and n as 
        // their default value. left_smaller[i] will store 
        // the index of previous smaller element for ith 
        // element of the array. 
        // right_smaller[i] will store the index of next 
        // smaller element for ith element of the array. 
        int[] left_smaller = new int[n]; 
        int[] right_smaller = new int[n]; 
        for (int j = 0; j < n; j++) { 
            left_smaller[j] = -1; 
            right_smaller[j] = n; 
        } 
  
        int i = 0; 
        while (i < n) { 
            while (s.Count != 0 && s.Peek() != -1 
                   && arr[i] < arr[s.Peek()]) { 
  
                // if the current element is smaller than 
                // element with index stored on the top of 
                // stack then, we pop the top element and 
                // store the current element index as the 
                // right_smaller for the popped element. 
                right_smaller[s.Peek()] = (int)i; 
                s.Pop(); 
            } 
            if (i > 0 && arr[i] == arr[(i - 1)]) { 
  
                // we use this condition to avoid the 
                // unnecessary loop to find the 
                // left_smaller. since the previous element 
                // is same as current element, the 
                // left_smaller will always be the same for 
                // both. 
                left_smaller[i] 
                    = left_smaller[(int)(i - 1)]; 
            } 
            else { 
  
                // Element with the index stored on the top 
                // of the stack is always smaller than the 
                // current element. Therefore the 
                // left_smaller[i] will always be s.top(). 
                left_smaller[i] = s.Peek(); 
            } 
            s.Push(i); 
            i++; 
        } 
  
        for (i = 0; i < n; i++) { 
  
            // here we find area with every element as the 
            // smallest element in their range and compare 
            // it with the previous area. in this way we get 
            // our max Area form this. 
            max_area = Math.Max( 
                max_area, arr[i] 
                              * (right_smaller[i] 
                                 - left_smaller[i] - 1)); 
        } 
  
        return max_area; 
    } 
  
    // Driver code 
    public static void Main(String[] args) 
    { 
        int[] hist = { 6, 2, 5, 4, 5, 1, 6 }; 
  
        // Function call 
        Console.WriteLine("Maximum area is "
                          + getMaxArea(hist, hist.Length)); 
    } 
} 
  
// This code is contributed by Rajput-Ji

Javascript

<script> 
  
  
//Function to find largest rectangular area possible in a given histogram. 
function getMaxArea(arr, n) 
{ 
    // Your code here 
    //we create an empty stack here. 
    let s = []; 
    //we push -1 to the stack because for some elements there will be no previous 
    //smaller element in the array and we can store -1 as the index for previous smaller. 
    s.push(-1); 
    let area = arr[0]; 
    let i = 0; 
    //We declare left_smaller and right_smaller array of size n and initialize them with -1 and n as their default value. 
    //left_smaller[i] will store the index of previous smaller element for ith element of the array. 
    //right_smaller[i] will store the index of next smaller element for ith element of the array. 
    let left_smaller = new Array(n).fill(-1), right_smaller = new Array(n).fill(n); 
    while(i<n){ 
        while(s.length > 0 &&s[s.length-1]!=-1&&arr[s[s.length-1]]>arr[i]){ 
            //if the current element is smaller than element with index stored on the  
            //top of stack then, we pop the top element and store the current element index 
            //as the right_smaller for the popped element. 
            right_smaller[s[s.length-1]] = i; 
            s.pop(); 
        } 
        if(i>0&&arr[i]==arr[i-1]){ 
            //we use this condition to avoid the unnecessary loop to find the left_smaller. 
            //since the previous element is same as current element, the left_smaller will always be the same for both. 
            left_smaller[i] = left_smaller[i-1]; 
        }else{ 
            //Element with the index stored on the top of the stack is always smaller than the current element. 
            //Therefore the left_smaller[i] will always be s[s.length-1]. 
            left_smaller[i] = s[s.length-1]; 
        }   
        s.push(i); 
        i++; 
    } 
    for(let j = 0; j<n; j++){ 
        //here we find area with every element as the smallest element in their range and compare it with the previous area. 
        // in this way we get our max Area form this. 
        area = Math.max(area, arr[j]*(right_smaller[j]-left_smaller[j]-1)); 
    } 
    return area; 
} 
  
// driver code 
  
let hist = [6, 2, 5, 4, 5, 1, 6]; 
let n = hist.length; 
document.write("maxArea = " + getMaxArea(hist, n)); 
  
// This code is contributed by shinjanpatra 
  
</script>

Output

maxArea = 12

Time Complexity: O(N)
Auxiliary Space: O(N)

Related Articles: Divide and Conquer based O(N log N) solution

Thanks to Ashish Anand for suggesting initial solution.

GeeksforGeeks

Improve

Previous Article

Check if an array is stack sortable

Find maximum of minimum for every window size in a given array

Similar Reads

Largest Rectangular Area in a Histogram using Segment Tree

Find the largest rectangular area possible in a given histogram where the largest rectangle can be made of a number of contiguous bars. For simplicity, assume that all bars have same width and the width is 1 unit. For example, consider the following histogram with 7 bars of heights {6, 2, 5, 4, 5, 1, 6}. The largest possible rectangle possible is 1

Largest Rectangle Area under Histogram using JavaScript | Without using Stacks

Find the largest rectangular area possible in a given histogram where the largest rectangle can be made of a number of contiguous bars. For simplicity, assume that all bars have the same width and the width is 1 unit. For example, consider the following histogram with 7 bars of heights {6, 2, 5, 4, 5, 1, 6}. The largest possible rectangle possible

Find the largest area rectangular sub-matrix whose sum is equal to k

Given a 2D matrix mat[][] and a value k. Find the largest rectangular sub-matrix whose sum is equal to k. Example: Input : mat = { { 1, 7, -6, 5 }, { -8, 6, 7, -2 }, { 10, -15, 3, 2 }, { -5, 2, 0, 9 } } k = 7 Output : (Top, Left): (0, 1) (Bottom, Right): (2, 3) 7 -6 5 6 7 -2 -15 3 2 Brute Approach: The program takes in a matrix of integers and an i

Largest area rectangular sub-matrix with equal number of 1's and 0's

Given a binary matrix. The problem is to find the largest area rectangular sub-matrix with equal number of 1's and 0's. Examples: Input : mat[][] = { {0, 0, 1, 1}, {0, 1, 1, 0}, {1, 1, 1, 0}, {1, 0, 0, 1} } Output : 8 sq. units (Top, left): (0, 0) (Bottom, right): (3, 1) Input : mat[][] = { {0, 0, 1, 1}, {0, 1, 1, 1} } Output : 6 sq. units The naiv

Largest square which can be formed using given rectangular blocks

Given an array arr[] of positive integers where each element of the array represents the length of the rectangular blocks. The task is to find the largest length of the square which can be formed using the rectangular blocks. Examples: Input: arr[] = {3, 2, 1, 5, 2, 4} Output: 3 Explanation: Using rectangular block of length 3, 5 and 4, square of s

Maximum of smallest possible area that can get with exactly k cut of given rectangular

Given n×m big rectangular area with unit squares and k times cut is allowed, the cut should be straight (horizontal or vertical) and should go along the edges of the unit square. What is the maximum possible area of the smallest piece he can get with exactly k cuts. Examples : Input : 3 4 1 Output : 6 Input : 6 4 2 Output : 8 Image for 2nd input Im

Largest rectangular sub-matrix having sum divisible by k

Given a n x n matrix of integers. The problem is to find the largest area rectangular sub-matrix having sum divisible by the given value k. Examples: Input : mat[][] = { {1, 2, -1, -4} {-8, -3, 4, 2}, {3, 8, 10, 1} {-4, -1, 1, 7} } k = 5Output : Area = 12Explanation: (Top, Left): (0, 0) (Bottom, Right): (2, 3)The sub-matrix is:| 1, 2, -1, -4 || -8,

Largest rectangular sub-matrix whose sum is 0

Given a 2D matrix, find the largest rectangular sub-matrix whose sum is 0. for example consider the following N x M input matrix Examples: Input : 1, 2, 3 -3, -2, -1 1, 7, 5Output : 1, 2, 3 -3, -2, -1Input : 9, 7, 16, 5 1, -6, -7, 3 1, 8, 7, 9 7, -2, 0, 10Output :-6, -7 8, 7 -2, 0 Recommended PracticeLargest rectangular sub-matrix whose sum is 0Try

Counting Triangles in a Rectangular space using BIT

Pre-requisite: BIT(Binary Indexed Tree or Fenwick Tree), 2D BITGiven a 2D plane, respond to Q queries, each of the following type: Insert x y - Insert a point (x, y) coordinate.Triangle x1 y1 x2 y2 - Print the number of triangles that can be formed, by joining the points inside the rectangle, described by two points (x1, y1) and (x2, y2), (x1, y1)

Infix to Postfix using different Precedence Values for In-Stack and Out-Stack

Conversion of infix to postfix expression can be done elegantly using two precedence function. Each operator is assigned a value (larger value means higher precedence) which depends upon whether the operator is inside or outside the stack. Also the right and left associativity for different operators can be handled by varying it's values in the two

Article Tags :

Practice Tags :