42Trapping Rain Water

Solution 1: Brute Force

O(N^2)

class Solution {
    public int trap(int[] height) {
        int ans =  0;
        int n = height.length;
        for(int i = 1;  i< (n-1); i++){
            int maxLeft = 0;
            int maxRight = 0;
            for(int j = i-1; j>=0; j--){
                maxLeft = Math.max(maxLeft, height[j]);
            }
            for(int j = i+1; j<n; j++){
                maxRight = Math.max(maxRight, height[j]);
            }

            ans += Math.max(0, Math.min(maxLeft, maxRight) - height[i]);
        }
        return ans;
    }
}

Solution 2: DP

O(N)

class Solution {
    public int trap(int[] height) {
        int ans =  0;
        int n = height.length;
        int[] maxLeft = new int[n];
        int[] maxRight = new int[n];
        for(int i = 1; i < n;  i++){
            maxLeft[i] = Math.max(height[i-1], maxLeft[i-1]);
        }
        for(int i = n-2; i >= 0; i--){
            maxRight[i] = Math.max(height[i+1], maxRight[i+1]);
        }

        for(int i = 1;  i< (n-1); i++){
            ans += Math.max(0, Math.min(maxLeft[i], maxRight[i]) - height[i]);
        }
        return ans;
    }
}

Solution 3: Stack O(N)

class Solution {
    public int trap(int[] height) {
        Stack<Integer> stack = new Stack();
        int ans = 0;
        int i = 0;
        while(i < height.length){
            if(stack.empty() || height[i] <= height[stack.peek()]){
                stack.push(i);
                i++;
            }
            else{
                int bottom = stack.pop();
                int maxBottomWater;
                if(stack.empty()){
                    maxBottomWater = 0;
                }
                else{
                    maxBottomWater = (Math.min(height[stack.peek()], height[i]) - height[bottom]) * (i - stack.peek() - 1);
                }
                ans += maxBottomWater;
            }
        }
        return ans;
    }
}

Solution 4: Two Pointers O(N)

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        int left = 0; 
        int right = n - 1;
        int ans = 0;
        int maxLeft = 0;
        int maxRight = 0;
        while(left <= right){
            maxLeft = Math.max(maxLeft, height[left]);
            maxRight = Math.max(maxRight, height[right]);
            if(maxLeft < maxRight){
                ans += (maxLeft - height[left]);
                left++;
            }
            else{
                ans += (maxRight - height[right]);
                right--;
            }

        }
        return ans;
    }
}