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.