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 is able to trap after raining.

For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

@tag-array

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.

Code

Java

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

    }

}

// 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])
            rmx[n - 1 - i] = max(rmx[n - i], height[n - 1 - i])

        res = 0
        for i in range(n):
            res += min(lmx[i], rmx[i]) - height[i]
        return res

############

class Solution(object):
  def trap(self, height):
    """
    :type height: List[int]
    :rtype: int
    """
    ans = left = 0
    right = len(height) - 1
    leftWall = rightWall = float("-inf")
    while left <= right:
      if leftWall <= rightWall:
        ans += max(0, leftWall - height[left])
        leftWall = max(leftWall, height[left])
        left += 1
      else:
        ans += max(0, rightWall - height[right])
        rightWall = max(rightWall, height[right])
        right -= 1
    return ans

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.

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

// 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])
            rmx[n - 1 - i] = max(rmx[n - i], height[n - 1 - i])

        res = 0
        for i in range(n):
            res += min(lmx[i], rmx[i]) - height[i]
        return res

############

class Solution(object):
  def trap(self, height):
    """
    :type height: List[int]
    :rtype: int
    """
    ans = left = 0
    right = len(height) - 1
    leftWall = rightWall = float("-inf")
    while left <= right:
      if leftWall <= rightWall:
        ans += max(0, leftWall - height[left])
        leftWall = max(leftWall, height[left])
        left += 1
      else:
        ans += max(0, rightWall - height[right])
        rightWall = max(rightWall, height[right])
        right -= 1
    return ans

42 - Trapping Rain Water

Question

Algorithm

Code

Algorithm 2 - not finding the max height

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

Algorithm 2 - not finding the max height

All Problems

All Solutions