By Long Luo

This article is the solution From Brute Force to DP to Two Pointers with Detail Explaination of Problem 42. Trapping Rain Water.

Intuition

It’s like Leetcode 11. Container With Most Water , we can consider the black block as a wall, the blue block as water. Given an array, each element represents the height of the wall from left to right, find out how many units of water can be held.

The solution can be refered 2 Approaches: BF and Two Pointers with Image Explaination .

1. Brute Force

It’s easy to use the brute force approach. The time complexity is \(O(max^n)\), so it will TLE.

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
27
28
29
30
31
32
33

// Row time: O(max * n) space: O(1)
// TLE
public static int trap_row(int[] height) {
    if (height == null || height.length <= 2) {
        return 0;
    }

    int ans = 0;
    int len = height.length;
    int maxHeight = 0;

    for (int x : height) {
        maxHeight = Math.max(maxHeight, x);
    }

    for (int i = 1; i <= maxHeight; i++) {
        boolean flag = false;
        int water = 0;
        for (int j = 0; j < len; j++) {
            if (flag && height[j] < i) {
                water++;
            }

            if (height[j] >= i) {
                ans += water;
                water = 0;
                flag = true;
            }
        }
    }

    return ans;
}

Analysis

• Time Complexity: \(O(max^n)\)
• Space Complexity: \(O(1)\)

2. Calculate by Column

To find the water in each column, we only need to focus on:

1. Current column;
2. The highest wall on the left;
3. The highest wall on the right.

To find how much water filled, we only need to look at the shorter one of the tallest wall on the left and the tallest wall on the right.

Therefore, according to the height of the shorter wall and the wall of the current column, it can be divided into three cases.

1. \(min(leftMax, rightMax) > current\):

Imagine pouring water between the tallest walls on either side. How much water will the column being asked for?

Obviously, the shorter side, which is the height of the wall on the left, minus the height of the current column, which is \(2 - 1 = 1\), can store one unit of water.

2. \(min(leftMax, rightMax) < current\):

Imagine pouring water between the tallest walls on either side. How much water will the column being asked for?

The column being sought will not have water because it is larger than the lower walls on either side.

3. \(min(leftMax, rightMax) == current\):

As in the previous case, there will be no water.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

// Col time: O(n^2) space: O(1)
public static int trap_col(int[] height) {
    if (height == null || height.length <= 2) {
        return 0;
    }

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

        for (int left = i; left >= 0; left--) {
            maxLeft = Math.max(maxLeft, height[left]);
        }

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

    return ans;
}

Analysis

• Time Complexity: \(O(n^2)\)
• Space Complexity: \(O(1)\)

3. Dynamic Programming

In Approache 2, for each column, we have to traverse all the heights to get the tallest wall on the left and the tallest wall on the right, we can optimize it.

We can use extra space to tradeoff the time complexity.

Use two arrays, \(max_left[i]\) and \(max_right[i]\), which represents the height of the tallest wall on the left or right of column \(i\).

\(max_left[i] = Max(max_left[i-1], height[i-1])\). Choose the higher height on the left side of the wall in front of it and the height of the wall in front of it, which is the highest wall on the left side of the current column.

\(max_right[i] = Max(max_right[i+1],height[i+1])\). The highest height on the right side of the wall behind it and the height of the wall behind it choose a larger one, which is the highest wall on the right side of the current column.

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

// DP time: O(n) space: O(n)
public static int trap_dp(int[] height) {
    if (height == null || height.length <= 2) {
        return 0;
    }

    int ans = 0;
    int len = height.length;
    int[] leftMax = new int[len];
    int[] rightMax = new int[len];
    for (int i = 1; i < len - 1; i++) {
        leftMax[i] = Math.max(leftMax[i - 1], height[i - 1]);
    }

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

    for (int i = 1; i < len - 1; i++) {
        int min = Math.min(leftMax[i], rightMax[i]);
        ans += min > height[i] ? min - height[i] : 0;
    }

    return ans;
}

Analysis

• Time Complexity: \(O(n)\)
• Space Complexity: \(O(n)\)

4. Two Pointers

In DP Approach, we can often optimize the space complexity.

We can see that the elements in the \(max_left[i]\) and \(max_right[i]\) arrays are actually only used once, and then never used again. So we can use just use one element instead of an array.

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

// Two Pointers time: O(n) space: O(1)
public static int trap_tp_opt(int[] height) {
    if (height == null || height.length <= 2) {
        return 0;
    }

    int len = height.length;
    int ans = 0;
    int left = 0;
    int right = len - 1;
    int leftMax = height[0];
    int rightMax = height[right];
    while (left < right) {
        if (height[left] < height[right]) {
            leftMax = Math.max(leftMax, height[left]);
            ans += leftMax - height[left];
            left++;
        } else {
            rightMax = Math.max(rightMax, height[right]);
            ans += rightMax - height[right];
            right--;
        }
    }

    return ans;
}

Analysis

• Time Complexity: \(O(n)\)
• Space Complexity: \(O(1)\)

All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