LeetCode Q42 Trapping Rain Water

Question:

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.

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!

Solution: O(n) — 8ms space O(n);

Firstly scan the height from right to left get the current points highest number and store it. Then Scan the height from left to right get current point min(left bound, right bound) if the number less than current height means can’t trap the water.**insert 0 to the most left bound and another 0 insert to the most right bound.

class Solution {
public:
    int trap( vector<int>& height ) {
        int n = height.size(), trapWater = 0;
        if ( n > 0 ){
            int left[ n ] = { 0 }, right = 0, water;
            for( int i = n - 2; i >= 0; --i )
                left[ i ] = max( left[ i + 1 ], height[ i + 1 ] );
        
            for( int i = 1; i < height.size(); ++i )
                if (( water = min(left[i], right = max(right, height[i-1])) - height[i]) > 0)
                    trapWater += water;
        }    
        return trapWater;
    }
};