Maximum area histogram

Write a program to find the maximum area under histogram or largest rectangle in a histogram. It’s optimized solution can be obtained using stack.

Problem

Find the largest rectangular area possible in a given histogram where the largest rectangle can be made of a number of contiguous bars. Assume that all bars have the same width and the width is 1 unit.

Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

For example, consider the following histogram. Here, the area can be calculated over many bars.

But, the maximum area is under the highlighted bars i.e, 4 * 3 = 12.

This is what we have to calculate.

Example -

Input: [2, 1, 5, 6, 2, 3]
Output: 10
Input: [6, 2, 5, 4, 5, 1, 6]
Output: 12

We will see following two ways to solve the problems

1. Brute-force approach (using nested loops)
2. Using stack

Brute-force approach (using nested loops)

In this approach, we will nested loops. The outer loop will iterate over all the array items and two inner loop will iterate over all the next and previous elements of currently pointed by the outer loop. Inner loops will check, smaller element in the left and right and then the area of rectangle can be calculated and compared.

Python

def max_area_histogram(arr):
    max_area = 0

    for i in range(len(arr)):
        for j in range(i, len(arr)):
            min_height = min(arr[i], arr[j])
            for k in range(i, j):
                min_height = min(min_height, arr[k])

            max_area = max(max_area, min_height * ((j - i) + 1))
    return max_area


arr = [6, 2, 5, 4, 5, 1, 6]
print(max_area_histogram(arr))

JavaScript

function maxAreaHistogram(arr) {
    let maxArea = 0;

    for (let i = 0; i < arr.length; i++) {
        for (let j = i; j < arr.length; j++) {
            minHeight = Math.min(arr[i], arr[j]);
            for (let k = i; k < j; k++) {
                minHeight = Math.min(minHeight, arr[k]);
            }
            maxArea = Math.max(maxArea, minHeight * ((j - i) + 1));
        }
    }
    return maxArea;
}

arr = [6, 2, 5, 4, 5, 1, 6];
console.log(maxAreaHistogram(arr));

Although, we have solved this problem using just loops but this is not an optimized solution.
Because the time complexity of this solution is O(n3).

Using stack

If we observe the problem, for every bar we have to check the index of nearest smaller to left and nearest smaller to the right because if we can find these two parameters then we got the width of that area under which maximum area resides by simply subtracting these parameters.

For better understanding check these problems Nearest smaller to left and Nearest smaller to right and for finding index go through Stock span problem.

For example, consider the following diagram

To make our calculation easier consider that left most smallest element is at -1 and rightmost smallest number is at the index equal to the length of the array (here 7) then only we can subtract the width and get the appropriate value.

For index 3 having height 4, index of nearest smaller to left is 1 and nearest smaller to right is 5.

Now, subtract nearest smaller to left from nearest smaller to right and extra 1 because we are taking two extra bars from both sides i.e., 5–1–1 = 3.

So, 3 will be the width of total bars or area which can be covered by the index 3 bar having height 4 because we have assumed that the width of each bar is of 1 unit.

Now, we can calculate the area under the span of this bar i.e., 4 * 3 = 12.

So, we can say that

WIDTH = NEAREST SMALLER TO RIGHT - NEAREST SMALLER TO LEFT - 1

And, then we can calculate the area because the height is already known.

We, have to do this for each bar and store the values in an array then find the maximum value among them.

Python

JavaScript

Slightly better approach with less number of lines

Python

JavaScript

To read more such article based on data structures check out ProCoding.org