Leetcode 42. Trapping RainWater

 42. Trapping RainWater

Hard, Dynamic Programming

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 * 10⁴
• 0 <= height[i] <= 10⁵

 To solve the Trapping Rain Water problem, we can calculate the amount of water trapped above each bar in the elevation map. Below are three approaches:

---

Approaches:

1. Brute Force:

   • For each bar, calculate the maximum height of bars to the left and right.
   • Water above the current bar is determined by the minimum of these two heights minus the height of the current bar.

2. Dynamic Programming:

   • Precompute the maximum height of bars to the left (leftMax) and right (rightMax) for each index.
   • For each bar, the water trapped is the difference between the minimum of leftMax and rightMax and the height of the bar.

3. Two Pointers:

   • Use two pointers (left and right) and two variables to keep track of the maximum heights from the left and right.
   • Move the pointers inward, adding trapped water based on the smaller height.

---

Implementation (Two Pointers Approach):

The two-pointer approach is efficient and works in $O(n)$ time and $O(1)$ space.

public class Solution {
    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, waterTrapped = 0;

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

        return waterTrapped;
    }
}

---

Implementation (Dynamic Programming Approach):

public class Solution {
    public int Trap(int[] height) {
        if (height == null || height.Length == 0) return 0;

        int n = height.Length;
        int[] leftMax = new int[n];
        int[] 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 waterTrapped = 0;
        for (int i = 0; i < n; i++) {
            waterTrapped += Math.Min(leftMax[i], rightMax[i]) - height[i];
        }

        return waterTrapped;
    }
}

---

Implementation (Brute Force Approach):

public class Solution {
    public int Trap(int[] height) {
        if (height == null || height.Length == 0) return 0;

        int n = height.Length, waterTrapped = 0;
        for (int i = 0; i < n; i++) {
            int leftMax = 0, rightMax = 0;

            // Find the maximum height to the left of the current bar
            for (int j = 0; j <= i; j++) {
                leftMax = Math.Max(leftMax, height[j]);
            }

            // Find the maximum height to the right of the current bar
            for (int j = i; j < n; j++) {
                rightMax = Math.Max(rightMax, height[j]);
            }

            waterTrapped += Math.Min(leftMax, rightMax) - height[i];
        }

        return waterTrapped;
    }
}

---

Complexity Analysis:

1. Brute Force:

   • Time Complexity: $O(n^2)$ — Two nested loops for left and right max calculations.
   • Space Complexity: $O(1)$ — No extra space used.

2. Dynamic Programming:

   • Time Complexity: $O(n)$ — Precomputing left and right max arrays and a single traversal.
   • Space Complexity: $O(n)$ — Left and right max arrays.

3. Two Pointers:

   • Time Complexity: $O(n)$ — Single traversal of the array.
   • Space Complexity: $O(1)$ — Only a few variables used.

---

Example Outputs:

Example 1:

• Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
• Output: 6

Example 2:

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