Trapping Rain Water: Two-Pointer Left-Max and Right-Max

• Trapping Rain Water – given an array of bar heights, compute how much water is trapped in dips between bars after rain.
• Water formula – the water above any single bar equals the smaller of the tallest bar to its left and the tallest bar to its right, minus the bar's own height, never less than zero.
• Two-pointer approach – a left pointer and a right pointer walk inward from both ends, each tracking the running maximum height on its side.
• Process the shorter side – at each step, whichever side has the smaller boundary wall is the side whose trapped water can be safely committed.
• Complexity – runs in O(n) time with O(1) extra space, improving on the prefix-array method that needs O(n) space.

What is the Trapping Rain Water problem?

The Trapping Rain Water problem gives you an array of non-negative integers representing bar heights. After rain, water collects in the dips between taller bars. You must compute the total amount of water trapped.

The water above any single bar depends on two things: the tallest bar anywhere to its left and the tallest bar anywhere to its right. The water level at that position is the smaller of those two maxima, because water spills over the shorter side. The trapped water is that level minus the bar's own height, or zero if the bar is already as tall as or taller than the water level.

package com.bank.service;

// Brute force: for each bar, scan left and right for the maximum
public class TrappingRainBrute {
    public static long trapBrute(int[] heights) {
        long total = 0;
        for (int i = 1; i < heights.length - 1; i++) {
            int leftMax = 0, rightMax = 0;
            for (int l = 0; l <= i; l++) leftMax = Math.max(leftMax, heights[l]);
            for (int r = i; r < heights.length; r++) rightMax = Math.max(rightMax, heights[r]);
            total += Math.min(leftMax, rightMax) - heights[i];
        }
        return total;
    }
}

This brute force runs in O(n^2) time because each bar scans both directions.

Why does the two-pointer approach exist?

The brute-force solution recomputes the left max and right max for every bar, which is wasteful. The prefix-array approach precomputes a leftMax array and a rightMax array in two passes, then sums in a third pass. That is O(n) time but O(n) space for the two arrays.

The two-pointer approach achieves the same O(n) time with O(1) extra space by maintaining the running maxima on the fly with two pointers walking inward from both ends.

package com.bank.service;

// Prefix-array approach: O(n) time, O(n) space
public class TrappingRainPrefix {
    public static long trapPrefix(int[] heights) {
        int n = heights.length;
        if (n < 3) return 0;
        int[] leftMax = new int[n];
        int[] rightMax = new int[n];
        leftMax[0] = heights[0];
        for (int i = 1; i < n; i++) leftMax[i] = Math.max(leftMax[i - 1], heights[i]);
        rightMax[n - 1] = heights[n - 1];
        for (int i = n - 2; i >= 0; i--) rightMax[i] = Math.max(rightMax[i + 1], heights[i]);
        long total = 0;
        for (int i = 0; i < n; i++) total += Math.min(leftMax[i], rightMax[i]) - heights[i];
        return total;
    }
}

How does the two-pointer solution work internally?

You place a left pointer at the first bar and a right pointer at the last bar. You keep two running values: leftMax and rightMax, both starting at zero. At each step you compare the bar at the left pointer with the bar at the right pointer.

If the left bar is less than or equal to the right bar, you process the left side. If the left bar is taller than leftMax, you update leftMax. Otherwise, the difference leftMax minus the left bar is the trapped water at that position, and you add it to the total. Then you move the left pointer inward.

If the right bar is smaller, you process the right side symmetrically with rightMax and move the right pointer inward.

package com.bank.service;

import java.math.BigDecimal;

public class TrappingRainTwoPointer {

