One of the most popular array problems you’ll encounter in coding interviews is Trapping Rain Water. At first glance, it looks like a geometry problem, but it’s really about identifying the tallest boundaries on both sides of every bar.

Let’s break it down step by step, starting with the simplest solution and gradually optimizing it.

---

Problem Statement

You’re given an array of non-negative integers where each value represents the height of a bar with a width of 1.

Your task is to calculate how much rainwater can be trapped after it rains.

Example

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

Output:
9

Visualizing the bars makes it easier to see that water gets trapped in the valleys between taller bars.

---

Key Observation

For every position, the amount of water it can hold depends on:

• The tallest bar to its left
• The tallest bar to its right

The water level at any index is determined by the shorter of these two boundaries.

Mathematically:

water[i] = min(maxLeft, maxRight) - height[i]

If this value is negative, we simply treat it as zero.

---

Solution 1: Brute Force

The most straightforward solution is to calculate the tallest bar on both sides for every index.

For each position:

1. Scan left to find the maximum height.
2. Scan right to find the maximum height.
3. Add the trapped water.

from typing import List

class Solution:
    def trap(self, height: List[int]) ->int:
        if not height:
            return 0

        n = len(height)
        res = 0

        for i in range(n):
            leftMax = rightMax = height[i]

            for j in range(i):
                leftMax = max(leftMax, height[j])

            for j in range(i + 1, n):
                rightMax = max(rightMax, height[j])

            res += min(leftMax, rightMax) - height[i]

        return res

Complexity

• Time: O(n²)
• Space: O(1)

Why is it slow?

For every element, we’re scanning the array twice:

• once to the left
• once to the right

This repeated work makes the algorithm quadratic.

---

Solution 2: Prefix and Suffix Maximum Arrays

Instead of repeatedly searching for the tallest bars, we can precompute them.

We’ll build two arrays:

• prefix[i] → tallest bar from the left up to i
• suffix[i] → tallest bar from the right up to i

Building the Prefix Array

Height:
0 2 0 3 1 0 1 3 2 1

Prefix:
0 2 2 3 3 3 3 3 3 3

Building the Suffix Array

Height:
0 2 0 3 1 0 1 3 2 1

Suffix:
3 3 3 3 3 3 3 3 2 1

Now each position already knows its tallest boundary on both sides.

from typing import List

class Solution:
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0

        n = len(height)
        res = 0

        prefix = [0] * n
        suffix = [0] * n

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

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

        for i in range(n):
            res += min(prefix[i], suffix[i]) - height[i]

        return res

Complexity

• Time: O(n)
• Space: O(n)

This eliminates repeated scanning, making the algorithm linear.

---

Solution 3: Two Pointers (Optimal)

Can we eliminate the extra arrays?

Yes.

Instead of storing prefix and suffix arrays, we can maintain:

• leftMax
• rightMax

while moving two pointers toward each other.

l                             r
↓                             ↓

0 2 0 3 1 0 1 3 2 1

The important insight is:

The side with the smaller maximum height determines how much water can be trapped at that moment.

Why?

Suppose:

leftMax = 3
rightMax = 7

The water level on the left can never exceed 3, regardless of what happens further on the right. So we can safely process the left pointer.

Similarly, if:

leftMax = 8
rightMax = 4

The right side becomes the limiting boundary, so we process the right pointer.

This lets us compute the answer in a single pass.

from typing import List

class Solution:
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0

        l, r = 0, len(height) - 1
        leftMax = height[l]
        rightMax = height[r]

        res = 0

        while l < r:
            if leftMax < rightMax:
                l += 1
                leftMax = max(leftMax, height[l])
                res += leftMax - height[l]
            else:
                r -= 1
                rightMax = max(rightMax, height[r])
                res += rightMax - height[r]

        return res

Complexity

• Time: O(n)
• Space: O(1)

This is the optimal solution.

---

Dry Run

Consider:

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

Initially:

l = 0
r = 9

leftMax = 0
rightMax = 1

Since leftMax < rightMax, we move the left pointer.

Eventually:

leftMax = 2

When we encounter:

height = 0

Water trapped becomes:

2 - 0 = 2

Later:

leftMax = 3

When another valley appears:

height = 1

water = 3 - 1 = 2

Repeating this process across the array gives a total trapped water of:

9

---

Comparison

Approach	Time	Space
Brute Force	O(n²)	O(1)
Prefix & Suffix Arrays	O(n)	O(n)
Two Pointers	O(n)	O(1)

---

Final Thoughts

The Trapping Rain Water problem is an excellent example of how understanding the properties of a problem can lead to significant optimizations.

We started with a brute-force solution that repeatedly searched for boundaries, improved it by precomputing prefix and suffix maximums, and finally arrived at the elegant two-pointer approach that achieves linear time with constant extra space.

The biggest takeaway is recognizing that the smaller of the two maximum boundaries determines the water level. Once you internalize this insight, the optimal solution becomes much more intuitive.

This pattern of progressively refining a solution—from brute force to precomputation to two pointers—is common in coding interviews, making this problem a valuable one to master.