Trapping Rain Water hard

Problem Statement

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

Steps

The core idea is to find, for each bar, the maximum water level it can trap. This maximum level is determined by the highest bar to its left and the highest bar to its right. The amount of trapped water for that bar is the minimum of these two heights minus the bar's height. We sum this up for all bars to get the total trapped water.

We can solve this problem using two approaches:

1. Two Pointers: This approach iterates through the array from both ends simultaneously, keeping track of the maximum height encountered so far from the left and right.
2. Dynamic Programming: This approach pre-calculates the maximum height to the left and right for each bar, making the calculation of trapped water straightforward.

Explanation (Two Pointers Approach)

The two-pointer approach is efficient because it iterates through the array only once. It uses two pointers, left and right, initialized to the beginning and end of the array, respectively. It maintains leftMax and rightMax to track the maximum heights encountered from the left and right.

In each iteration:

• If height[left] < height[right], it means the left boundary is the limiting factor. We calculate the trapped water at left, based on leftMax and move left to the right.
• Otherwise, the right boundary is the limiting factor. We calculate trapped water at right based on rightMax and move right to the left.

This process continues until left and right cross each other.

Code (C# - Two Pointers)

public class Solution {
    public 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]) {
                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;
    }
}

Complexity

• Time Complexity: O(n), where n is the length of the height array. We iterate through the array once.
• Space Complexity: O(1). The algorithm uses a constant amount of extra space.

Code (C# - Dynamic Programming)

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

        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(height[i], leftMax[i - 1]);
        }

        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            rightMax[i] = Math.Max(height[i], rightMax[i + 1]);
        }

        int trappedWater = 0;
        for (int i = 0; i < n; i++) {
            trappedWater += Math.Max(0, Math.Min(leftMax[i], rightMax[i]) - height[i]);
        }

        return trappedWater;
    }
}

Complexity (Dynamic Programming)

• Time Complexity: O(n). We iterate through the array three times.
• Space Complexity: O(n). We use two arrays of size n to store leftMax and rightMax. The two-pointer approach is generally preferred due to its better space complexity.