Trapping Rain Water Using Stack in DSA Python - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize an empty stack for storing indices.

DSA Python

stack = [1]

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

A[]

B{}

C()

Dset()

Attempts:

3 left

💡 Hint

Common Mistakes

Using curly braces {} creates a dictionary, not a stack.

Using parentheses () creates a tuple, which is immutable.

We use a list [] as a stack to store indices of bars.

2fill in blank

medium

Complete the code to pop the top element from the stack.

DSA Python

top = stack.[1]()

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

Apop

Bremove

Cdelete

Ddiscard

Attempts:

3 left

💡 Hint

Common Mistakes

Using remove() causes errors because it expects a value, not an index.

Using delete is not a list method.

The pop() method removes and returns the last item from the list, acting as stack pop.

3fill in blank

hard

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

DSA Python

while stack and height[i] > height[[1]]:

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

Astack.pop()

Bstack[0]

Cstack

Dstack[-1]

Attempts:

3 left

💡 Hint

Common Mistakes

Using stack[0] compares with the bottom element, causing wrong logic.

Using stack.pop() removes the element, which is incorrect here.

We compare with the height at the index on top of the stack, which is stack[-1].

4fill in blank

hard

Fill both blanks to calculate the distance and bounded height for trapped water.

DSA Python

distance = i - [1] - 1
bounded_height = min(height[i], height[[2]]) - height[top]

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

Astack[-1]

Btop

Cstack[0]

Di

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong indices for distance causes incorrect water calculation.

Mixing up top and stack[-1] leads to errors.

Distance is between current index i and the new top of stack stack[-1]. Bounded height is min(height[stack[-1]], height[i]) - height[top].

5fill in blank

hard

Fill all three blanks to update the total trapped water and push current index to stack.

DSA Python

water += distance * bounded_height
stack.[1](i)
i += [2]

# Loop condition
while i < [3]:

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

Aappend

B1

Clen(height)

Dpop

Attempts:

3 left

💡 Hint

Common Mistakes

Using pop instead of append removes elements incorrectly.

Incrementing i by wrong value causes infinite loops.

Looping beyond length causes index errors.

We add trapped water, push current index with append, increment i by 1, and loop while i is less than the length of the height list.

Practice

1. What is the main purpose of using a stack in the Trapping Rain Water Using Stack algorithm?

easy

A. To store the total amount of trapped water

B. To sort the heights of bars in ascending order

C. To keep track of bars that are not yet processed for water trapping

D. To reverse the order of the height array

Solution

1. Step 1: Understand the role of the stack

   The stack stores indices of bars that are waiting to find a right boundary to trap water.

2. Step 2: Why not other options?

   The stack does not store water amount or sort bars; it helps find boundaries for trapped water.

3. Final Answer:

   To keep track of bars that are not yet processed for water trapping -> Option C

4. Quick Check:

   Stack tracks bars for trapping water = B [OK]

Hint: Stack holds bars waiting for right boundary [OK]

Common Mistakes:

• Thinking stack stores water amount
• Assuming stack sorts the bars
• Believing stack reverses the array

2. Which of the following Python code snippets correctly initializes an empty stack for the trapping rain water algorithm?

easy

A. stack = 0

B. stack = {}

C. stack = None

D. stack = []

Solution

1. Step 1: Identify correct stack initialization

   In Python, a stack is commonly represented by a list, so stack = [] initializes an empty stack.

2. Step 2: Why other options are wrong

   {} is a dictionary, None is no value, and 0 is an integer, none suitable for stack operations.

3. Final Answer:

   stack = [] -> Option D

4. Quick Check:

   Empty list for stack = A [OK]

Hint: Use empty list [] to create stack in Python [OK]

Common Mistakes:

• Using {} which creates a dictionary
• Assigning None instead of list
• Using integer 0 as stack

3. What is the output of the following code snippet that uses stack to calculate trapped rain water?

def trap(height):
    stack = []
    water = 0
    for i, h in enumerate(height):
        while stack and height[stack[-1]] < h:
            top = stack.pop()
            if not stack:
                break
            distance = i - stack[-1] - 1
            bounded_height = min(height[stack[-1]], h) - height[top]
            water += distance * bounded_height
        stack.append(i)
    return water

print(trap([0,1,0,2,1,0,1,3,2,1,2,1]))

medium

A. 6

B. 5

C. 4

D. 7

Solution

1. Step 1: Trace the algorithm with given heights

   The code calculates trapped water for heights [0,1,0,2,1,0,1,3,2,1,2,1]. The total trapped water is 6 units.

2. Step 2: Confirm calculation matches known example

   This is a classic example where trapped water is 6, matching the output of the code.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Trapped water = 6 [OK]

Hint: Classic example trap water = 6 units [OK]

Common Mistakes:

• Miscounting trapped water units
• Ignoring stack pop conditions
• Wrong distance or bounded height calculation

4. Identify the error in the following code snippet for trapping rain water using stack:

def trap(height):
    stack = []
    water = 0
    for i, h in enumerate(height):
        while stack and height[stack[-1]] <= h:
            top = stack.pop()
            if not stack:
                break
            distance = i - stack[-1] - 1
            bounded_height = min(height[stack[-1]], h) - height[top]
            water += distance * bounded_height
        stack.append(i)
    return water

print(trap([4,2,0,3,2,5]))

medium

A. The distance calculation is incorrect

B. The condition should be < instead of <=

C. The stack should be a queue

D. The water variable should be initialized to 1

Solution

1. Step 1: Check the while loop condition

   The condition height[stack[-1]] <= h causes popping even when heights are equal, which is incorrect for trapping water calculation.

2. Step 2: Correct condition and reason

   It should be height[stack[-1]] < h to pop only when current height is strictly greater, ensuring correct water trapping.

3. Final Answer:

   The condition should be < instead of <= -> Option B

4. Quick Check:

   Use < not <= in while condition [OK]

Hint: Use strict less than < in stack pop condition [OK]

Common Mistakes:

• Using <= causes wrong popping
• Confusing stack with queue
• Incorrect distance formula
• Initializing water to 1 instead of 0

5. Given the height array [3, 0, 2, 0, 4], what is the total trapped rain water calculated using the stack method? Explain how the stack helps in this calculation.

hard

A. 4

B. 7

C. 5

D. 6

Solution

1. Step 1: Calculate trapped water step-by-step

   Heights: [3,0,2,0,4]. Water trapped at position 1 is 3 units, at position 2 is 0 units, at position 3 is 1 unit. Total trapped water = 4 units.

2. Step 2: Explain stack role in calculation

   The stack stores indices of bars. When a higher bar is found, it pops lower bars and calculates trapped water using distance and bounded height between bars.

3. Final Answer:

   4 -> Option A

4. Quick Check:

   Stack helps find boundaries; trapped water = 4 [OK]

Hint: Stack finds left/right boundaries to calculate trapped water [OK]

Common Mistakes:

• Adding trapped water incorrectly
• Ignoring zero height bars
• Not using stack to find boundaries