LeetCode 42 – Trapping Rain Water: Problem Overview and Three O(n) Solution Techniques (Two‑Pointer, Prefix‑Max, Monotonic Stack)

LeetCode problem 42, "Trapping Rain Water", asks for the amount of water that can be trapped after raining given an array of non‑negative integers representing bar heights.

Example input [0,1,0,2,1,0,1,3,2,1,2,1] yields output 6 .

Two‑pointer solution : Use left and right pointers, maintain a bucket height that never decreases, and accumulate water based on the shorter side at each step.

public int trap(int[] height) {
    int left = 0, right = height.length - 1; // two pointers
    int water = 0;
    int bucketHeight = 0; // bucket height, only increases
    while (left < right) {
        int minHeight = Math.min(height[left], height[right]);
        bucketHeight = Math.max(bucketHeight, minHeight);
        if (height[left] > height[right])
            water += bucketHeight - height[right--];
        else
            water += bucketHeight - height[left++];
    }
    return water;
}

Prefix‑max solution : Compute arrays of the maximum height seen from the left and from the right, then for each position add min(leftMax[i], rightMax[i]) - height[i] to the total water.

public int trap(int[] height) {
    int length = height.length;
    int[] leftMax = new int[length];
    leftMax[0] = height[0];
    for (int i = 1; i < length; ++i)
        leftMax[i] = Math.max(leftMax[i - 1], height[i]);
    int[] rightMax = new int[length];
    rightMax[length - 1] = height[length - 1];
    for (int i = length - 2; i >= 0; --i)
        rightMax[i] = Math.max(rightMax[i + 1], height[i]);
    int water = 0;
    for (int i = 0; i < length; ++i)
        water += Math.min(leftMax[i], rightMax[i]) - height[i];
    return water;
}

Monotonic stack solution : Maintain a stack of indices with increasing heights; when a higher bar appears, pop the stack and calculate trapped water using the distance between the current index and the new stack top and the bounded height.

public int trap(int[] height) {
    int water = 0;
    Stack
stack = new Stack<>(); // monotonic increasing stack
    for (int i = 0; i < height.length; i++) {
        while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
            int index = stack.pop(); // popped bar
            if (!stack.isEmpty()) {
                int left = stack.peek(); // left boundary
                int currWidth = i - left - 1; // width
                int currHeight = Math.min(height[left], height[i]) - height[index];
                water += currWidth * currHeight;
            }
        }
        stack.push(i);
    }
    return water;
}

All three methods run in O(n) time with O(1) or O(n) extra space, providing efficient ways to solve this classic interview question.

Author: Bo Ge, algorithm expert with extensive experience in data structures and algorithms.