Largest Rectangle in Histogram

Problem

Given an array of integers heights representing the histogram’s bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

Example 1:

Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.

Example 2:

Input: heights = [2,4]
Output: 4

Constraints:

1 <= heights.length <= 10^5
0 <= heights[i] <= 10^4

Solution

Approach: Monotonic Increasing Stack

The key insight is to use a stack to find, for each bar, the maximum width of a rectangle with that bar as the minimum height. We maintain a monotonically increasing stack of indices.

For each bar:

While the current bar is shorter than the bar at the top of the stack, we’ve found the right boundary for that taller bar
Pop the taller bar and calculate its maximum rectangle area
Push the current bar’s index

The left boundary is the previous element in the stack (or 0 if stack is empty), and the right boundary is the current index.

Implementation

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        max_area = 0
        stack = []  # Stack stores (index, height)

        for i, h in enumerate(heights):
            start = i
            # Pop all bars taller than current
            while stack and stack[-1][1] > h:
                index, height = stack.pop()
                # Width = current index - popped bar's start index
                max_area = max(max_area, height * (i - index))
                start = index  # Current bar can extend back to this index

            stack.append((start, h))

        # Process remaining bars in stack
        for index, height in stack:
            max_area = max(max_area, height * (len(heights) - index))

        return max_area

Alternative (Indices Only):

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        max_area = 0
        stack = []  # Stack stores indices

        for i in range(len(heights)):
            # Pop taller bars and calculate their areas
            while stack and heights[stack[-1]] > heights[i]:
                h_index = stack.pop()
                height = heights[h_index]
                # Width: from element after previous stack top to current
                width = i if not stack else i - stack[-1] - 1
                max_area = max(max_area, height * width)

            stack.append(i)

        # Process remaining bars
        while stack:
            h_index = stack.pop()
            height = heights[h_index]
            width = len(heights) if not stack else len(heights) - stack[-1] - 1
            max_area = max(max_area, height * width)

        return max_area

Complexity Analysis

Time Complexity: O(n), where n is the number of bars. Each bar is pushed and popped from the stack at most once.
Space Complexity: O(n) in the worst case, when heights are in increasing order and we push all indices onto the stack.

Key Insights

Monotonic Stack: We maintain a stack of indices where heights are in increasing order. When we encounter a shorter bar, it acts as the right boundary for all taller bars in the stack.
Width Calculation: For a bar at index i popped when processing index j, the width is j - i (or adjusted based on the previous stack element). The bar can extend left to where a shorter bar exists.
Start Index Extension: When we pop a taller bar, the current shorter bar can extend back to where the taller bar started. This is why we track the start index.
Remaining Bars: Bars still in the stack after processing all elements can extend to the end of the histogram. We process them with width = len(heights) - index.
Why This Works: For each bar, we find the maximum width rectangle where that bar is the minimum height. The monotonic stack efficiently finds both left and right boundaries where shorter bars exist.