Largest Rectangle in Histogram Using Stack in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Largest Rectangle Calculation

What is the output of the following code that calculates the largest rectangle area in a histogram using a stack?

DSA Python

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]))

A 10

B 12

C 9

D 8

💡 Hint

Think about the largest rectangle that can be formed by combining bars.

The largest rectangle area is 10, formed by bars with heights 5 and 6 (width 2).

🧠 Conceptual

intermediate

Understanding Stack Usage in Histogram Problem

Why do we add a zero height bar at the end of the histogram array when using a stack to find the largest rectangle?

A To avoid index errors during iteration

B To increase the maximum area by adding an extra bar

C To ensure all bars are popped from the stack by the end of the iteration

D To mark the start of the histogram

💡 Hint

Think about what happens to bars still in the stack after the main loop.

Adding a zero height bar forces the stack to empty by popping all remaining bars, ensuring all possible rectangles are considered.

🔧 Debug

advanced

Identify the Error in Stack Implementation

What error will occur when running this code snippet for largest rectangle in histogram?

DSA Python

def largest_rectangle_area(heights):
    stack = []
    max_area = 0
    for i, h in enumerate(heights):
        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]))

A No error, outputs 10

B IndexError due to empty stack access

C SyntaxError due to missing colon

D Incorrect maximum area calculation

💡 Hint

Check how width is calculated when stack is not empty.

The width calculation is off by one; it should subtract one more to get the correct width.

❓ Predict Output

advanced

Output of Largest Rectangle for Uniform Heights

What is the output of the largest rectangle area for a histogram with uniform heights?

DSA Python

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([4,4,4,4,4]))

A 20

B 16

C 4

D 0

💡 Hint

All bars have the same height, so the largest rectangle covers all bars.

The largest rectangle covers all 5 bars with height 4, area = 5 * 4 = 20.

🚀 Application

expert

Applying Largest Rectangle in Histogram to Maximal Rectangle in Binary Matrix

Given a binary matrix, we use the largest rectangle in histogram algorithm on each row's histogram of consecutive ones. What is the maximum rectangle area in the matrix below? Matrix: [[1,0,1,0,0], [1,0,1,1,1], [1,1,1,1,1], [1,0,0,1,0]]

A 8

B 6

C 9

D 10

💡 Hint

Convert each row to a histogram of heights of consecutive ones and apply largest rectangle algorithm.

The maximal rectangle area of 6 is found in the third row histogram covering columns 2 to 4 with height 2.