[LeetCode] 42. Trapping Rain Water

Posted on | In

Problem

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.

42. Trapping Rain Water The above elevation map 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. Thanks Marcos for contributing this image!

Example:

1
2
Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

Explanation 1

  1. We notice that each element’s water height is equal to the minimum of current element’s leftMostHeight and rightMostHeight then subtract the current element’s height. From the above example, if the current element is at index 5, then it’s left side’s maximum height is 2 at index 3, it’s rightside’s maximum height is 3 at index 7. So the current element’s water height is minimum of 2 and 3, then minius current element’s height 0, which will be $2-0=2$.

  2. We can create a leftMost array and a rightMost array to keep track of each element’s left most and right most height. Then loop again to get each current element’s water height and sum it as the result.

Solution 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int trap(int[] height) {
        int[] left = new int[height.length];
        int[] right = new int[height.length];
        int leftMost = 0, rightMost = 0;
        
        for (int i = 1; i < left.length; i++) {
            leftMost = Math.max(leftMost,height[i-1]);
            left[i] = leftMost;
        }
        
        for (int i = right.length-2; i >= 0; i--) {
            rightMost = Math.max(rightMost, height[i+1]);
            right[i] = rightMost;
        }
        
        int res = 0;
        for (int i = 0; i < height.length; i++) {
            int min = Math.min(left[i], right[i]);
            if (min > height[i]) {
                res += (min-height[i]);
            }
        }
        
        return res;
    }
}

Explanation 2

  1. We can solve this problem in $O(1)$ space by using left pointer and right pointer technique.

  2. When left pointer moving toward right, it keeps track the leftMostHeight; when right pointer moving toward middle, it keeps track of the rightMostHeight. While left pointer and right pointer not meet, choose the minimum of leftMostHeight and rightMostHeight then subtract the respective element’s height, that will be that element’s water height, then moving the respective pointer toward middle until left pointer and right pointer meet.

  3. For example, from the above example, when left pointer is at index 4, its leftMost is 2, when right pointer at index 7, its rightMost is 3. because leftMost is less than rightMost, so we use the minimum between leftMost and rightMost to subtract current element’s height, which means $2-1=1$, so at index 4, we have water 1. Then we move the left pointer 1 step toward middle.

Solution 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int trap(int[] height) {
        int leftMost = 0, rightMost = 0;
        int left = 0, right = height.length-1;
        int res = 0;
        while (left < right) {
            leftMost = Math.max(leftMost, height[left]);
            rightMost = Math.max(rightMost, height[right]);
            if (leftMost < rightMost) {
                res += leftMost - height[left];
                left++;
            } else {
                res += rightMost - height[right];
                right--;
            }
        }
        
        return res;
    }
}