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

• Trapping Rain Water – computes how much water is held between bars of varying heights after rain.
• Two-pointer method – a left and right pointer walk inward, each tracking its running maximum height.
• Processing rule – at each step, process whichever side has the smaller boundary, adding trapped water or updating the wall.
• Time and space – O(n) time and O(1) extra space, improving on the prefix-array version that uses O(n) space.
• Correctness invariant – when one side is shorter, the other side guarantees a wall at least as tall, so the near-side max alone determines the water.

What is the Trapping Rain Water two-pointer approach?

The two-pointer approach to Trapping Rain Water uses a left pointer starting at the first bar and a right pointer at the last bar, walking inward until they meet. Two running variables, leftMax and rightMax, track the tallest bar seen so far from each direction. At each step, you process the side with the smaller boundary wall.

package com.bank.service;

public class TrappingRainTwoPointer {
    public static long trap(int[] h) {
        if (h == null || h.length < 3) return 0;
        int left = 0, right = h.length - 1;
        int leftMax = 0, rightMax = 0;
        long total = 0;
        while (left < right) {
            if (h[left] < h[right]) {
                if (h[left] >= leftMax) leftMax = h[left];
                else total += leftMax - h[left];
                left++;
            } else {
                if (h[right] >= rightMax) rightMax = h[right];
                else total += rightMax - h[right];
                right--;
            }
        }
        return total;
    }
}

Why does processing the shorter side work?

When heights[left] is less than heights[right], you know the right side has at least one wall as tall as heights[right], which is at least as tall as heights[left]. The water over the left bar is therefore limited purely by leftMax, because the right side can only be taller and never reduces the water level.

This guarantee lets you commit the left bar's trapped water immediately without knowing the exact rightMax yet. The symmetric argument applies when processing the right side.

// Walkthrough: heights = [2, 0, 3, 0, 5]
// left=0,right=4: h[0]=2 < h[4]=5, leftMax=2 (new wall), left=1
// left=1,right=4: h[1]=0 < h[4]=5, water+=2-0=2, left=2
// left=2,right=4: h[2]=3 < h[4]=5, leftMax=3 (new wall), left=3
// left=3,right=4: h[3]=0 < h[4]=5, water+=3-0=3, left=4
// Total = 5

How is this different from the prefix-array approach?

The prefix-array approach precomputes a leftMax array and a rightMax array in two passes, then sums in a third pass. It is O(n) time but O(n) space.

| Aspect | Prefix Array | Two Pointers |
|---|---|---|
| Time | O(n) | O(n) |
| Space | O(n) for two arrays | O(1) |
| Number of passes | Three | One |
| Ease of proof | Straightforward | Requires invariant reasoning |

package com.bank.service;

public class TrappingRainPrefixComparison {
    // Prefix version: two extra arrays
    public static long trapPrefix(int[] h) {
        int n = h.length;
        int[] lm = new int[n], rm = new int[n];
        lm[0] = h[0];
        for (int i = 1; i < n; i++) lm[i] = Math.max(lm[i-1], h[i]);
        rm[n-1] = h[n-1];
        for (int i = n-2; i >= 0; i--) rm[i] = Math.max(rm[i+1], h[i]);
        long total = 0;
        for (int i = 0; i < n; i++) total += Math.min(lm[i], rm[i]) - h[i];
        return total;
    }
    // Two-pointer version: no extra arrays
    // See TrappingRainTwoPointer.trap()
}

What are the edge cases?

The algorithm handles special inputs naturally. An empty array or one with fewer than three bars returns zero because no dip can form. A flat array of identical heights traps nothing. A strictly increasing or decreasing array also traps nothing.

package com.bank.service;

public class TrapEdgeCases {
    public static void main(String[] args) {
        System.out.println(TrappingRainTwoPointer.trap(new int[]{}));        // 0
        System.out.println(TrappingRainTwoPointer.trap(new int[]{5}));       // 0
        System.out.println(TrappingRainTwoPointer.trap(new int[]{1,2,3}));   // 0
        System.out.println(TrappingRainTwoPointer.trap(new int[]{3,3,3}));   // 0
    }
}

0
0
0
0

What about overflow and money precision?

When bar heights represent daily account balances in rupees, the sum of trapped water across many bars can overflow an int. Using long for the total is the minimum safeguard. For exact financial arithmetic, use BigDecimal.

package com.bank.service;

import java.math.BigDecimal;

public class TrapBigDecimal {
    public static BigDecimal trap(BigDecimal[] h) {
        if (h == null || h.length < 3) return BigDecimal.ZERO;
        int l = 0, r = h.length - 1;
        BigDecimal lm = BigDecimal.ZERO, rm = BigDecimal.ZERO, total = BigDecimal.ZERO;
        while (l < r) {
            if (h[l].compareTo(h[r]) < 0) {
                if (h[l].compareTo(lm) >= 0) lm = h[l];
                else total = total.add(lm.subtract(h[l]));
                l++;
            } else {
                if (h[r].compareTo(rm) >= 0) rm = h[r];
                else total = total.add(rm.subtract(h[r]));
                r--;
            }
        }
        return total;
    }
}

What are common mistakes?

The most frequent mistake is processing the larger side instead of the smaller side, which breaks the invariant.

// WRONG: processing the larger side
if (h[left] > h[right]) {  // Bug!
    // left side water is NOT determined yet
}

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

Another mistake is forgetting the fewer-than-three-bars guard, which causes array index errors.

When should you use this technique?

Use it when you need to compute trapped quantities between peaks in a single pass with constant space. The pattern appears in liquidity analytics, reserve measurement, and any scenario where bar heights form a skyline and you need the volume of the dips.

package com.bank.service;

public class ReserveAnalytic {
    public static void main(String[] args) {
        int[] weeklyBalances = {50000, 20000, 35000, 15000, 60000};
        long reserve = TrappingRainTwoPointer.trap(weeklyBalances);
        System.out.println("Trapped reserve across the week: " + reserve);
    }
}

Trapped reserve across the week: 40000

What should a senior engineer know?

A senior engineer should be able to prove the loop invariant formally. At every moment, everything to the left of the left pointer and everything to the right of the right pointer has been fully accounted for. The leftMax and rightMax values are the true maxima of the processed-and-current regions on each side.

The stack-based approach is an alternative O(n) solution that computes horizontal layers of water using a monotonic stack. It is useful for understanding but the two-pointer approach is simpler and uses less space.

The 2D extension, Trapping Rain Water II, uses a priority queue BFS from the grid border to determine the water level at each cell, which is a natural but harder generalization.

What are common interview follow-up questions?

• Interviewers commonly ask:
• Can you solve it in O(1) space? (Yes, the two-pointer approach.)
• What about the 2D grid version? (Priority queue BFS from the border.)
• Can you solve it with a stack? (Yes, monotonic stack for horizontal layers.)
• How do you handle floating-point bar heights? (Use BigDecimal for exact arithmetic.)