Clean Intuitive O(n) and O(1) space Two Pass Solution


  • 0
    J

    The idea is to keep track of the index (curr_max) of the largest element up to a certain index (i) and if height[i] > height[curr_max] then you add height[curr_max] multiplied by the width of the bar (curr_max to i) minus all the sum of all the elements in between.

    You would have to do this reverse as well to consider both cases.

    class Solution {
    public:
        int trap(vector<int>& height) {
            int len = height.size();
    
            int temp = 0;
            int res = 0;
            int curr_max = 0;
            for(int i = 1; i < len; i++) {
                if(height[i] >= height[curr_max]) {
                    res += (i - curr_max - 1)*height[curr_max] - temp;
                    curr_max = i;
                    temp = 0;
                } else {
                    temp += height[i];
                }
            }
            temp = 0;
            curr_max = len - 1;
            for(int i = len - 2; i >= 0; i--) {
                if(height[i] > height[curr_max]) {
                    res += (curr_max - i - 1)*height[curr_max] - temp;
                    curr_max = i;
                    temp = 0;
                } else {
                    temp += height[i];
                }
            }
    
            return res;
        }
    };
    

Log in to reply
 

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