Largest Rectangle in Histogram Using Stack in DSA Python - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the stack as an empty list.

DSA Python

stack = [1]

Drag options to blanks, or click blank then click option'

A[]

B{}

CNone

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using curly braces {} which creates a set or dictionary.

Using None which is not a list.

Using 0 which is an integer, not a list.

The stack is used to store indices and should start empty, so an empty list [] is correct.

2fill in blank

medium

Complete the code to append the current index i to the stack.

DSA Python

stack.[1](i)

Drag options to blanks, or click blank then click option'

Ainsert

Bremove

Cpop

Dappend

Attempts:

3 left

💡 Hint

Common Mistakes

Using pop which removes an element instead of adding.

Using insert which requires an index and is not typical for stack push.

Using remove which deletes a specific value.

To add an element to the end of a list (stack), use the append method.

3fill in blank

hard

Fix the error in the condition to check if the stack is not empty.

DSA Python

while stack and heights[i] < heights[[1]]:

Drag options to blanks, or click blank then click option'

Ai

Bstack[-1]

Cstack[0]

D-i

Attempts:

3 left

💡 Hint

Common Mistakes

Using stack[0] which is the bottom of the stack.

Using i which is the current index, not the top of the stack.

Using -i which is invalid indexing.

To get the last element in the stack, use stack[-1]. This checks the height at the top index.

4fill in blank

hard

Fill both blanks to calculate the width correctly when popping from the stack.

DSA Python

width = i - [1] - [2]

Drag options to blanks, or click blank then click option'

Astack.pop()

Bstack[-1]

C1

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using stack.pop() inside width calculation which removes an element again.

Using 0 instead of 1 which gives wrong width.

Using stack[0] which is bottom of stack, not top.

The width is calculated as the difference between current index i and the index at the new top of the stack stack[-1], minus 1.

5fill in blank

hard

Fill both blanks to update max_area correctly inside the loop.

DSA Python

max_area = max(max_area, heights[[1]] * [2])

Drag options to blanks, or click blank then click option'

Astack.pop()

Bwidth

Cstack[-1]

Di

Attempts:

3 left

💡 Hint

Common Mistakes

Using stack[-1] instead of popping for height.

Using i instead of width for multiplication.

Not updating max_area with max function.

We pop the top index to get the height, multiply by the width calculated, and update max_area with the maximum value.

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