Mastering Rainwater Trapping in Data Structures and Algorithms (DSA) on LeetCode

Trapping Rain Water Problem Explained

What’s the Core Idea or Problem This Concept Is Solving?

You're given an array of non-negative integers where each element represents the height of a building (or a wall). After it rains, water gets trapped between the taller buildings.

Your job is to calculate how much water is trapped in total between the buildings.

Real-Life Analogy

Imagine a street full of uneven walls placed side by side. When it rains, water collects in the valleys formed between these walls. If one wall is shorter than its neighbors, it will trap water, like a bowl catching rain.

Example:

yamlCopy codeHeights:   [0,1,0,2,1,0,1,3,2,1,2,1]
Visual:                     |       | |     |   |
                            |   |   | | |   | | |
                            | | | | | | | | | | |
Water level:                     ~ ~   ~~~ ~ ~

Water accumulates in these "valleys," and we want to calculate the total amount.

How the Concept Works in Simple English

To find the trapped water:

1. Place one pointer at the left of the array, and another at the right.

2. Keep track of the tallest wall seen so far from both the left and right.

3. Always move the pointer that's on the shorter side inward. This is because the water trapped is determined by the shorter side.

4. If the current wall is lower than the tallest seen so far, it means water can be trapped at that point.

5. Add the trapped water at every step.

6. Repeat the process until the two pointers meet.

This is called the Two-Pointer Approach and is efficient.

Optional Visual/Story-Based Analogy

Imagine you're looking at a row of cups of different heights placed in a line. Pour water from above. Water stays in the shorter cups only if they're surrounded by taller ones. Your goal is to move from both ends and figure out how much water each cup can hold without overflowing.

Python Code (Two Pointer Optimized Approach)

pythonCopy codeclass Solution:
    def trap(self, height):
        if not height:
            return 0

        left, right = 0, len(height) - 1
        left_max, right_max = 0, 0
        total_water = 0

        while left < right:
            if height[left] < height[right]:
                if height[left] >= left_max:
                    left_max = height[left]
                else:
                    total_water += left_max - height[left]
                left += 1
            else:
                if height[right] >= right_max:
                    right_max = height[right]
                else:
                    total_water += right_max - height[right]
                right -= 1

        return total_water

Line-by-Line Beginner-Friendly Explanation

• left, right = 0, len(height) - 1: Start pointers at both ends of the list.

• left_max, right_max = 0, 0: Track the maximum height encountered from both sides.

• total_water = 0: Stores the total trapped water.

While the left pointer is before the right:

• If the height on the left is less than the right, handle the left side:

  • If the current height is greater than left_max, update left_max.

  • Else, water = left_max - current height

• If the height on the right is less, handle the right side similarly.

Move the pointers inward after each step.

Dry Run Example

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

sqlCopy codeInitial: left = 0 (4), right = 5 (5)
left_max = 0, right_max = 0, total = 0

1. left(4) < right(5)? Yes → Update left_max = 4
   → Move left → left = 1

2. height[1] = 2 → 2 < left_max (4)
   → Water = 4 - 2 = 2 → total = 2
   → Move left → left = 2

3. height[2] = 0 → 0 < left_max (4)
   → Water = 4 - 0 = 4 → total = 6
   → Move left → left = 3

4. height[3] = 3 → 3 < left_max (4)
   → Water = 4 - 3 = 1 → total = 7
   → Move left → left = 4

5. height[4] = 2 → 2 < left_max (4)
   → Water = 4 - 2 = 2 → total = 9
   → Move left → left = 5

Now left == right → Stop

Final Output: 9 units of trapped water

Time and Space Complexity

• Time Complexity: O(n)
  We process each element once.

• Space Complexity: O(1)
  Only a few variables are used; no extra arrays are needed.