leetcode-42

42. Trapping Rain Water

Leetcode 42

I solved this problem using C++.
My initial idea: use for loop to find the maximum height of the left and right sides.

However, this solution is not efficient enough.
Then I use dynamic programming to solve this problem.

set leftMax[i] as the maximum height of the left side of height[i] not including height[i]
set rightMax[i] as the maximum height of the right side of height[i] not including height[i]

Then I can find the minimum height of the left and right sides of height[i] and subtract height[i] from it.
leftMax[i] equals to the maximum height of height[i-1] and leftMax[i-1]
rightMax[i] equals to the maximum height of height[i+1] and rightMax[i+1]

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
class Solution
{
public:
    int trap(vector<int> &height)
    {
        int result = 0;
        vector<int> leftMax(height.size(), 0);
        vector<int> rightMax(height.size(), 0);
        for (int i = 1; i < height.size(); i++)
        {
            leftMax[i] = max(leftMax[i - 1], height[i - 1]);
        }
        for (int i = height.size() - 2; i >= 0; i--)
        {
            rightMax[i] = max(rightMax[i + 1], height[i + 1]);
        }
        for (int i = 0; i < height.size(); i++)
        {
            int minHeight = min(leftMax[i], rightMax[i]);
            if (minHeight > height[i])
            {
                result += minHeight - height[i];
            }
        }
        return result;
    }
};

This solution is O(n) in time complexity and O(n) in space complexity.

Then I use two pointers to solve this problem.
This solution is more efficient than the previous one.
The idea is to use two pointers to maintain the maximum height of the left and right sides of height[i].
The left pointer starts from the left side of the array and the right pointer starts from the right side of the array.
The maximum height of the left side is maxL and the maximum height of the right side is maxR.

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(vector<int> &height)
    {
        int result = 0;
        int lt = 0, rt = height.size() - 1;
        int maxL = height[lt], maxR = height[rt];
        while (lt < rt)
        {
            maxL = max(maxL, height[lt]);
            maxR = max(maxR, height[rt]);
            if (maxL <= maxR)
            {
                result += maxL - height[lt];
                lt++;
            }
            else
            {
                result += maxR - height[rt];
                rt--;
            }
        }
        return result;
    }
};

e.g.
height = [4, 2, 0, 3, 2, 5]
Output: 9

  1. set lt = 0, rt = 5, result = 0, maxL = 4, maxR = 5
  2. maxL = max(4, 4), maxR = max(5, 5)
  3. maxL <= maxR, so result = 0 + 4 - 4 = 0, lt = 1
  4. maxL = max(4, 2), maxR = max(5, 5)
  5. maxL <= maxR, so result = 0 + 4 - 2 = 2, lt = 2
  6. maxL = max(4, 0), maxR = max(5, 5)
  7. maxL <= maxR, so result = 2 + 4 - 0 = 6, lt = 3
  8. maxL = max(4, 3), maxR = max(5, 5)
  9. maxL <= maxR, so result = 6 + 4 - 3 = 7, lt = 4
  10. maxL = max(4, 2), maxR = max(5, 5)
  11. maxL <= maxR, so result = 7 + 4 - 2 = 9, lt = 5
  12. lt = 5, rt = 5, so the loop ends

This solution is O(n) in time complexity and O(1) in space complexity.

The main idea to solve this problem is to find the maximum height of the left and right sides of height[i] and subtract height[i] from it.

conclusion

It’s a good problem to practice dynamic programming and two pointers.
It’s hard and always asked in interviews.😥😒