Leetcode Study Day 8

Trapping Rain Water

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

Max Height Approach

The first solution is to get the maximum height of the left of each element and the maximum height of the right of each element respectively. Then based on the two maximum height, we can calculate the water that can be trapped in each element. The total water is the sum of the water trapped in each element.

Left and Right Max Height

int n = height.size();
    vector <int> max_Left(n, 0);
    vector <int> max_Right(n, 0);
    for (int i = 1; i < n; i++){
        if (height[i - 1] > max_Left[i-1]){
            max_Left[i] = height[i - 1];
        }
        else
            max_Left[i] = max_Left[i-1];
    }
    for (int i = n - 2; i >=0; i --){
        if (height[i + 1] > max_Right[i+1]){
            max_Right[i] = height[i + 1];
        }
        else
            max_Right[i] = max_Right[i+1];
    }

The water trapped in each element

For each element, we know the max height of the left and right, we choose the smaller one because the condition of the trapped water is based on the shortest height. Then we minus the height of the current element, the result is the water trapped in the current element. The reason that we minus the current height is that it represents the height that is solid, which represents that the water can’t be trapped in. We then add the water trapped in each element together, the result is the total water trapped in the elevation map.

int trap_water = 0;
for (int i = 0; i < n; i++){
    int minMaxHeight = min (max_Left[i], max_Right[i]);
    if (minMaxHeight - height[i] > 0)
        trap_water += (minMaxHeight - height[i]);
}
return trap_water;

Full code

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        vector <int> max_Left(n, 0);
        vector <int> max_Right(n, 0);
        for (int i = 1; i < n; i++){
            if (height[i - 1] > max_Left[i-1]){
                max_Left[i] = height[i - 1];
            }
            else
                max_Left[i] = max_Left[i-1];
        }
        for (int i = n - 2; i >=0; i --){
            if (height[i + 1] > max_Right[i+1]){
                max_Right[i] = height[i + 1];
            }
            else
                max_Right[i] = max_Right[i+1];
        }
        int trap_water = 0;
        for (int i = 0; i < n; i++){
            int minMaxHeight = min (max_Left[i], max_Right[i]);
            if (minMaxHeight - height[i] > 0)
                trap_water += (minMaxHeight - height[i]);
        }
        return trap_water;

    }
};

Two pointer solution

We can also improved the last solution by using a two pointer solution. In this solution, we don’t need to iterate the loop for three times. The two pointers are called left and right respectively. The left pointer is the index of the leftmost element and the right pointer is the index of the rightmost element. We also create two variables called leftMax and rightMax to store the maximum height of the left and right respectively.

int n = height.size();
int total_water = 0;
int left_max = 0;
int right_max = 0;
int left = 0;
int right = n-1 ;

We called the minimum of leftMax and rightMax water_level, which is to make sure the water will not be leaked in this height. If water_level is higher than the current element’s height, which means some water is trapped in this element, we then update the total_water, left and skip the following operations and jump to the next iteration. The idea from right to the left is similar.

If the current left or right element is higher than the leftMax and the rightMax, we then update the leftmax and the rightMax

while (left < right){
    int water_level = min (left_max, right_max);
    if (water_level >= height[left]){
        total_water += (water_level - height[left]);
        left ++;
        continue;
    }
    if (water_level >= height[right]){
        total_water += (water_level - height[right]);
        right --;
        continue;
    }
    left_max = max(left_max, height[left]);
    right_max = max(right_max, height[right]);
    }

Full Code

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        int total_water = 0;
        int left_max = 0;
        int right_max = 0;
        int left = 0;
        int right = n-1 ;
        while (left < right){
            int water_level = min (left_max, right_max);
            if (water_level >= height[left]){
                total_water += (water_level - height[left]);
                left ++;
                continue;
            }
            if (water_level >= height[right]){
                total_water += (water_level - height[right]);
                right --;
                continue;
            }
            left_max = max(left_max, height[left]);
            right_max = max(right_max, height[right]);
        }
        return total_water;
    }
};