Largest Rectangle in Histogram Using Stack in DSA Python

Mental Model

We use a stack to keep track of bars that are not yet processed for largest rectangle. When a smaller bar comes, we calculate areas for taller bars before it.

Analogy: Imagine stacking books by height. When a shorter book arrives, you remove taller books from the top to find the biggest flat surface you can make with the books below.

Histogram bars: heights = [2, 1, 5, 6, 2, 3]
Index:        0  1  2  3  4  5
Stack stores indices of bars in increasing height order.
Example stack: bottom [0, 2, 3] top
Each step we compare current bar height with top of stack height.

Dry Run Walkthrough

Input: histogram heights = [2, 1, 5, 6, 2, 3]

Goal: Find the largest rectangle area that can be formed in the histogram

Step 1: Push index 0 (height 2) onto stack

Stack: [0]
Heights: 2 -> 1 -> 5 -> 6 -> 2 -> 3

Why: Start with first bar, stack is empty so push it

Step 2: Current bar height 1 is less than height at stack top (2), pop index 0 and calculate area

Popped index 0 (height 2), stack empty now
Calculate area = height 2 * width 1 = 2
Push index 1 (height 1)

Why: Smaller bar means we finalize rectangles for taller bars before it

Step 3: Push index 2 (height 5) since 5 > 1 (top of stack height)

Stack: [1, 2]
Heights: 2 -> 1 -> 5 -> 6 -> 2 -> 3

Why: Increasing height, so push index

Step 4: Push index 3 (height 6) since 6 > 5 (top of stack height)

Stack: [1, 2, 3]
Heights: 2 -> 1 -> 5 -> 6 -> 2 -> 3

Why: Increasing height, so push index

Step 5: Current bar height 2 is less than height at stack top (6), pop index 3 and calculate area

Popped index 3 (height 6), stack now [1, 2]
Area = 6 * (4 - 2 - 1) = 6 * 1 = 6
Current bar 2 still less than top stack height 5, pop index 2

Why: Smaller bar means finalize rectangles for taller bars

Step 6: Calculate area for popped index 2 (height 5): width = 4 - 1 - 1 = 2, area = 5 * 2 = 10 Push index 4 (height 2)

Stack: [1, 4]
Heights: 2 -> 1 -> 5 -> 6 -> 2 -> 3

Why: After popping taller bars, push current smaller bar

Step 7: Push index 5 (height 3) since 3 > 2 (top of stack height)

Stack: [1, 4, 5]
Heights: 2 -> 1 -> 5 -> 6 -> 2 -> 3

Why: Increasing height, so push index

Step 8: Reached end, pop remaining bars and calculate areas: Pop index 5 (height 3): width = 6 - 4 - 1 = 1, area = 3 * 1 = 3 Pop index 4 (height 2): width = 6 - 1 - 1 = 4, area = 2 * 4 = 8 Pop index 1 (height 1): width = 6, area = 1 * 6 = 6

Stack empty
Max area found = 10

Why: Calculate areas for all remaining bars to find max rectangle

Result:

Largest rectangle area = 10

Annotated Code

DSA Python

class Solution:
    def largestRectangleArea(self, heights: list[int]) -> int:
        stack = []  # stores indices of bars
        max_area = 0
        for i, h in enumerate(heights):
            # Pop bars taller than current
            while stack and heights[stack[-1]] > h:
                height = heights[stack.pop()]
                # Width depends on current index and stack top
                width = i if not stack else i - stack[-1] - 1
                max_area = max(max_area, height * width)
            stack.append(i)
        # Clear remaining bars
        n = len(heights)
        while stack:
            height = heights[stack.pop()]
            width = n if not stack else n - stack[-1] - 1
            max_area = max(max_area, height * width)
        return max_area

# Driver code
heights = [2, 1, 5, 6, 2, 3]
sol = Solution()
print(sol.largestRectangleArea(heights))

while stack and heights[stack[-1]] > h:

Pop indices of bars taller than current bar to calculate area

height = heights[stack.pop()]

Get height of popped bar for area calculation

width = i if not stack else i - stack[-1] - 1

Calculate width of rectangle using current index and new stack top

max_area = max(max_area, height * width)

Update max area if current rectangle is larger

stack.append(i)

Push current bar index onto stack

while stack:

Process remaining bars in stack after full iteration

height = heights[stack.pop()]

Pop bar height for final area calculation

width = n if not stack else n - stack[-1] - 1

Calculate width for remaining bars using total length

max_area = max(max_area, height * width)

Update max area if larger rectangle found

Output

10

Complexity Analysis

Time: O(n) because each bar is pushed and popped at most once

Space: O(n) for the stack storing indices of bars

vs Alternative: Naive approach checks all pairs for rectangles with O(n^2) time, stack method is much faster

Edge Cases

Empty histogram

Returns 0 as no bars exist

DSA Python

for i, h in enumerate(heights):

All bars same height

Calculates area as height * number of bars

DSA Python

while stack and heights[stack[-1]] > h:

Strictly increasing heights

Bars are pushed without popping until end

DSA Python

stack.append(i)

Strictly decreasing heights

Bars popped immediately to calculate areas

DSA Python

while stack and heights[stack[-1]] > h:

When to Use This Pattern

When asked to find largest rectangle area in a histogram, use a stack to track bars and calculate areas efficiently by popping taller bars when a smaller bar appears.

Common Mistakes

Mistake: Not calculating width correctly when popping bars
Fix: Use current index and stack top index to compute width as i - stack[-1] - 1 or i if stack empty

Mistake: Forgetting to process remaining bars in stack after iteration
Fix: Add a final loop to pop all remaining bars and calculate areas

Summary

Finds the largest rectangle area in a histogram using a stack to track bars.

Use when you need to efficiently find max rectangle area in bar charts or histograms.

The key is to pop taller bars when a smaller bar arrives to calculate max areas step-by-step.