Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/42.html

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

Algorithm - firstly finding the max height

Based on Dynamic Programming, maintaining a one-dimensional dp array, this DP algorithm needs to traverse the array two passes.

The first pass stores the maximum value of the left position of i in dp[i], and then starts the second pass to traverse the array.

In the second traversal, find the maximum value on the right, and then compare it with the maximum on the left to take the smaller value, and compare it with the current value A[i]. If it is greater than the current value, store the difference in the result.

Algorithm 2 - not finding the max height

If height has length 0, then return 0.

Loop over height in both directions and use two arrays leftMax and rightMax to store maximum height in both directions. Each element in the array leftMax represents the maximum height in the subarray from the leftmost index to the current index. Each element in the array rightMax represents the maximum height in the subarray from the current index to the rightmost index.

For each index i, the maximum amount of water trapped at the index is Math.min(leftMax[i], rightMax[i]) - height[i]. Thus the total amount of water trapped can be obtained.

Code

  • public class Trapping_Rain_Water {
    
        public static void main(String[] args) {
            Trapping_Rain_Water out = new Trapping_Rain_Water();
            Solution_local_minimum s = out.new Solution_local_minimum();
    
            System.out.println(s.trap(new int[]{5,2,1,2,1,5}));
        }
    
        // The short board effect, the storage capacity is related to the short board of the bucket.
        // Find the longest slab in the height array, and then iterate from both ends to the long slab. When encountering a shorter one, find the storage capacity, and when encountering a longer one, update the edge.
        public class Solution_optimize {
            public int trap(int[] height) {
    
                if (height == null || height.length == 0)     return 0;
    
                int sum = 0;
                int maxind = 0;
                int max = Integer.MIN_VALUE;
    
                // find max index
                for (int i = 0; i < height.length; i++) {
                    if (height[i] > max) {
                        max = height[i];
                        maxind = i;
                    }
                }
    
                // left
                int leftmax = height[0];
                for (int i = 1; i < maxind; i++) {
    
                    if (leftmax < height[i]) {
                        leftmax = height[i];
                    }
    
                    sum += leftmax - height[i];
                }
    
                // right
                int rightmax = height[height.length - 1];
                for (int i = height.length - 2; i > maxind; i--) {
                    if (rightmax < height[i]) {
                        rightmax = height[i];
                    }
    
                    sum += rightmax - height[i];
                }
    
                return sum;
            }
        }
    
        // local minimum solution is NOT doable. like [5,2,1,2,1,5], there are 2 local minimums with each holding 1 water
        // but they are just part of a global minimum
        class Solution_local_minimum {
    
            public int trap(int[] height) {
    
                // for each position, probe to left and right, find local minimum
    
                if (height == null || height.length == 0)     return 0;
    
                int sum = 0;
    
                int i = 1; // index=0 or index=length-1 will not be a local min, since nothing on its left to hold water
                while (i < height.length - 1) {
    
                    // only process local min index
                    if (height[i] < height[i - 1] && height[i] < height[i + 1]) {
    
                        int left = i - 1;
                        while (left - 1 >= 0 && height[left] < height[left - 1]) {
                            left--;
                        }
    
                        int right = i + 1;
                        while (right + 1 < height.length && height[right] < height[right + 1]) {
                            right++;
                        }
    
                        // now find its highest bar on both sides
                        int lower = Math.min(height[left], height[right]);
    
                        // add up
                        while (left < right) {
    
                            if (height[left] < lower) {
                                sum += lower - height[left];
                            }
    
                            left ++;
                        }
    
                        // update pointer to search next local minimum
                        i = right;
    
                    } else {
                        i++;
                    }
                }
    
                return sum;
            }
    
        }
    
    }
    
    
    //////
    
    class Solution_notFindingMaxHeight {
        public int trap(int[] height) {
            if (height == null || height.length == 0)
                return 0;
            int length = height.length;
            int[] leftMax = new int[length]; // `leftMax` represents the maximum height in the subarray from the leftmost index to the current index
            int[] rightMax = new int[length]; // `rightMax` represents the maximum height in the subarray from the current index to the rightmost index
            leftMax[0] = height[0];
            for (int i = 1; i < length; i++)
                leftMax[i] = Math.max(height[i], leftMax[i - 1]);
            rightMax[length - 1] = height[length - 1];
            for (int i = length - 2; i >= 0; i--)
                rightMax[i] = Math.max(height[i], rightMax[i + 1]);
            int amount = 0;
            for (int i = 0; i < length; i++)
                amount += Math.min(leftMax[i], rightMax[i]) - height[i];
            return amount;
        }
    }
    
    //////
    
    class Solution {
        public int trap(int[] height) {
            int n = height.length;
            if (n < 3) {
                return 0;
            }
    
            int[] lmx = new int[n];
            int[] rmx = new int[n];
            lmx[0] = height[0];
            rmx[n - 1] = height[n - 1];
            for (int i = 1; i < n; ++i) {
                lmx[i] = Math.max(lmx[i - 1], height[i]);
                rmx[n - 1 - i] = Math.max(rmx[n - i], height[n - i - 1]);
            }
    
            int res = 0;
            for (int i = 0; i < n; ++i) {
                res += Math.min(lmx[i], rmx[i]) - height[i];
            }
            return res;
        }
    }
    
  • // OJ: https://leetcode.com/problems/trapping-rain-water/
    // Time: O(N)
    // Space: O(N)
    class Solution {
    public:
        int trap(vector<int>& A) {
            int N = A.size(), ans = 0;
            vector<int> left(N, 0), right(N, 0);
            for (int i = 1; i < N; ++i) left[i] = max(left[i - 1], A[i - 1]);
            for (int i = N - 2; i >= 0; --i) right[i] = max(right[i + 1], A[i + 1]);
            for (int i = 1; i < N - 1; ++i) ans += max(0, min(left[i], right[i]) - A[i]);
            return ans;
        }
    };
    
  • class Solution:
        def trap(self, height: List[int]) -> int:
            n = len(height)
            if n < 3:
                return 0
    
            lmx = [height[0]] * n
            rmx = [height[n - 1]] * n
            for i in range(1, n):
                lmx[i] = max(lmx[i - 1], height[i]) # i self compare
                rmx[n - 1 - i] = max(rmx[n - i], height[n - 1 - i])
    
            # no negative, worst is, min(left,right) is itself
            return sum( min(lmx[i], rmx[i]) - height[i] for i in range(n) )
    
    ######
    
    class Solution: # zip
        def trap(self, height: List[int]) -> int:
            n = len(height)
            left = [height[0]] * n
            right = [height[-1]] * n
            for i in range(1, n):
                left[i] = max(left[i - 1], height[i])
                right[n - i - 1] = max(right[n - i], height[n - i - 1])
            return sum(min(l, r) - h for l, r, h in zip(left, right, height))
    
    ######
    
    class Solution: # find the highest bar first
        def trap(self, height: List[int]) -> int:
            if not height:
                return 0
    
            total_water = 0
            max_index = 0
            max_height = float('-inf')
    
            # Find the index of the maximum height
            for i in range(len(height)):
                if height[i] > max_height:
                    max_height = height[i]
                    max_index = i
    
            # Calculate water trapped on the left side of the maximum height
            left_max = height[0]
            for i in range(1, max_index):
                if left_max < height[i]:
                    left_max = height[i]
                total_water += left_max - height[i]
    
            # Calculate water trapped on the right side of the maximum height
            right_max = height[-1]
            for i in range(len(height) - 2, max_index, -1):
                if right_max < height[i]:
                    right_max = height[i]
                total_water += right_max - height[i]
    
            return total_water
    
  • func trap(height []int) int {
    	n := len(height)
    	if n < 3 {
    		return 0
    	}
    
    	lmx, rmx := make([]int, n), make([]int, n)
    	lmx[0], rmx[n-1] = height[0], height[n-1]
    	for i := 1; i < n; i++ {
    		lmx[i] = max(lmx[i-1], height[i])
    		rmx[n-1-i] = max(rmx[n-i], height[n-1-i])
    	}
    
    	res := 0
    	for i := 0; i < n; i++ {
    		res += min(lmx[i], rmx[i]) - height[i]
    	}
    	return res
    }
    
    func max(a, b int) int {
    	if a > b {
    		return a
    	}
    	return b
    }
    
    func min(a, b int) int {
    	if a < b {
    		return a
    	}
    	return b
    }
    
  • function trap(height: number[]): number {
        let ans = 0;
        let left = 0,
            right = height.length - 1;
        let maxLeft = 0,
            maxRight = 0;
        while (left < right) {
            if (height[left] < height[right]) {
                // move left
                if (height[left] >= maxLeft) {
                    maxLeft = height[left];
                } else {
                    ans += maxLeft - height[left];
                }
                ++left;
            } else {
                // move right
                if (height[right] >= maxRight) {
                    maxRight = height[right];
                } else {
                    ans += maxRight - height[right];
                }
                --right;
            }
        }
        return ans;
    }
    
    
  • public class Solution {
        public int Trap(int[] height) {
            int n = height.Length;
            int[] left = new int[n];
            int[] right = new int[n];
            left[0] = height[0];
            right[n - 1] = height[n - 1];
            for (int i = 1; i < n; ++i) {
                left[i] = Math.Max(left[i - 1], height[i]);
                right[n - i - 1] = Math.Max(right[n - i], height[n - i - 1]);
            }
            int ans = 0;
            for (int i = 0; i < n; ++i) {
                ans += Math.Min(left[i], right[i]) - height[i];
            }
            return ans;
        }
    }
    
  • impl Solution {
        #[allow(dead_code)]
        pub fn trap(height: Vec<i32>) -> i32 {
            let n = height.len();
            let mut left: Vec<i32> = vec![0; n];
            let mut right: Vec<i32> = vec![0; n];
    
            left[0] = height[0];
            right[n - 1] = height[n - 1];
    
            // Initialize the left & right vector
            for i in 1..n {
                left[i] = std::cmp::max(left[i - 1], height[i]);
                right[n - i - 1] = std::cmp::max(right[n - i], height[n - i - 1]);
            }
    
            let mut ans = 0;
    
            // Calculate the ans
            for i in 0..n {
                ans += std::cmp::min(left[i], right[i]) - height[i];
            }
    
            ans
        }
    }
    

All Problems

All Solutions