Trapping Rain Water and Container With Most Water

Container With Most Water (LeetCode 11)

Use two pointers starting at both ends, and at each step, move the pointer pointing to the shorter line.

int maxArea(int[] height) {
    int l = 0, r = height.length - 1, res = 0;
    while (l < r) {
        // Area is limited by the height of the shorter pointer
        int area = Math.min(height[l], height[r]) * (r - l);
        res = Math.max(res, area);
        
        // Move the shorter pointer to seek a taller wall
        if (height[l] < height[r]) l++;
        else r--;
    }
    return res;
}

Why move the shorter line? If you move the taller line, the width will decrease, and the new height cannot be greater than the current shorter line. Thus, the area can only decrease or stay the same. Moving the shorter line is the only way to potentially find a taller boundary and increase the area.

Complexity: Time O(n), Space O(1).

Trapping Rain Water (LeetCode 42)

Method 1: Dynamic Programming (O(n) Space)

The water trapped at each position is determined by min(max_height_to_left, max_height_to_right) - current_height.

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

    int water = 0;
    for (int i = 0; i < n; i++)
        water += Math.min(leftMax[i], rightMax[i]) - height[i];
    return water;
}

Method 2: Two Pointers (O(1) Space)

Maintain leftMax and rightMax on the fly using two pointers.

int trapTwoPointers(int[] height) {
    int l = 0, r = height.length - 1;
    int leftMax = 0, rightMax = 0, water = 0;
    while (l < r) {
        if (height[l] < height[r]) {
            if (height[l] >= leftMax) leftMax = height[l];
            else water += leftMax - height[l];
            l++;
        } else {
            if (height[r] >= rightMax) rightMax = height[r];
            else water += rightMax - height[r];
            r--;
        }
    }
    return water;
}

Logic: The height of water trailing at l is constrained by the minimum of the maximum elements to its left and right.

• If height[l] < height[r], we know that there is a wall to the right (at least height[r]) that is taller than any wall we might find to the left of l (leftMax). Thus, the limiting factor at l is definitely leftMax.

Method 3: Monotonic Stack

Maintain a stack of indices with decreasing heights. When a taller wall is found, pop elements and calculate the trapped water horizontally:

int trapStack(int[] height) {
    Deque<Integer> stack = new ArrayDeque<>();
    int water = 0;
    for (int i = 0; i < height.length; i++) {
        while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
            int bottomIndex = stack.pop();
            if (stack.isEmpty()) break;
            int leftIndex = stack.peek();
            
            int width = i - leftIndex - 1;
            int h = Math.min(height[i], height[leftIndex]) - height[bottomIndex];
            water += width * h;
        }
        stack.push(i);
    }
    return water;
}

Comparison