Trapping Rain Water - Java Solution

1. Introduction

In this post, we explore a solution to the "Trapping Rain Water" problem, which is a fascinating question in the realm of array and two-pointer techniques. The problem involves calculating the total amount of rainwater that can be trapped between bars of varying heights, represented as an array.

Problem

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

2. Solution Steps

1. Initialize two pointers left and right at the beginning and end of the array, respectively.

2. Maintain two variables leftMax and rightMax to keep track of the maximum height seen so far from the left and right.

3. Iterate through the array using the two pointers:

a. Update leftMax and rightMax as the maximum height seen so far from each side.

b. If height[left] < height[right], water trapped on the current bar is leftMax - height[left]. Add this to the total water trapped and move left pointer forward.

c. Else, water trapped on the current bar is rightMax - height[right]. Add this to the total water trapped and move right pointer backward.

4. Continue this process until left and right pointers meet.

5. Return the total amount of water trapped.

3. Code Program

public class TrappingRainWater {
    public static void main(String[] args) {
        int[] height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        System.out.println(trap(height)); // Test the function
    }

    // Function to calculate the total water trapped
    public static int trap(int[] height) {
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0;
        int trappedWater = 0;

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

        return trappedWater;
    }
}

Output:

6

Explanation:

1. trap: This function computes the total amount of rainwater that can be trapped.

2. Two-pointer technique is used, with left and right pointers starting from the beginning and end of the array, respectively.

3. leftMax and rightMax keep track of the maximum heights encountered so far from the left and right.

4. The function calculates water trapped at each bar based on the minimum of leftMax and rightMax and the current height.

5. The pointers are moved inward, updating leftMax and rightMax and accumulating trapped water.

6. The process continues until the left and right pointers meet, covering all possible locations for trapping water.

7. This method effectively computes the trapped water with O(n) time complexity and O(1) space complexity, making it an optimal solution.