Problem description:

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.

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:

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

Solution:

An element of array can store water if there’re higher bar on left and right.
Use two variables to store the left_max and right_max. The reason doing this is because the water trapped at any element= min(left_max, right_max)- height[i]. So we can calculate the water trapped on smaller element out of height[left] and height[right] first, then move the pointers with condition left <= right.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def trap(self, height: List[int]) -> int:
        # keep left_max, right_max to know if there's a higher bar 
        # only move left pointer when height[left] is smaller than height[right]
        # only move right pointer when height[right] is smaller than height[left]
        res, left, right = 0, 0, len(height)-1
        left_max, right_max = 0, 0
        while left<= right:
            if height[left]< height[right]:
                if height[left]> left_max:
                    left_max= height[left]
                else:
                    res += left_max-height[left]
                left += 1
            else:
                if height[right]> right_max:
                    right_max= height[right]
                else:
                    res+= right_max-height[right]
                right -= 1
        return res
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
28
class Solution {
public:
    int trap(vector<int>& height) {
        // if an element of the array can store water, if has a bar on it's left and right
        int res= 0;
        int left= 0, right= height.size()-1;
        int left_max= 0, right_max= 0;
        
        while(left<= right){
            if(height[left]< height[right]){
                // this means height[right] is definitely a bar, so just consider left side below
                if(height[left]> left_max)
                    left_max= height[left];
                else
                    res += left_max-height[left];
                left++;
            }
            else{
                if(height[right]> right_max)
                    right_max= height[right];
                else
                    res+= right_max-height[right];
                right--;
            }
        }
        return res;
    }
};

Solution DP

The idea is to know what the max height is, to the left and right of every index. Think about it- at any given index, there can only be trapped rain water above it if the min(max_height_to_the_left, max_height_to_the_right) is bigger than the height at this particular index.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def trap(self, height: List[int]) -> int:
        tmp_left, tmp_right, n = 0, 0, len(height)
        max_left, max_right = [0]*n, [0]*n
        
        for i in range(n):
            max_left[i] = tmp_left  # index i's left boundary is tmp_left
            if height[i] > tmp_left: # current height is greater, update the tmp_left so it could be coundary for upcoming indexes
                tmp_left = height[i]
        
        for i in range(n-1, -1, -1):
            max_right[i] = tmp_right
            if height[i] > tmp_right:
                tmp_right = height[i]
        
        res = 0
        for i in range(n):
            if height[i] < min(max_left[i], max_right[i]):
                res += min(max_left[i], max_right[i])-height[i]
        return res

time complexity: $O(n)$
space complexity: $O(1)$
reference:
https://goo.gl/rNJVRc