Maximum area histogram

Category: Data Structures
Tags: #datastructures#stack

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.

Maximum area histogram

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 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, area can be calculated over many bars.

Maximum area histogram example 1

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

Maximum area histogram example 2

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. 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 outer loop. Inner loops will check, smaller element in the left and right and then 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));

Output

[-1, -1, 4, -1, 2]

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

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

Maximum area histogram example 3

To make our calculation easier consider that left most smallest element is at -1 and right most smallest number is at index equal to length of 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 width of each bar is of 1 unit.

Now, we can calculate 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.

Program

Python
class Stack:
    def __init__(self):
        self.stack = []

    def isEmpty(self):
        return len(self.stack) == 0

    def push(self, num):
        self.stack.append(num)

    def pop(self):
        if self.isEmpty():
            raise Exception('Stack Underflow')
        return self.stack.pop()

    def peek(self):
        if self.isEmpty():
            return None
        return self.stack[-1]

def nearestSmallerToRight(arr):
    stack = Stack()
    result = []

    for i in range(len(arr)-1, -1, -1):
        if stack.isEmpty():
            result.append(len(arr))
            stack.push([arr[i], i])
        elif not stack.isEmpty():
            while(not stack.isEmpty() and arr[i] <= stack.peek()[0]): # to check equal values
                stack.pop()
            if stack.isEmpty():
                result.append(len(arr))
            else:
                result.append(stack.peek()[1])
            stack.push([arr[i], i])

    result.reverse()
    return result

def nearestSmallerToLeft(arr):
    stack = Stack()
    result = []

    for i in range(0, len(arr)):
        if stack.isEmpty():
            result.append(-1)
            stack.push([arr[i], i])
        elif not stack.isEmpty():
            while(not stack.isEmpty() and arr[i] <= stack.peek()[0]): # to check equal values
                stack.pop()
            if stack.isEmpty():
                result.append(-1)
            else:
                result.append(stack.peek()[1])
            stack.push([arr[i], i])

    return result

def max_area_histogram(arr):
    NSL = nearestSmallerToLeft(arr)
    NSR = nearestSmallerToRight(arr)

    WIDTH = []
        
    for i in range(0, len(arr)):
        WIDTH.append(NSR[i] - NSL[i] - 1)

    AREA = []
        
    for i in range(0, len(arr)):
        AREA.append(arr[i] * WIDTH[i])

    return max(AREA)

arr = [6, 2, 5, 4, 5, 1, 6]

print(max_area_histogram(arr))
JavaScript
class Stack {
    constructor() {
        this.stack = [];
    }
    
    isEmpty() {
        return this.stack.length === 0;
    }
    
    push(num) {
        this.stack.push(num);
    }
    
    pop() {
        if (this.isEmpty())
            throw 'Stack underflow';
        return this.stack.pop();
    }
    
    peek() {
        if (this.isEmpty())
            return null;
        return this.stack[this.stack.length - 1];
    }
}

function nearestSmallerToRight(arr) {
    const stack = new Stack();
    const result = [];

    for (let i = arr.length; i >= 0; i--) {
        if (stack.isEmpty()) {
            result.push(arr.length);
            stack.push([arr[i], i]);
        } else if (!stack.isEmpty()) {
            while (!stack.isEmpty() && arr[i] <= stack.peek()[0]) {
                stack.pop();
            }
            if (stack.isEmpty()) {
                result.push(arr.length);
            } else {
                result.push(stack.peek()[1]);
            }
            stack.push([arr[i], i]);
        }
    }

    result.reverse();
    return result;
}

function nearestSmallerToLeft(arr) {
    const stack = new Stack();
    const result = [];

    for (let i = 0; i < arr.length; i++) {
        if (stack.isEmpty()) {
            result.push(-1);
            stack.push([arr[i], i]);
        } else if (!stack.isEmpty()) {
            while (!stack.isEmpty() && arr[i] <= stack.peek()[0]) {
                stack.pop();
            }
            if (stack.isEmpty()) {
                result.push(-1);
            } else {
                result.push(stack.peek()[1]);
            }
            stack.push([arr[i], i]);
        }
    }

    return result;
}

function max_area_histogram(arr) {
    const NSL = nearestSmallerToLeft(arr);
    const NSR = nearestSmallerToRight(arr);

    const WIDTH = [];
        
    for (let i = 0; i < arr.length; i++)
        WIDTH.push(NSR[i] - NSL[i] - 1);

    const AREA = []
        
    for (let i = 0; i < arr.length; i++)
        AREA.push(arr[i] * WIDTH[i]);

    return Math.max(...AREA);
}

const arr = [6, 2, 5, 4, 5, 1, 6];

console.log(max_area_histogram(arr));

Output

[-1, -1, 4, -1, 2]

Slightly better approach with less number of lines

Python
class Stack:
    def __init__(self):
        self.stack = []

    def isEmpty(self):
        return len(self.stack) == 0

    def push(self, num):
        self.stack.append(num)

    def pop(self):
        if self.isEmpty():
            raise Exception('Stack Underflow')
        return self.stack.pop()

    def peek(self):
        if self.isEmpty():
            return None
        return self.stack[-1]

def max_area_histogram(arr):
    stack = Stack()
    stack.push(-1)
    max_area = 0

    for i in range(len(arr)):
        while stack.peek() != -1 and arr[stack.peek()] >= arr[i]:
            last_element_index = stack.pop()
            max_area = max(max_area, arr[last_element_index] * (i - stack.peek() - 1))
        stack.push(i)

    while stack.peek() != -1:
        last_element_index = stack.pop()
        max_area = max(max_area, arr[last_element_index] * (len(arr) - stack.peek() - 1))

    return max_area

arr = [6, 2, 5, 4, 5, 1, 6]

print(max_area_histogram(arr))
JavaScript
class Stack {
    constructor() {
        this.stack = [];
    }
    
    isEmpty() {
        return this.stack.length === 0;
    }
    
    push(num) {
        this.stack.push(num);
    }
    
    pop() {
        if (this.isEmpty())
            throw 'Stack underflow';
        return this.stack.pop();
    }
    
    peek() {
        if (this.isEmpty())
            return null;
        return this.stack[this.stack.length - 1];
    }
}

function maxAreaHistogram(arr) {
    const stack = new Stack();
    stack.push(-1);
    maxArea = 0;

    for (let i = 0; i < arr.length; i++) {
        while (stack.peek() !== -1 && arr[stack.peek()] >= arr[i]) {
            lastElementIndex = stack.pop();
            maxArea = Math.max(maxArea, arr[lastElementIndex] * (i - stack.peek() - 1));
        }
        stack.push(i);
    }

    while (stack.peek() != -1) {
        lastElementIndex = stack.pop();
        maxArea = Math.max(maxArea, arr[lastElementIndex] * (arr.length - stack.peek() - 1));
    }

    return maxArea;
}

const arr = [6, 2, 5, 4, 5, 1, 6];

console.log(maxAreaHistogram(arr));