    /**
     * Computes trapped water using two pointers.
     * Uses long to avoid overflow when summing large bar heights.
     */
    public static long trap(int[] heights) {
        if (heights == null || heights.length < 3) return 0;

        int left = 0;
        int right = heights.length - 1;
        int leftMax = 0;
        int rightMax = 0;
        long totalTrapped = 0;

        while (left < right) {
            if (heights[left] <= heights[right]) {
                if (heights[left] >= leftMax) {
                    leftMax = heights[left];
                } else {
                    totalTrapped += leftMax - heights[left];
                }
                left++;
            } else {
                if (heights[right] >= rightMax) {
                    rightMax = heights[right];
                } else {
                    totalTrapped += rightMax - heights[right];
                }
                right--;
            }
        }
        return totalTrapped;
    }

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

Trapped reserve: 7

Why is processing the shorter side safe?

This is the key correctness insight that interviewers probe. When the left bar is less than or equal to the right bar, you know for certain that the right side has at least one wall as tall as heights[right], which is at least as tall as heights[left]. The water level at the left position is therefore bounded by leftMax alone, because the right side can only be taller and never reduces the water level.

That guarantee lets you commit the left bar's trapped water immediately without knowing the exact rightMax yet. The mirror argument holds when the right side is the shorter boundary. At every moment, leftMax and rightMax are the true maxima of the regions already processed plus the current pointer positions.

// The invariant: everything left of 'left' and right of 'right'
// has been fully accounted for. The near-side max alone
// determines the water on the shorter side.
//
// Example walkthrough with heights = [3, 0, 2, 0, 4]:
// Step 1: left=0, right=4, h[0]=3 <= h[4]=4 -> process left
//         leftMax = 3 (new wall), no water. left=1
// Step 2: left=1, right=4, h[1]=0 <= h[4]=4 -> process left
//         leftMax=3 > h[1]=0, water += 3-0=3. left=2
// Step 3: left=2, right=4, h[2]=2 <= h[4]=4 -> process left
//         leftMax=3 > h[2]=2, water += 3-2=1. left=3
// Step 4: left=3, right=4, h[3]=0 <= h[4]=4 -> process left
//         leftMax=3 > h[3]=0, water += 3-0=3. left=4
// Loop ends: total = 3+1+3 = 7

How is this different from the prefix-array approach?

Both approaches compute the same result. The difference is space usage.

| Aspect | Prefix Array | Two Pointers |
|---|---|---|
| Time complexity | O(n) | O(n) |
| Space complexity | O(n) for two arrays | O(1) |
| Passes over data | Three (left scan, right scan, sum) | One |
| Clarity | Easier to reason about | Requires invariant understanding |
| Production use | Fine for moderate inputs | Preferred for very large series |

// Prefix arrays need two full-length arrays:
// int[] leftMax = new int[n];   // O(n) space
// int[] rightMax = new int[n];  // O(n) space

// Two pointers need only four variables:
// int leftMax, rightMax, left, right;  // O(1) space

What are the edge cases?

Several inputs need careful handling. An empty array or an array with fewer than three bars cannot form a dip, so the answer is zero. An array of identical heights traps nothing because there are no dips. A monotonically increasing or decreasing array also traps nothing because water would spill off one end.

package com.bank.service;

public class TrappingRainEdgeCases {
    public static void main(String[] args) {
        System.out.println(TrappingRainTwoPointer.trap(new int[]{}));          // 0 (empty)
        System.out.println(TrappingRainTwoPointer.trap(new int[]{5}));         // 0 (single bar)
        System.out.println(TrappingRainTwoPointer.trap(new int[]{5, 5}));      // 0 (two bars)
        System.out.println(TrappingRainTwoPointer.trap(new int[]{1, 2, 3}));   // 0 (increasing)
        System.out.println(TrappingRainTwoPointer.trap(new int[]{3, 2, 1}));   // 0 (decreasing)
        System.out.println(TrappingRainTwoPointer.trap(new int[]{5, 5, 5}));   // 0 (flat)
    }
}

0
0
0
0
0
0

What about overflow and money precision?

When bar heights represent financial amounts, use BigDecimal for exact arithmetic. Even with integer heights, the sum of trapped water across many bars can overflow an int. Using long for the running total is the minimum safeguard.

package com.bank.service;

import java.math.BigDecimal;

public class TrappingRainBigDecimal {
    public static BigDecimal trap(BigDecimal[] heights) {
        if (heights == null || heights.length < 3) return BigDecimal.ZERO;
        int left = 0, right = heights.length - 1;
        BigDecimal leftMax = BigDecimal.ZERO;
        BigDecimal rightMax = BigDecimal.ZERO;
        BigDecimal total = BigDecimal.ZERO;

        while (left < right) {
            if (heights[left].compareTo(heights[right]) <= 0) {
                if (heights[left].compareTo(leftMax) >= 0) {
                    leftMax = heights[left];
                } else {
                    total = total.add(leftMax.subtract(heights[left]));
                }
                left++;
            } else {
                if (heights[right].compareTo(rightMax) >= 0) {
                    rightMax = heights[right];
                } else {
                    total = total.add(rightMax.subtract(heights[right]));
                }
                right--;
            }
        }
        return total;
    }
}

What are common mistakes?

The most frequent mistake is using the wrong comparison direction. Processing the side with the larger boundary instead of the smaller one breaks the correctness invariant.

// WRONG: processing the larger side
if (heights[left] > heights[right]) {  // Bug: should be <=
    // Processing left when right is smaller
    // The left side's water is NOT determined yet
}

// CORRECT: process the shorter side
if (heights[left] <= heights[right]) {
    // Process left: right side guarantees a taller wall
}

Another common mistake is forgetting the edge case of fewer than three bars, which causes an index out of bounds or a wrong non-zero result.

When should you use this approach?

Use the two-pointer Trapping Rain Water approach when you need O(n) time with O(1) space for computing trapped quantities between peaks. It is a classic interview problem that tests the ability to maintain invariants with two converging pointers.

In a banking context, this applies to computing trapped liquidity in balance skylines, where dips between higher-balance days represent idle reserves that could not drain without breaching a wall. The constant-space two-pointer method is preferred over prefix arrays when the daily series spans years of data.

package com.bank.service;

public class LiquidityReserveAnalytic {
    public static void main(String[] args) {
        // Daily balance skyline for Rajesh's account over a week
        int[] dailyBalances = {50000, 20000, 35000, 15000, 60000, 30000, 45000};
        long trappedReserve = TrappingRainTwoPointer.trap(dailyBalances);
        System.out.println("Trapped idle reserve: " + trappedReserve);
    }
}

Trapped idle reserve: 40000

What should a senior engineer know?

A senior engineer should be able to prove the invariant formally. At every step, everything to the left of the left pointer has been fully accounted for, everything to the right of the right pointer has been fully accounted for, and leftMax and rightMax are the true maxima of the processed-and-current regions on each side. Because you only commit water on the side whose boundary is guaranteed smaller, you never over-count or under-count.

The stack-based approach is another O(n) solution that processes bars differently, maintaining a stack of bar indices and computing horizontal layers of water when a taller bar arrives. It is useful for understanding but the two-pointer approach is simpler and uses less space.

What are common interview follow-up questions?

Interviewers commonly ask these follow-ups after Trapping Rain Water:

• Can you solve it in O(1) space? (Yes, the two-pointer approach.)
• What if the bars are in 2D, a grid? (Trapping Rain Water II uses a priority queue BFS from the border.)
• Can you compute trapped water using a stack? (Yes, the monotonic stack approach computes horizontal layers.)
• What if bar heights are floating-point? (Use BigDecimal for exact arithmetic or accept floating-point precision limits.)