LeetCode Hard — Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]

Output: 6

Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:

Input: height = [4,2,0,3,2,5]

Output: 9

Constraints:

• n == height.length
• 1 <= n <= 2 * 104
• 0 <= height[i] <= 105

Java Solution

To solve this problem, you can use a two-pointer approach. Here’s a Java solution:

public class TrappingRainWater {
    public int trap(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }

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

        while (left < right) {
            if (height[left] < height[right]) {
                if (height[left] >= leftMax) {
                    leftMax = height[left];
                } else {
                    trappedWater += leftMax - height[left];
                }
                left++;
            } else {
                if (height[right] >= rightMax) {
                    rightMax = height[right];
                } else {
                    trappedWater += rightMax - height[right];
                }
                right--;
            }
        }

        return trappedWater;
    }

    public static void main(String[] args) {
        TrappingRainWater solution = new TrappingRainWater();

        // Example 1
        int[] height1 = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        System.out.println("Example 1 Output: " + solution.trap(height1));

        // Example 2
        int[] height2 = {4, 2, 0, 3, 2, 5};
        System.out.println("Example 2 Output: " + solution.trap(height2));
    }
}

This program defines a TrappingRainWater class with the trap method. The two-pointer approach is used to iterate from both ends towards the center while keeping track of the maximum heights from the left and right. The trapped water is calculated based on the difference between the current height and the minimum of the left and right maximum heights. The main method demonstrates how to use the program with the provided examples.

Python Solution

Here’s the equivalent Python solution for the trapping rainwater problem using a two-pointer approach:

class TrappingRainWater:
    def trap(self, height):
        if not height:
            return 0

        left, right = 0, len(height) - 1
        left_max, right_max = 0, 0
        trapped_water = 0

        while left < right:
            if height[left] < height[right]:
                if height[left] >= left_max:
                    left_max = height[left]
                else:
                    trapped_water += left_max - height[left]
                left += 1
            else:
                if height[right] >= right_max:
                    right_max = height[right]
                else:
                    trapped_water += right_max - height[right]
                right -= 1

        return trapped_water

# Example usage:
solution = TrappingRainWater()

# Example 1
height1 = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
print("Example 1 Output:", solution.trap(height1))

# Example 2
height2 = [4, 2, 0, 3, 2, 5]
print("Example 2 Output:", solution.trap(height2))

This Python code mirrors the Java solution. The TrappingRainWater class has the trap method. The two-pointer approach is used to iterate from both ends towards the center while keeping track of the maximum heights from the left and right. The trapped water is calculated based on the difference between the current height and the minimum of the left and right maximum heights. The example usage section demonstrates how to use the program with the provided examples.