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

Algorithm

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, rmx = [height[0]] * n, [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])

        res = 0
        for i in range(n):
            # no negative, worst is, min(left,right) is itself
            res += min(lmx[i], rmx[i]) - height[i]
        return res


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
    }
}

42 - Trapping Rain Water

Question

Algorithm

Algorithm 2 - not finding the max height

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Algorithm 2 - not finding the max height

Code

All Problems

All Solutions