42. Trapping Rain Water

LeetCode
,

Brute Force

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int trap(int[] height) {
        int n = height.length;
        int total = 0;
        for (int i = 1; i < n - 1; i++) {
            int leftMax = 0, rightMax = 0;

            for (int l = i; l >= 0; l--) leftMax = Math.max(leftMax, height[l]);
            for (int r = i; r < n; r++) rightMax = Math.max(rightMax, height[r]);

            total += Math.min(leftMax, rightMax) - height[i];
        }
        return total;
    }
}

Remarks:

  1. TC: $O(n^2)$, SC: $O(1)$
  2. Cannot pass: out of time

Dynamic Programming

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int trap(int[] height) {
        int n = height.length;
        if (n == 0) return 0;

        int[] leftMax = new int[n];
        int[] rightMax = new int[n];

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

        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        }

        int total = 0;
        for (int i = 0; i < n; i++) {
            total += Math.min(leftMax[i], rightMax[i]) - height[i];
        }

        return total;
    }
}

Remarks:

  1. Key Methodology: for any bar i, vol[i] = min(highest_on_the_left, highest_on_the_right) - height[i].
  2. The highest on the left for i will be max(height[i], highest_on_the_left[i - 1]). Same for the right side.
  3. TC: $O(n)$, SC: $O(n)$

Two Pointers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int trap(int[] height) {
        int n = height.length;
        int left = 0, right = n - 1;
        int leftMax = 0, rightMax = 0;
        int ans = 0;

        while (left <= right) {
            leftMax = Math.max(leftMax, height[left]);
            rightMax = Math.max(rightMax, height[right]);

            if (leftMax < rightMax) {
                ans += leftMax - height[left];
                left++;
            } else {
                ans += rightMax - height[right];
                right--;
            }
        }

        return ans;
    }
}
  1. TC: $O(n)$, SC: $O(1)$
  2. Main idea: if we know the left one is smaller than the right, because the water volume is based on the lower bar, we can simply confirm the volum of the current bar is leftMax - height[left];.