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

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

^
|
|                        __
|            __         |  |__    __
|   __    __|  |__    __|  |  |__|  |__
|__|__|__|__|__|__|__|_________________|

Difficulty Hard

Related Problems [LeetCode 11] Container With Most Water

Analysis

We need to know at least of two bars' height before we can calculate how much water they can trap. This means, for each bar, if it wants to trap water on it, it must has a left bar and right bar both higher than it.

Idea 1 Time: O(n), Space: O(1) Iterate over the sequence of bars, find the highest bar, then calculate the left capacity and right capacity respectively. Iterating over each bar, when current bar's height is shorter than the previous highest bar, add leftHighest - height[i] to sum.

                        highest
     peak               _/_                   peak
    _/_ height[i]      |   |       height[j] _/_
 __|   |_/_            |   |             _\_|   |
|__|___|___|___________|___|____________|___|___|

Idea 2 Time: O(n), Space: O(n) For each bar, find the highest bars in its left and right. the water that it can store is min(maxLeft, maxRigth) - height

Procedure:

1. iterate from begin to end, get each bar's left highest bar.
2. iterate from end to begin, get each bar's right highest bar.
3. iterate from begin to end, sum up each bar's capacity.

Solutions

1. Cpp solution 9ms

class Solution{
public:
    int trap(const vector<int> &heights){
        const int n = heights.size();
        int maxi = 0; // the highest height, separate the array into to two part
        for(int i = 0; i < n; ++i){
            if(heights[maxi] < heights[i]) maxi = i;
        }
        int water = 0;
        for(int i = 0, peak = 0; i < maxi; ++i){
            if(heights[i] > peak) peak = heights[i];
            else water += peak - heights[i];
        }
        for(int i = n - 1, peak = 0; i > maxi; --i){
            if(heights[i] > peak) peak = heights[i];
            else water += peak - heights[i];
        }
        return water;
    }
};

1. Cpp solution

class Solution{
public:
    int trapRainWater(const vector<int> &heights){
        const int n = heights.size();
        vector<int> max_left(n, 0);
        vector<int> max_right(n, 0);

        for(int i = 1; i < n; ++i){
            max_left[i] = max(max_left[i - 1], heights[i - 1]);
            max_right[n - 1 - i] = max(max_right[n - i], heights[n - i]);
        }
        int sum = 0;
        for(int i = 0; i < n; ++i){
            int height = min(max_left[i], max_right[i]);
            if(height > heights[i]){
                sum += height - heights[i];
            }
        }

        return sum;
    }
};

1. Go solution 9ms

func trap(height []int) int {
    maxIndex := 0
    for i, v := range height {
        if v > height[maxIndex] {
            maxIndex = i
        }
    }

    sum := 0
    for i, maxLeft := 0, 0; i < maxIndex; i++ {
        if height[i] > maxLeft {
            maxLeft = height[i]
        } else {
            sum += maxLeft - height[i]
        }
    }

    for i, maxRight := len(height) - 1, 0; i > maxIndex; i-- {
        if height[i] > maxRight {
            maxRight = height[i]
        } else {
            sum += maxRight - height[i]
        }
    }

    return sum
}

Reference