Trapping Rain Water

Hey fellow developers, welcome back to our DSA learning series. We hope
you are doing great and enjoying this journey with us. This series is
all about exploring problems the way a beginner genuinely sees them. We
are students ourselves, so we know exactly how confusing a problem can
look at first glance, and how a simple explanation at the right moment
can completely change the way you understand it. Today, we are going to
look at a very popular and very interesting problem --- Trapping Rain
Water.

This is a problem that almost every interviewer loves to ask. It is
marked as "Hard" on most platforms, but in reality, once you truly
understand what the question is trying to communicate, the whole logic
feels surprisingly intuitive. So let us take our time and walk through
the thought process slowly, step by step.

Problem Statement

We are given an array of non-negative integers that represent the
heights of vertical bars placed next to each other. Each bar has a width
of 1 unit. Now imagine rainwater falling on top of these bars. Depending
on the relative heights of the bars on the left and right, some amount
of water might get trapped between them. Our task is to determine how
much water gets accumulated in total.

For example:

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

Output: 6

Looking at the structure visually, you can almost see small pits and
valleys forming, and the water naturally fills up in those gaps.

Brute Force Intuition

Let us start with the most straightforward idea --- the one that comes
to mind when you simply think about the situation as a person, not as a
coder.

Imagine you are standing at a particular bar of height h. To figure
out how much water can stay on top of this bar, you do not look only at
the bar itself; you quickly glance to your left and right. Water can
only stay if there is a taller boundary on both sides. So you check:

• What is the tallest bar on my left?
• What is the tallest bar on my right?

Then, the maximum water level above the current bar is determined by the
shorter of these two heights. Because water will spill over the smallest
boundary.

So the water trapped on index i becomes:

min(max height on left, max height on right) − current height

This idea is clean and logical. Now, to convert this into code, the
simplest approach is to run two loops for each index --- one scanning
leftward, and another scanning rightward. That gives us a clear
brute-force solution.

public int trap(int[] height) {
    int n = height.length;
    int totalWater = 0;

    for (int i = 0; i < n; i++) {
        int maxLeft = 0;
        int maxRight = 0;

        // Find max on the left
        for (int j = i; j >= 0; j--) {
            maxLeft = Math.max(maxLeft, height[j]);
        }

        // Find max on the right
        for (int j = i; j < n; j++) {
            maxRight = Math.max(maxRight, height[j]);
        }

        int waterLevel = Math.min(maxLeft, maxRight) - height[i];
        totalWater += waterLevel;
    }

    return totalWater;
}

This solution works perfectly, and it is a good starting point because it forces us to understand the meaning behind the formula. However, it takes O(n²) time since for every index we scan the array twice. The space usage is constant, but the speed becomes an issue as input size grows.

Optimized Approach Using Prefix Arrays

Now that we understand the brute-force idea, let us refine it. Notice
that in the brute force solution, we repeatedly calculate the same
values --- the left maximum and right maximum for many positions. Why
not compute them once and reuse?

This leads to the prefix-max and suffix-max approach.

We create an array left[] where left[i] stores the maximum height
from index 0 to i.

Similarly, we create a right[] array where right[i] stores the
maximum height from index i to the last index.

Once these two arrays are ready, we already have all the information needed to compute the trapped water at every index in O(1) time. The final loop just applies the same formula as before.

Here is the code:

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        if(n == 0) return 0;

        int[] left = new int[n];
        int[] right = new int[n];

        // Build prefix max array
        left[0] = height[0];
        for(int i = 1; i < n; ++i) {
            left[i] = Math.max(left[i - 1], height[i]);
        }

        // Build suffix max array
        right[n - 1] = height[n - 1];
        for(int i = n - 2; i >= 0; --i) {
            right[i] = Math.max(right[i + 1], height[i]);
        }

        int trapped = 0;
        for(int i = 0; i < n; ++i) {
            trapped += Math.min(left[i], right[i]) - height[i];
        }

        return trapped;
    }
}

The time complexity now becomes O(n) and the logic becomes cleaner. The only trade-off is that we use two extra arrays, giving us O(n) space.

Final and Most Optimized Approach: Two-Pointer Technique

Finally, once we understand how prefix and suffix maxima help us, we can
push the optimization even further. The question becomes: Do we really need two whole arrays? The surprising answer is — no. We can keep track of everything we need using just two pointers (one starting from the left end and one from the right) and two variables (leftMax and rightMax) that update as we move inward. Here is the key observation: Water trapping at any point is limited by the smaller boundary between left and right. So, if height[left] is smaller, we focus on the left side. If height[right] is smaller, we shift our attention to the right side. This allows us to calculate trapped water on the fly while moving the pointers.

Here is the final optimized code:

class Solution {
    public int trap(int[] height) {
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0;
        int trapped = 0;

        while (left < right) {

            if (height[left] < height[right]) {
                if (height[left] >= leftMax) {
                    leftMax = height[left];
                } else {
                    trapped += leftMax - height[left];
                }
                left++;
            } else {
                if (height[right] >= rightMax) {
                    rightMax = height[right];
                } else {
                    trapped += rightMax - height[right];
                }
                right--;
            }
        }
        return trapped;
    }
}

This version gives us both O(n) time and O(1) space — the optimal combination.

Conclusion

By the time you reach this point, you have seen how the thought process evolves naturally: starting from a basic observation, moving to a brute-force method, then improving it with precomputed arrays, and finally refining it into the elegant two-pointer solution. And this journey is extremely important, because in interviews, most companies are not just looking for the final optimized answer — they want to hear how you build your logic step by step.

This problem is a great example of how understanding the idea is more valuable than memorizing the code. Once the concept becomes clear, all three approaches become easy to derive on your own.