Largest Rectangle in Histogram Using Stack in DSA Python - Build from Scratch

Largest Rectangle in Histogram Using Stack

📖 Scenario: Imagine you have a row of buildings of different heights. You want to find the largest rectangular area that can fit inside the skyline formed by these buildings.

🎯 Goal: Build a program that finds the largest rectangle area in a histogram using a stack to keep track of building heights.

📋 What You'll Learn

Create a list called heights with exact building heights

Create an empty list called stack to store indices

Use a for loop with variable i to iterate over range(len(heights) + 1)

Print the largest rectangle area as an integer

💡 Why This Matters

🌍 Real World

Finding the largest rectangle in a histogram helps in image processing, stock market analysis, and land area calculations.

💼 Career

This algorithm is often asked in coding interviews and is useful for roles involving algorithm design and optimization.

1

Create the histogram heights list

Create a list called heights with these exact values: 2, 1, 5, 6, 2, 3

DSA Python

# Create the list heights with values 2, 1, 5, 6, 2, 3
# Your code here

Hint

Use square brackets and separate numbers with commas.

2

Initialize the stack and max_area variable

Create an empty list called stack and a variable called max_area set to 0

DSA Python

heights = [2, 1, 5, 6, 2, 3]
# Create an empty list stack and set max_area to 0
# Your code here

Hint

Use [] for an empty list and assign 0 to max_area.

3

Use a for loop to find the largest rectangle

Use a for loop with variable i to iterate over range(len(heights) + 1). Inside the loop, use a while loop to pop from stack while stack is not empty and either i == len(heights) or heights[i] <= heights[stack[-1]]. Calculate the area for each popped index and update max_area if the area is larger. Append i to stack if the while loop ends.

DSA Python

heights = [2, 1, 5, 6, 2, 3]
stack = []
max_area = 0
# Use a for loop with i in range(len(heights) + 1) and implement the stack logic
# Your code here

Hint

Use a for loop with range(len(heights) + 1) and a while loop inside to pop from stack and calculate areas.

4

Print the largest rectangle area

Print the value of max_area to display the largest rectangle area

DSA Python

heights = [2, 1, 5, 6, 2, 3]
stack = []
max_area = 0
for i in range(len(heights) + 1):
    while stack and (i == len(heights) or heights[i]  max_area:
            max_area = area
    stack.append(i)
# Print the max_area
# Your code here

Hint

Use print(max_area) to show the result.