O(n) solution, O(1) space, simple c++ soln with comments.


  • 0
    M

    Basic idea is to keep a count of running water and everytime we encounter a closing wall, we store that water in a accumulated counter. If we never encounter a closing wall, that water is drained. For every value on the x-axis assume you store the current maximum of water, and then subtract the amount which was taken by the building.

    class Solution {
    public:
        int trap(vector<int>& height) {
            int total_blocks = height.size();
            
            int accumulated = 0;
            int current = 0;
            int max = 0;
            
            for (int i = 0; i < total_blocks; i++) {
                if (height[i] > max) {
                    // Found a closing wall, accumulate
                    // the current water pool.
                    max = height[i];
                    accumulated += current;
                    current = 0;
                } else {
                    
                    // Add water
                    current += max;
                    
                    // Subtrack building
                    current -= min(max, height[i]);
                }
            }
            
            // Last block is not the highest, so need to overflow whatever is left in current.
            if (current && max != height[total_blocks - 1]) {
                int i = total_blocks - 1;
                int min = height[i];
                while (height[i] != max) {
                    if (height[i] > min)
                         min = height[i];
                    // Drain the excess water
                    current -= (max - min);
                    i--;
                }
            }
            
            accumulated += current;
            
            return accumulated;
        }
    };
    

Log in to reply
 

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