0042. Trapping Rain Water

https://leetcode.com/problems/trapping-rain-water

Description

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Example 1:

**Input:** height = [0,1,0,2,1,0,1,3,2,1,2,1]
**Output:** 6
**Explanation:** The above elevation map (black section) 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.

Example 2:

**Input:** height = [4,2,0,3,2,5]
**Output:** 9

Constraints:

• n == height.length

• 1 <= n <= 2 * 104

• 0 <= height[i] <= 105

ac1: two pointers

https://leetcode.com/problems/trapping-rain-water/discuss/17357/Sharing-my-simple-c%2B%2B-code%3A-O(n)-time-O(1)-space

class Solution {
    public int trap(int[] height) {
        int res = 0;
        int leftMax = 0, rightMax = 0, left = 0, right = height.length - 1;
        
        while (left <= right) {
            if (leftMax < rightMax) {
                if (height[left] >= leftMax) {
                    leftMax = height[left];
                } else {
                    res += leftMax - height[left];
                }
                left++;
            } else {
                if (height[right] >= rightMax) {
                    rightMax = height[right];
                } else {
                    res += rightMax - height[right];
                } 
                right--;
            }
        }
        
        return res;
    }
}

ac2: brute force

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        // edge cases
        if (n < 3) return 0;

        int water = 0;
        // 1st pass walk through, 2nd pass find left max, 3rd pass find right max
        for (int i = 0; i < n; i++) {
            // find left max
            int lmax = 0;
            for (int l = 0; l <= i; l++) {
                lmax = Math.max(lmax, height[l]);
            }
            // find right max
            int rmax = 0;
            for (int r = n-1; r >= i; r--) {
                rmax = Math.max(rmax, height[r]);
            }
            // calculate water volumn
            water += Math.min(rmax, lmax) - height[i];
        }

        // result
        return water;
    }
}

/*
brute force, O(n2) time + O(1) space
DP-like memorization + 3 pass, O(3n) time + O(2n) space
stack + 1 pass, O(n) time + O(n) space
two pointers + 1 pass, O(n) time + O(1) space
*/

ac3: DP-like memorization

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        // edge cases
        if (n < 3) return 0;

        int[] lmax = new int[n];
        int[] rmax = new int[n];
        lmax[0] = height[0];
        rmax[n-1] = height[n-1];

        // find left max
        for (int i = 1; i < n; i++) {
            lmax[i] = Math.max(lmax[i-1], height[i]);
        }
        // find right max
        for (int i = n - 2; i >= 0; i--) {
            rmax[i] = Math.max(rmax[i+1], height[i]);
        }

        // accumulate water
        int water = 0;
        for (int i = 0; i < n; i++) {
            water += Math.min(lmax[i], rmax[i]) - height[i];
        }

        // result
        return water;
    }
}

ac4: stack

Very hard to understand, doubt if it's suitable for interview. https://leetcode.com/problems/trapping-rain-water/discuss/17414/A-stack-based-solution-for-reference-inspired-by-Histogram

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        int water = 0;
        // edge cases
        if (n < 3) return 0;

        // stack 
        Stack<Integer> stack = new Stack<Integer>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                int bottom = height[stack.pop()];
                if (stack.isEmpty()) break;
                int length = i - stack.peek() - 1;
                int h = Math.min(height[i], height[stack.peek()]) - bottom;
                water += length * h;
            }
            stack.push(i);
        }

        // result
        return water;
    }
}