Find Trapping Rain Water in Java

Title: Find Trapping Rain Water in Java

The Trapping Rain Water problem is a classic array puzzle that shows up often in coding interviews because it rewards candidates who notice the two-pointer trick instead of reaching for nested loops. Given an array of non-negative integers representing the height of bars standing side by side, the goal is to compute how much water gets trapped between them after rain falls.

In this guide, you will learn how to model the problem correctly, walk through an efficient O(n) Java solution using two pointers, trace the algorithm on a concrete example, and look at the mistakes, edge cases, and interview follow-up questions that come up around this problem.

Understanding the Problem

Each element of the input array height represents the height of a bar at that index, and all the bars have the same width of 1 unit. Water poured over the bars settles into the dips between them, and the amount trapped above any single bar is bounded by the shorter of the tallest bar to its left and the tallest bar to its right.

Formally, for every index i, the water trapped above height[i] equals Math.min(leftMax, rightMax) - height[i], where leftMax is the maximum height to the left of i (inclusive) and rightMax is the maximum height to the right of i (inclusive). Summing this value across every index gives the total trapped water.

Approach

1. Handle the trivial case first: if height is null or has fewer than 3 elements, no water can be trapped, so return 0 immediately.
2. Set up two pointers, left starting at index 0 and right starting at the last index, along with two trackers leftMax and rightMax both initialized to 0.
3. Loop while left is less than right, comparing height[left] and height[right] on each iteration.
4. If height[left] is less than or equal to height[right], the left side is the bottleneck: update leftMax to the larger of leftMax and height[left], add leftMax - height[left] to the running water total, then move left forward.
5. Otherwise the right side is the bottleneck: update rightMax to the larger of rightMax and height[right], add rightMax - height[right] to the running total, then move right backward.
6. Continue until left and right meet, at which point every bar in the array has contributed to the total exactly once.
7. Return the accumulated water value as the answer.

Java Program

public class TrappingRainWater {

    public static int trap(int[] height) {
        if (height == null || height.length < 3) {
            return 0;
        }

        int left = 0;
        int right = height.length - 1;
        int leftMax = 0;
        int rightMax = 0;
        int water = 0;

        while (left < right) {
            if (height[left] <= height[right]) {
                leftMax = Math.max(leftMax, height[left]);
                water += leftMax - height[left];
                left++;
            } else {
                rightMax = Math.max(rightMax, height[right]);
                water += rightMax - height[right];
                right--;
            }
        }

        return water;
    }

    public static void main(String[] args) {
        int[] heights = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        System.out.println("Trapped water: " + trap(heights));
    }
}

Explanation of the Program

• trap(int[] height) is the only method needed; it returns the total trapped water for the given array.
• The guard clause at the top returns 0 immediately for arrays with null or fewer than 3 elements, since you need at least a left wall, a dip, and a right wall to trap anything.
• left and right walk toward each other from opposite ends of the array, while leftMax and rightMax remember the tallest bar seen so far on each side.
• Whichever side currently holds the smaller bar is guaranteed to have a real boundary already recorded in the other side’s max, so it is always safe to finalize the water above that side’s current bar before moving its pointer.
• The main method demonstrates the method on the classic sample array and prints the result.

Step-by-Step Trace

Trace the algorithm on the fresh input [1, 3, 2, 4, 1, 3, 1], where the target output is 3 units of trapped water.

At the end of each iteration, water holds the exact amount trapped by every bar processed so far, because the pointer that moves is always the one whose max tracker already accounts for a taller wall on the opposite side.

Examples

Example 1: The Classic Skyline

The array [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] is the textbook test case for this problem and traps 6 units of water.

int[] heights = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
System.out.println(TrappingRainWater.trap(heights));
// Output: 6

Example 2: Two Tall Walls

The array [4, 2, 0, 3, 2, 5] has two prominent peaks that trap water in the valley between them, for a total of 9 units.

