Implement a function to find the largest rectangular area in a histogram | Python

Problem:

Implement a function to find the largest rectangular area in a histogram using a Stack.

Solution:

We can solve this problem using the stack data structure. We will traverse the given histogram and for each bar, we will find the left and right boundaries of the maximum rectangle with that bar as the height. We will store the indices of bars in the stack such that the bars on the left of the top of the stack have a smaller height than the current bar. For each bar, we will keep popping the stack until we find a bar with a smaller height than the current bar. We will use the popped bar as the right boundary for the current bar and the previous bar on the stack as the left boundary.

def get_max_area(histogram):
    stack = []
    n = len(histogram)
    left_boundary = [0] * n
    right_boundary = [0] * n

    # find left boundaries
    for i in range(n):
        while stack and histogram[stack[-1]] >= histogram[i]:
            stack.pop()
        if stack:
            left_boundary[i] = stack[-1]
        else:
            left_boundary[i] = -1
        stack.append(i)

    # clear stack for reuse
    stack.clear()

    # find right boundaries
    for i in range(n - 1, -1, -1):
        while stack and histogram[stack[-1]] >= histogram[i]:
            stack.pop()
        if stack:
            right_boundary[i] = stack[-1]
        else:
            right_boundary[i] = n 
        stack.append(i)

    # find maximum area
    max_area = 0
    for i in range(n):
        area = histogram[i] * (right_boundary[i] - left_boundary[i] -1)
        max_area = max(max_area, area)
    return max_area

histogram = [6,2,5,4,5,1,6]
get_max_area(histogram)

Output: 12

Complexity:

Time: O(n)
Space: O(n)