LeetCode 42: Trapping Rain Water Solution in Python Explained

Problem Statement

LeetCode 42, Trapping Rain Water, is a hard-level problem where you’re given an array of non-negative integers height representing an elevation map, where each bar has a width of 1. Your task is to compute how much water can be trapped between the bars after raining. The water trapped at each position depends on the minimum of the maximum heights on its left and right, minus its own height.

Constraints

0 <= height.length <= 2 * 10^4: Array length is between 0 and 20,000.
0 <= height[i] <= 10^5: Each height is between 0 and 100,000.

Example

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: Water trapped = [0,0,1,0,1,2,1,0,0,1,0,0], total = 6.

Input: height = [4,2,0,3,2,5]
Output: 9
Explanation: Water trapped = [0,2,4,1,2,0], total = 9.

Input: height = [1,2]
Output: 0
Explanation: No water can be trapped with fewer than 3 bars.

Understanding the Problem

How do you solve LeetCode 42: Trapping Rain Water in Python? For height = [0,1,0,2,1,0,1,3,2,1,2,1], water is trapped in "valleys" between bars, totaling 6 units. Each position traps water based on the minimum of the tallest bars on its left and right, minus its height. We’ll explore two approaches: a Two Pointers Solution (optimal and primary) and an Alternative with Stack (intuitive but slightly less efficient). The two-pointer method uses O(1) space and O(n) time by tracking max heights from both ends.

Solution 1: Two Pointers Approach (Primary)

Explanation

Use two pointers, left and right, starting from the ends of the array. Maintain the maximum height seen from the left (left_max) and right (right_max). Water at each position is the minimum of these maxes minus the height there. Move the pointer with the smaller max, as water is limited by the shorter side.

Here’s a flow for [4,2,0,3,2,5]:

left = 0, right = 5, left_max = 4, right_max = 5
Move left: water at 1 = min(4,5) - 2 = 2
Move left: water at 2 = min(4,5) - 0 = 4
...
Total = 9

Initialize Pointers and Maxes.

left = 0, right = n-1, left_max = right_max = 0.

Process with Two Pointers.

Update maxes, calculate water, move smaller side.

Sum Water.

Add water trapped at each step.

Return Total.

Step-by-Step Example

Example 1: height = [0,1,0,2,1,0,1,3,2,1,2,1]

We need 6.

Goal: Compute trapped water.
Result for Reference: 6.
Start: height = [0,1,0,2,1,0,1,3,2,1,2,1], left = 0, right = 11, water = 0.
Step 1: left_max = 0, right_max = 1, left_max < right_max.

left = 0, water += 0, left_max = 0, left = 1.

Step 2: left_max = 1, right_max = 1, equal, move left.

left = 1, water += 0, left_max = 1, left = 2.

Step 3: left_max = 1, right_max = 1.

left = 2, water += (1-0) = 1, left = 3.

Step 4: left_max = 2, right_max = 1, move right.

right = 10, water += (1-2) = 0, right_max = 2, right = 9.

Step 5: left_max = 2, right_max = 2.

right = 9, water += (2-1) = 1, right = 8.

Step 6: Continue, e.g., left = 5, water += (2-0) = 2.
Finish: Total water = 6.

Example 2: height = [4,2,0,3,2,5]

We need 9.

Start: left = 0, right = 5, water = 0.
Step 1: left_max = 4, right_max = 5, move left.

left = 1, water += (4-2) = 2, left_max = 4.

Step 2: left = 2, water += (4-0) = 4, left = 3.
Step 3: left = 3, water += (4-3) = 1, left = 4.
Step 4: left = 4, water += (4-2) = 2, left = 5.
Finish: water = 9.

How the Code Works (Two Pointers)

Here’s the Python code with line-by-line explanation:

def trap(height: list[int]) -> int:
    # Line 1: Handle edge cases
    if len(height) < 3:
        return 0

    # Line 2: Initialize pointers and maxes
    left, right = 0, len(height) - 1
    left_max = right_max = water = 0

    # Line 3: Process with two pointers
    while left < right:
        # Line 4: Update max heights
        left_max = max(left_max, height[left])
        right_max = max(right_max, height[right])

        # Line 5: Move pointer with smaller max
        if left_max < right_max:
            # Line 6: Add water at left
            water += left_max - height[left]
            left += 1
        else:
            # Line 7: Add water at right
            water += right_max - height[right]
            right -= 1

    # Line 8: Return total water
    return water

Alternative: Stack Approach

Explanation

Use a stack to track decreasing heights. When a taller bar is found, pop the stack, calculate water trapped between the popped bar and the current bar, bounded by the next stack top.

Initialize Stack.
Process Heights.

Push if decreasing, pop and calculate if increasing.

3. Sum Water. 4. Return Total.

Step-by-Step Example (Alternative)

For [4,2,0,3,2,5]:

Start: stack = [], water = 0.
Step 1: 4, stack = [4].
Step 2: 2, stack = [4,2].
Step 3: 0, stack = [4,2,0].
Step 4: 3, pop 0, water = (min(2,3) - 0) * 1 = 2, pop 2, water += (min(4,3) - 2) * 1 = 1, stack = [4,3].
Step 5: 2, stack = [4,3,2].
Step 6: 5, pop 2, water += (min(3,5) - 2) * 1 = 1, pop 3, water += (min(4,5) - 3) * 1 = 1, stack = [4,5].
Finish: Total water = 9.

How the Code Works (Stack)

def trapStack(height: list[int]) -> int:
    # Line 1: Initialize stack and water
    stack = []
    water = 0

    # Line 2: Process each height
    for i in range(len(height)):
        # Line 3: Pop and calculate water for increasing heights
        while stack and height[i] > height[stack[-1]]:
            bottom = stack.pop()
            if not stack:
                break
            # Line 4: Calculate trapped water
            left = stack[-1]
            h = min(height[left], height[i]) - height[bottom]
            w = i - left - 1
            water += h * w
        # Line 5: Push current index
        stack.append(i)

    # Line 6: Return total water
    return water

Complexity

Two Pointers:

Time: O(n) – Single pass with two pointers.
Space: O(1) – Only variables.

Stack:

Time: O(n) – Each element pushed/popped once.
Space: O(n) – Stack size up to n.

Efficiency Notes

Two Pointers is O(n) time and O(1) space, optimal for LeetCode 42. Stack is also O(n) time but uses O(n) space, making it less space-efficient but still effective.

Key Insights

Tips to master LeetCode 42:

Water Limits: Min of left/right maxes sets the level.
Two Pointers: Move from shorter side for efficiency.
Valley Thinking: Focus on trapped areas.

Additional Example

For height = [2,0,2]:

Goal: 2.
Two Pointers: water at 1 = min(2,2) - 0 = 2.
Result: 2.

Edge Cases

Empty or Short: [] or [1,2] – Return 0.
Flat: [1,1,1] – Return 0.
Single Peak: [0,5,0] – Return 5.

Final Thoughts

The Two Pointers solution is a standout for LeetCode 42 in Python—clever, efficient, and space-saving. For a related challenge, try LeetCode 41: First Missing Positive to tackle another hard problem! Ready to trap some water? Solve LeetCode 42 on LeetCode now and test it with arrays like [4,2,3] or [0,1,0,2] to perfect your skills. Dive in and make it rain!