int[] heights = {4, 2, 0, 3, 2, 5};
System.out.println(TrappingRainWater.trap(heights));
// Output: 9

Example 3: Strictly Increasing Terrain

The array [1, 2, 3, 4, 5] never dips, so there is no basin for water to collect in and the method correctly returns 0.

int[] heights = {1, 2, 3, 4, 5};
System.out.println(TrappingRainWater.trap(heights));
// Output: 0

Common Mistakes to Avoid

These are the mistakes that most often turn a correct idea into a wrong answer or a slow solution on this problem.

• Comparing raw bar heights instead of running maxima – using height[left] and height[right] directly without tracking leftMax and rightMax undercounts water above bars that sit behind a taller wall already passed. Track the running maximum on each side separately from the current bar height.
• Advancing both pointers in the same iteration – moving left and right together before recomputing water skips over bars and produces a total that is too low. Move only the pointer on the shorter side, one step per iteration.
• Skipping the length guard – omitting the check for arrays with fewer than 3 elements can let the loop run on a 0 or 1 element array and mask the fact that no water can ever be trapped there. Return 0 immediately when height.length < 3.
• Falling back to the brute force scan without noticing the cost – recomputing the maximum to the left and right of every bar with nested loops works but degrades to O(n^2) and times out on large inputs. Use the two-pointer technique, or precompute leftMax[] and rightMax[] arrays, to stay at O(n).

Edge Cases to Test

Walk through these input shapes out loud before declaring the solution finished.

• Empty array
• Array with fewer than 3 elements
• All bars the same height
• Strictly increasing heights
• Strictly decreasing heights
• A single tall bar surrounded by zeros
• Maximum height located at the first or last index

Additional Considerations

The two-pointer solution shown above runs in O(n) time with O(1) extra space, since each pointer only sweeps across the array once and no auxiliary array is needed.

An alternative dynamic programming approach precomputes a leftMax[] array and a rightMax[] array in two linear passes, then combines them in a third pass with Math.min(leftMax[i], rightMax[i]) - height[i]. It is also O(n) time but trades the O(1) space of the two-pointer version for O(n) extra space, which can matter on memory-constrained systems.

The brute force approach, scanning left and right from every index to find the two maxima, runs in O(n^2) time with O(1) space. It is worth knowing as a starting point in an interview, but should not be the final answer for large inputs.

Because water accumulates as a sum of non-negative differences, overflow is only a realistic concern for extremely large arrays with near Integer.MAX_VALUE heights; using a long accumulator is a safe defensive choice if the input constraints are not tightly bounded.

Interview Follow-up Questions

These variations are the kind of follow-up an interviewer uses to probe how well you understand the underlying idea rather than just the code you memorized.

• What if you only need to know whether any water can be trapped at all? – short-circuit the loop the moment leftMax > height[left] or rightMax > height[right] is detected, without accumulating a running total.
• What if you must solve it using only two sequential passes instead of a two-pointer walk? – build the leftMax[] array left to right, then sweep right to left accumulating water directly against a single rightMax variable, still O(n) time and O(1) extra space beyond the one array.
• What if the terrain is a 2D height map instead of a single row of bars? – this becomes the harder Trapping Rain Water II problem, solved with a min-heap seeded from the boundary cells and processed inward, which changes the complexity to O(nm log(nm)).
• What if the array has billions of bars and does not fit in memory? – stream the data twice, once forward to compute prefix maxima and once backward to compute suffix maxima, combining the two streams in O(n) time with only a constant amount of state held at once.

Conclusion

The Trapping Rain Water problem is a great showcase for how tracking the right running state, in this case leftMax and rightMax, can turn an O(n^2) brute force idea into a single O(n) pass. Once the two-pointer insight clicks, the same pattern of shrinking a window from both ends shows up again and again in array problems.

Try adapting the code above to return the water trapped above each individual bar instead of just the total, or to work through the 2D version mentioned in the follow-up questions. You can learn more about array-based algorithms and interview problems like this one in the Arrays category.