Trapping Rain Water

• leetcode 42
• Hard
• Company Tags: Google, Twitter, Zenefits, Amazon, Apple, Bloomberg
• Tags: Array, Stack, Two Pointers
• Similar Problems: Container With Most Water, Product of Array Except Self;

Description

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.

Previous Thinking

Three ways:

• find the largest left and right for each positions.
• find the largest of all.
• Use Stack

C++ Solution

Method 1:

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.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], height[i - 1]);
            max_right[n - 1 - i] = max(max_right[n - i], height[n - i]);
        }

        int sum = 0;

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

        return sum;
    }
};

Method 2:

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();

        int max = 0;
        for(int i = 0; i < n; i++){
            if(height[i] > height[max])
            max = i;
        }

        int sum = 0;
        for(int i = 0, peak = 0; i < max; i++){
            if(height[i] > peak) peak = height[i];
            else sum += peak - height[i];
        }

        for(int i = n - 1, peak = 0; i > max; i--){
            if(height[i] > peak) peak = height[i];
            else sum += peak - height[i];
        }

        return sum;
    }
};

Method 3:

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        stack<pair<int,int>> s;

        int sum = 0;

        for(int i = 0; i < n; i++){
            int base = 0;
            while(!s.empty()){
                int bar = s.top().first;
                int pos = s.top().second;

                sum += (min(bar, height[i]) - base ) * (i - pos - 1);
                base = bar;

                if(height[i] < bar) break;
                else s.pop();
            }
            s.push(make_pair(height[i],i));
        }

        return sum;
    }
};

Java Solution

public class Solution {
    public int trap(int[] height) {
        int n = height.length;

        int[] max_left = new int[n];
        int[] max_right = new int[n];
        int sum = 0;

        for(int i = 1; i < n ;++i){
            max_left[i] = Math.max(max_left[i - 1], height[i - 1]);
            max_right[n - 1 - i] = Math.max(max_right[n - i], height[n - i]);
        }

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

        return sum;
    }
}

public class Solution {
    public int trap(int[] height) {
        int n = height.length;

        int max = 0;
        for(int i = 0; i < n; ++i){
            if(height[i] > height[max])
               max = i;
        }

        int sum = 0;

        for(int i = 0, peak = 0; i < max; i++){
            if(height[i] > peak) peak = height[i];
            else sum += peak - height[i];
        }

        for(int i = n - 1, peak = 0; i > max; i--){
            if(height[i] > peak) peak = height[i];
            else sum += peak - height[i];
        }



        return sum;
    }
}

public class Solution {
    static class Pair{
        int height;
        int pos;

        Pair(int pos, int height){
            this.pos = pos;
            this.height = height;
        }
    }


    public int trap(int[] height) {
        Stack<Pair> s = new Stack<>();
        int n = height.length;

        int sum = 0;

        for(int i = 0; i < n; i++){
            int base = 0;
            while(!s.empty()){
                int bar = s.peek().height;
                int pos = s.peek().pos;

                sum += (Math.min(bar, height[i]) - base) * (i - pos - 1);
                base = bar;

                if(height[i] < bar) break;
                else s.pop();
            }
            s.push(new Pair(i, height[i]));
        }
        return sum;
    }
}

Comment

• Method 1 and Method 2 are similar. And method 2 is lightly faster.
• Method 3 is fantastic. However, it is low efficient using the STL. Especially, I should define the Pair by myself, which made the efficiency even worse.