Trapping Rain Water Explained – From Brute Force to Two Pointer Approach (LeetCode)

Trapping Rain Water – My Learning Journey (From Intuition to Two Pointers)

Today I worked on the Trapping Rain Water problem, and honestly, it was not easy at first. I couldn’t directly come up with the solution, so I decided to step back and focus on understanding the intuition instead of forcing the code.

To build that intuition, I watched this video, which helped me understand how water is actually trapped between bars:

Reference Video:
https://www.youtube.com/watch?v=TCaBnVIllrQ

---

Key Intuition

The most important realization for this problem is:

Water trapped at any index depends on the maximum height on its left and the maximum height on its right.

Mathematically:

water[i] = min(max_left, max_right) - height[i]

If this value is negative, no water can be trapped at that position.

---

Approach 1: Brute Force (Time Limit Exceeded)

My first approach was very straightforward. For each index, I calculated:

• Maximum height on the left
• Maximum height on the right

However, I used slicing inside a loop, which created subarrays repeatedly and caused a Time Limit Exceeded (TLE) error.

class Solution:
    def trap(self, height):
        rm = []
        lm = []
        for i in range(len(height)):
            rm.append(max(height[:i+1]))
            lm.append(max(height[i:]))

        result = 0
        for i in range(len(height)):
            result += min(rm[i], lm[i]) - height[i]

        return result

This helped me understand the logic, but it was inefficient.

---

Approach 2: Prefix Maximum Arrays (Optimized)

To fix the performance issue, I optimized the solution by precomputing:

• left_max array
• right_max array

This reduced the time complexity to O(n) while using extra space.

class Solution:
    def trap(self, height):
        n = len(height)
        lm = [0] * n
        rm = [0] * n

        lm[0] = height[0]
        for i in range(1, n):
            lm[i] = max(lm[i-1], height[i])

        rm[n-1] = height[n-1]
        for i in range(n-2, -1, -1):
            rm[i] = max(rm[i+1], height[i])

        result = 0
        for i in range(n):
            result += min(lm[i], rm[i]) - height[i]

        return result

At this point, the logic was clear, but I still wanted to understand how this could be solved using two pointers.

---

Approach 3: Two Pointer Technique (Optimal)

The key insight for the two-pointer approach is:

Water is always limited by the smaller boundary.

Instead of storing arrays, I maintained:

• left_max while moving from the left
• right_max while moving from the right

At each step, I moved the pointer with the smaller maximum height, because that side determines how much water can be trapped.

class Solution:
    def trap(self, height):
        l, r = 0, len(height) - 1
        l_max = r_max = 0
        result = 0

        while l < r:
            l_max = max(l_max, height[l])
            r_max = max(r_max, height[r])

            if l_max < r_max:
                result += l_max - height[l]
                l += 1
            else:
                result += r_max - height[r]
                r -= 1

        return result

This solution runs in O(n) time and uses O(1) extra space. More importantly, I finally understood why it works, instead of just memorizing it.

---

Final Thoughts

Initially, I couldn’t build the solution on my own, but instead of giving up, I focused on understanding the intuition and building the solution step by step.

This problem taught me an important lesson:

Understanding the pattern matters more than rushing to the final code.

Now, the two-pointer approach feels natural, and I feel more confident approaching similar problems in the future.