0026 - Largest Rectangle In Histogram

Largest Rectangle In Histogram

Hard

You are given an array of integers heights where heights[i] represents the height of a bar. The width of each bar is 1.

Return the area of the largest rectangle that can be formed among the bars.

Note: This chart is known as a histogram.

Example 1:

Input: heights = [7,1,7,2,2,4]

Output: 8 Example 2:

Input: heights = [1,3,7]

Output: 7

Solution¶

• https://www.youtube.com/watch?v=ZGMw8Bvpwd4

• The stack stores (height, position) tuples. When a shorter bar is found, it triggers calculation of areas for taller bars that can't extend further right. The start position helps calculate correct widths when multiple bars are popped.

• Iterate through histogram bars

• For each bar, if current height is less than stack top, pop and calculate areas of rectangles that must end at current position

• Track starting position of rectangles to handle width calculation

• After iteration, process remaining stack elements for rectangles that extend to the end

• Time Complexity: O(n) - each bar is pushed and popped at most once

• Space Complexity: O(n) - for the stack

In [11]:

def largest_rectangle(heights):
    maxArea=0
    stk=[]
    for i, height in enumerate(heights):
        start=i
        while stk and height<stk[-1][0]:
            h, j = stk.pop()
            area=(i-j)*h
            maxArea=max(maxArea,area)
            start=j
        stk.append((height,start))
    while stk:
        h,j=stk.pop()
        area=(len(heights)-j)*h
        maxArea=max(maxArea, area)
    return maxArea
        

In [12]:

largest_rectangle([7,1,7,2,2,4])

Out[12]:

8