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.

Practice

1. What is the main purpose of using a stack in the Largest Rectangle in Histogram problem?

easy

A. To reverse the order of bars for easier calculation

B. To store the heights of all bars in sorted order

C. To keep track of bars' indices with increasing heights

D. To count the total number of bars in the histogram

Solution

1. Step 1: Understand the role of the stack

   The stack is used to store indices of bars in increasing height order to efficiently find the largest rectangle.

2. Step 2: Explain why increasing order is important

   When a bar with smaller height appears, we pop from the stack to calculate areas with bars taller than the current one.

3. Final Answer:

   To keep track of bars' indices with increasing heights -> Option C

4. Quick Check:

   Stack stores indices in increasing height order [OK]

Hint: Stack stores indices of increasing height bars [OK]

Common Mistakes:

• Thinking stack stores heights instead of indices
• Assuming stack sorts bars by height
• Using stack to count bars instead of track indices

2. Which of the following Python code snippets correctly initializes an empty stack for the Largest Rectangle in Histogram algorithm?

easy

A. stack = ()

B. stack = {}

C. stack = None

D. stack = []

Solution

1. Step 1: Identify correct data structure for stack

   In Python, a list is commonly used as a stack because it supports append() and pop() operations.

2. Step 2: Check each option

   stack = [] uses a list ([]), which is correct. stack = {} uses a dictionary ({}), not suitable. stack = None assigns None, not a stack. stack = () uses a tuple (()), which is immutable.

3. Final Answer:

   stack = [] -> Option D

4. Quick Check:

   List [] is correct stack initialization [OK]

Hint: Use list [] for stack in Python [OK]

Common Mistakes:

• Using dictionary {} instead of list
• Using tuple () which is immutable
• Assigning None instead of a list

3. What is the output of the following code snippet for the histogram heights = [2, 1, 5, 6, 2, 3]?

def largest_rectangle_area(heights):
    stack = []
    max_area = 0
    for i, h in enumerate(heights + [0]):
        while stack and heights[stack[-1]] > h:
            height = heights[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)
    return max_area

print(largest_rectangle_area([2, 1, 5, 6, 2, 3]))

medium

A. 10

B. 12

C. 8

D. 6

Solution

1. Step 1: Trace the stack and area calculation

   Iterate through heights with an extra 0 at the end to pop all bars. The largest rectangle area found is 10 (from bars with heights 5 and 6).

2. Step 2: Confirm max area calculation

   The max area is calculated as max(10, others), so final answer is 10.

3. Final Answer:

   10 -> Option A

4. Quick Check:

   Largest rectangle area = 10 [OK]

Hint: Add zero height at end to pop all bars [OK]

Common Mistakes:

• Forgetting to add zero at end of heights
• Incorrect width calculation
• Not popping all bars from stack

4. Find the error in this code snippet for Largest Rectangle in Histogram:

def largest_rectangle_area(heights):
    stack = []
    max_area = 0
    for i, h in enumerate(heights + [0]):
        while stack and heights[stack[-1]] >= h:
            height = heights[stack.pop()]
            width = i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)
    return max_area

print(largest_rectangle_area([2, 1, 5, 6, 2, 3]))

medium

A. Width calculation should be i - stack[-1] - 1

B. Missing adding zero height at end of heights

C. Comparison should be > instead of >=

D. Stack should store heights, not indices

Solution

1. Step 1: Identify width calculation mistake

   Width is calculated as i - stack[-1], but it should be i - stack[-1] - 1 to exclude the popped bar's index.

2. Step 2: Confirm other parts

   Adding zero at end is optional but common; comparison >= is acceptable; stack stores indices correctly.

3. Final Answer:

   Width calculation should be i - stack[-1] - 1 -> Option A

4. Quick Check:

   Width = i - stack[-1] - 1 [OK]

Hint: Width = current index - previous stack top - 1 [OK]

Common Mistakes:

• Incorrect width calculation causing wrong area
• Forgetting to add zero at end (optional)
• Confusing stack contents (indices vs heights)

5. Given the histogram heights = [6, 2, 5, 4, 5, 1, 6], what is the largest rectangle area using the stack approach?

hard

A. 10

B. 15

C. 12

D. 8

Solution

1. Step 1: Use stack to find largest rectangle

   Traverse bars with an extra 0 at end. The largest rectangle is formed by heights 5, 4, 5 spanning width 3, area = 12, but a larger rectangle is formed by heights 6 spanning width 2, area = 12, and also by heights 6 spanning width 1, area = 6. However, the maximum area is 15 formed by heights 5, 4, 5, 1, 6 combined correctly.

2. Step 2: Confirm no larger area exists

   After careful calculation, the largest rectangle area is 15 (from bars at indices 2 to 4 with height 5).

3. Final Answer:

   15 -> Option B

4. Quick Check:

   Max area = 15 from bars 5,4,5 [OK]

Hint: Check rectangles formed by popped bars for max area [OK]

Common Mistakes:

• Ignoring width when calculating area
• Not adding zero height at end to pop all bars
• Miscomputing width boundaries