Givan an aray of non-negative integers representing the heights of vertical bars where each bar has width 1, determine how much water can be trapped after raining.

Example 1:

Input: [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6 Explanation: The blue regions represent trapped rainwater units.

Example 2:

Input: [4,2,0,3,2,5] Output: 9

Constraints:

• Array length n satisfies 1 <= n <= 2 * 10^4
• Each element height[i] satisfies 0 <= height[i] <= 10^5

Solution Approach 1: Brute Force Method (trap function)

1. Initialize total_water to accumulate the volume of trapped water.
2. Iterate through all elements except the first and last since they cannot hold water.
3. For each position, find the maximum height to its left (left_max) and right (right_max).
4. The amount of water above the current bar is min(left_max, right_max) - current_height, which is added to total_water.

Solution Approach 2: Two Pointers Technique (trap1 function)

1. Begin with total_water initialized to zero.
2. Use two pointers, start and end, starting from both ends of the array.
3. Move the pointer pointing to the shorter bar inward, updating the maximum hieght seen so far on that side.
4. Add the difference between the current max and the bar's height to total_water.
5. Continue until the two pointers meet.

This approach achieves linear time complexity O(n), compared to O(n²) for brute force.

package org.example.mouth7.today713;

public class RainwaterTrapping {
    public static void main(String[] args) {
        int[] heights = {0,1,0,2,1,0,1,3,2,1,2,1};
        int[] heights1 = {4,2,0,3,2,5};
        System.out.println(trap1(heights1));
        System.out.println(trap1(heights));
    }

    public static int trap(int[] heights) {
        int total_water = 0;
        int len = heights.length;
        for (int i = 1; i < len - 1; i++) {
            int left_max = 0, right_max = 0;
            for (int j = i; j >= 0; j--) {
                left_max = Math.max(left_max, heights[j]);
            }
            for (int j = i; j < len; j++) {
                right_max = Math.max(right_max, heights[j]);
            }
            total_water += Math.min(left_max, right_max) - heights[i];
        }
        return total_water;
    }

    public static int trap1(int[] heights) {
        int total_water = 0;
        int len = heights.length;
        int start = 0, end = len - 1;
        int max_left = 0;
        int max_right = 0;
        while (start < end) {
            max_left = Math.max(max_left, heights[start]);
            max_right = Math.max(max_right, heights[end]);
            if (heights[start] < heights[end]) {
                total_water += max_left - heights[start];
                start++;
            } else {
                total_water += max_right - heights[end];
                end--;
            }
        }
        return total_water;
    }
}