Yet another simply O(n) solution in C++


  • 0
    C

    I had this intuition when I saw this problem. Instead of looking at the "trapped" water which is not continuous and distributed everywhere, the final shape of the "histogram" like plot after you fill in water is actually very structured. It will always be a pyramid like shape (or a rectangle) in which each height (h) has no greater width than previous height (h-1). So I set two indices i and j for leftmost and rightmost edge and compute the total width of water+bins at each height from bottom up and cumsum them. At the end, the trapped water can be obtained by removing the bins from input. Have fun !

    class Solution {
    public:
        int trap(vector<int>& height) {
            int water = 0; //total "water" including the previous bins
            int i = 0; //left index 
            int j = height.size()-1; //right index
            int h = 0;
            
            while(i <= j) {
                water += (min(height[i], height[j])-h)*(j-i+1);
                h = min(height[i], height[j]);
                while(i <= j && height[i] <= h) ++i;
                while(i <= j && height[j] <= h) --j;
            }
            for (int h : height) water -= h; //exclude previous bins
            return water;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.