Trapping Rain Water Problem in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of trapping rain water calculation

What is the output of the following Python code that calculates trapped rain water?

DSA Python

def trap(height):
    left, right = 0, len(height) - 1
    left_max, right_max = 0, 0
    water = 0
    while left < right:
        if height[left] < height[right]:
            if height[left] >= left_max:
                left_max = height[left]
            else:
                water += left_max - height[left]
            left += 1
        else:
            if height[right] >= right_max:
                right_max = height[right]
            else:
                water += right_max - height[right]
            right -= 1
    return water

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

A 8

B 5

C 6

D 7

💡 Hint

Think about how water is trapped between bars of different heights.

The code uses two pointers and keeps track of the maximum heights from left and right to calculate trapped water correctly. The total trapped water for the given input is 6 units.

🧠 Conceptual

intermediate

Understanding the role of left_max and right_max

In the trapping rain water problem, what do the variables left_max and right_max represent?

A The current water trapped at left and right positions

B The highest bars seen so far from the left and right sides respectively

C The total water trapped so far from left and right

D The indexes of the tallest bars in the array

💡 Hint

Think about how water trapping depends on the tallest bars on each side.

left_max and right_max track the tallest bars encountered from the left and right ends to determine how much water can be trapped at each position.

❓ Predict Output

advanced

Output of modified trapping rain water code with extra print statements

What is the output of this code snippet that prints trapped water after each step?

DSA Python

def trap(height):
    left, right = 0, len(height) - 1
    left_max, right_max = 0, 0
    water = 0
    steps = []
    while left < right:
        if height[left] < height[right]:
            if height[left] >= left_max:
                left_max = height[left]
            else:
                water += left_max - height[left]
            steps.append(water)
            left += 1
        else:
            if height[right] >= right_max:
                right_max = height[right]
            else:
                water += right_max - height[right]
            steps.append(water)
            right -= 1
    return steps

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

A [0, 2, 6, 7, 9]

B [0, 2, 5, 7, 8]

C [0, 1, 3, 6, 7]

D [0, 2, 4, 7, 7]

💡 Hint

Trace the water accumulation step by step.

The code accumulates trapped water stepwise and appends the total after each calculation. The correct sequence is [0, 2, 6, 7, 9].

🔧 Debug

advanced

Identify the error in this trapping rain water code

What error does this code produce when run?

DSA Python

def trap(height):
    left, right = 0, len(height) - 1
    left_max, right_max = 0, 0
    water = 0
    while left <= right:
        if height[left] < height[right]:
            if height[left] >= left_max:
                left_max = height[left]
            else:
                water += left_max - height[left]
            left += 1
        else:
            if height[right] >= right_max:
                right_max = height[right]
            else:
                water += right_max - height[right]
            right -= 1
    return water

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

A IndexError: list index out of range

B Runs correctly and returns 6

C TypeError: unsupported operand type(s)

D Returns incorrect trapped water value

💡 Hint

Check the loop condition carefully.

The loop condition 'left <= right' causes the pointers to cross and double count or miscalculate trapped water, resulting in an incorrect value.

🚀 Application

expert

Maximum trapped water between two bars

Given an array representing heights of bars, which pair of bars traps the maximum water between them (ignoring bars in between)?

DSA Python

def max_water_between_bars(height):
    max_water = 0
    left_index = 0
    right_index = 0
    for i in range(len(height)):
        for j in range(i+1, len(height)):
            water = min(height[i], height[j]) * (j - i - 1)
            if water > max_water:
                max_water = water
                left_index, right_index = i, j
    return (left_index, right_index, max_water)

print(max_water_between_bars([3,1,2,4,0,1,3,2]))

A (0, 6, 15)

B (3, 7, 8)

C (1, 6, 10)

D (0, 3, 6)

💡 Hint

Calculate water trapped as height times distance between bars minus one.

The maximum water trapped between bars ignoring intermediate bars is between indexes 0 and 6 with 15 units.

Practice

1. What does the Trapping Rain Water problem ask you to find given an array of heights?

easy

A. The number of bars taller than a given height

B. The highest bar in the array

C. The total amount of water that can be trapped between the bars after raining

D. The sum of all bar heights

Solution

1. Step 1: Understand the problem context

   The problem gives an array representing heights of bars and asks how much water can be trapped between them after rain.

2. Step 2: Identify the goal

   The goal is to calculate the total trapped water volume between bars, not just the tallest bar or sum of heights.

3. Final Answer:

   The total amount of water trapped between bars -> Option C

4. Quick Check:

   Trapped water = total water held between bars [OK]

Hint: Focus on trapped water volume, not bar heights [OK]

Common Mistakes:

• Confusing trapped water with tallest bar height
• Summing bar heights instead of water trapped
• Ignoring spaces between bars where water collects

2. Which of the following Python code snippets correctly initializes two pointers for the two-pointer approach in the Trapping Rain Water problem?

easy

A. left, right = 0, len(height) - 1

B. left, right = 1, len(height)

C. left, right = 0, len(height)

D. left, right = -1, len(height) - 1

Solution

1. Step 1: Understand pointer initialization

   Two pointers start at the ends: left at 0, right at last index (length - 1).

2. Step 2: Check each option

   left, right = 0, len(height) - 1 correctly sets left=0 and right=len(height)-1. Others have invalid indices.

3. Final Answer:

   left, right = 0, len(height) - 1 -> Option A

4. Quick Check:

   Start pointers at array ends [OK]

Hint: Two pointers start at first and last index [OK]

Common Mistakes:

• Setting right pointer to len(height) (out of range)
• Starting left pointer at 1 instead of 0
• Using negative indices incorrectly

3. What is the output of the following Python code for trapping rain water?

def trap(height):
    left, right = 0, len(height) - 1
    left_max = right_max = 0
    water = 0
    while left < right:
        if height[left] < height[right]:
            if height[left] >= left_max:
                left_max = height[left]
            else:
                water += left_max - height[left]
            left += 1
        else:
            if height[right] >= right_max:
                right_max = height[right]
            else:
                water += right_max - height[right]
            right -= 1
    return water

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

medium

A. 5

B. 6

C. 4

D. 7

Solution

1. Step 1: Trace pointers and water accumulation

   Using two pointers, water trapped is calculated by comparing left and right heights and updating max heights.

2. Step 2: Calculate trapped water for given input

   For input [0,1,0,2,1,0,1,3,2,1,2,1], total trapped water is 6 units.

3. Final Answer:

   6 -> Option B

4. Quick Check:

   Standard example result = 6 [OK]

Hint: Use two-pointer method to sum trapped water [OK]

Common Mistakes:

• Miscounting trapped water units
• Not updating max heights correctly
• Confusing left and right pointer moves

4. Find the error in this Python code snippet for the Trapping Rain Water problem:

def trap(height):
    left, right = 0, len(height) - 1
    left_max = right_max = 0
    water = 0
    while left <= right:
        if height[left] < height[right]:
            if height[left] > left_max:
                left_max = height[left]
            else:
                water += left_max - height[left]
            left += 1
        else:
            if height[right] > right_max:
                right_max = height[right]
            else:
                water += right_max - height[right]
            right -= 1
    return water

medium

A. The while loop condition should be 'left < right' instead of 'left <= right'

B. The comparison operators '>' should be '>=' when updating max heights

C. The water accumulation formula is incorrect

D. The pointers should be initialized to 1 and len(height) - 2

Solution

1. Step 1: Analyze the loop condition

   The loop uses 'left <= right', which causes pointers to cross and double count or error.

2. Step 2: Correct loop condition

   Changing to 'left < right' prevents overlap and ensures correct water calculation.

3. Final Answer:

   The while loop condition should be 'left < right' instead of 'left <= right' -> Option A

4. Quick Check:

   Loop ends before pointers cross [OK]

Hint: Use strict less than in loop to avoid pointer overlap [OK]

Common Mistakes:

• Using <= causes double counting
• Not updating max heights correctly
• Incorrect pointer initialization

5. Given the height array [4,2,0,3,2,5], what is the total trapped rain water? Use the two-pointer approach to solve.

hard

A. 7

B. 8

C. 6

D. 9

Solution

1. Step 1: Initialize pointers and max heights

   left=0, right=5, left_max=0, right_max=0, water=0.

2. Step 2: Move pointers and calculate trapped water

   Walk through: - left=0 (4), right=5 (5), left < right - height[left]

3. Final Answer:

   9 -> Option D

4. Quick Check:

   Sum trapped water units = 9 [OK]

Hint: Add water trapped at each step using max heights [OK]

Common Mistakes:

• Miscounting trapped water at zero height bars
• Not updating left_max and right_max correctly
• Stopping loop too early or late