42.trapping-rain-water.en.md

Trapping Rain Water

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

Problem Description

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

The above elevation map 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. Thanks Marcos for contributing this image!

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

Prerequisites

• Space-time tradeoff
• Two Pointers
• Monotonic Stack

Two Arrays

Solution

The difficulty of this problem is hard. We'd like to compute how much water a given elevation map can trap.

A brute force solution would be adding up the maximum level of water that each element of the map can trap.

Pseudo Code:

for (let i = 0; i < height.length; i++) {
  area += h[i] - height[i]; // the maximum level of water that the element i can trap
}

Now the problem becomes how to calculating h[i], which is in fact the minimum of maximum height of bars on both sides minus height[i]: h[i] = Math.min(leftMax, rightMax) where leftMax = Math.max(leftMax[i-1], height[i]) and rightMax = Math.max(rightMax[i+1], height[i]).

For the given example, h would be [0, 1, 1, 2, 2, 2 ,2, 3, 2, 2, 2, 1].

The key is to calculate leftMax and rightMax.

Key Points

• Figure out the modeling of h[i] = Math.min(leftMax, rightMax)

Code (JavaScript/Python3/C++)

JavaScript Code:

/*
 * @lc app=leetcode id=42 lang=javascript
 *
 * [42] Trapping Rain Water
 *
 */
/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function (height) {
  let max = 0;
  let volume = 0;
  const leftMax = [];
  const rightMax = [];

  for (let i = 0; i < height.length; i++) {
    leftMax[i] = max = Math.max(height[i], max);
  }

  max = 0;

  for (let i = height.length - 1; i >= 0; i--) {
    rightMax[i] = max = Math.max(height[i], max);
  }

  for (let i = 0; i < height.length; i++) {
    volume = volume + Math.min(leftMax[i], rightMax[i]) - height[i];
  }

  return volume;
};

Python Code:

class Solution:
    def trap(self, heights: List[int]) -> int:
        n = len(heights)
        l, r = [0] * (n + 1), [0] * (n + 1)
        ans = 0
        for i in range(1, len(heights) + 1):
            l[i] = max(l[i - 1], heights[i - 1])
        for i in range(len(heights) - 1, 0, -1):
            r[i] = max(r[i + 1], heights[i])
        for i in range(len(heights)):
            ans += max(0, min(l[i + 1], r[i]) - heights[i])
        return ans

C++ code:

int trap(vector<int>& heights)
{
	if(heights == null)
		return 0;
    int ans = 0;
    int size = heights.size();
    vector<int> left_max(size), right_max(size);
    left_max[0] = heights[0];
    for (int i = 1; i < size; i++) {
        left_max[i] = max(heights[i], left_max[i - 1]);
    }
    right_max[size - 1] = heights[size - 1];
    for (int i = size - 2; i >= 0; i--) {
        right_max[i] = max(heights[i], right_max[i + 1]);
    }
    for (int i = 1; i < size - 1; i++) {
        ans += min(left_max[i], right_max[i]) - heights[i];
    }
    return ans;
}

Complexity Analysis

• Time Complexity: $O(N)$
• Space Complexity: $O(N)$

Two Pointers

Solution

The above code is easy to understand, but it needs the extra space of N. We can tell from it that we in fact only cares about the minimum of (left[i], right[i]). Specifically:

• If l[i + 1] < r[i], the maximum in the left side of i will determine the height of trapping water.
• If l[i + 1] >= r[i], the maximum in the right side of i will determine the height of trapping water.

Thus, we don't need to keep two complete arrays. We can rather keep only a left max and a right max, using constant variable. This problem is a typical two pointers problem.

Algorithm:

1. Initialize two pointers left and right, pointing to the begin and the end of our height array respectively.
2. Initialize the left maximum height and the right maximum height to be 0.
3. Compare height[left] and height[right]

• If height[left] < height[right]
  • 3.1.1 If height[left] >= left_max, the current trapping volume is (left_max - height[left])
  • 3.1.2 Otherwise, no water is trapped and the volume is 0
• 3.2 Iterate the left pointer to the right
• 3.3 If height[left] >= height[right]
  • 3.3.1 If height[right] >= right_max, the current trapping volume is (right_max - height[right])
  • 3.3.2 Otherwise, no water is trapped and the volume is 0
• 3.4 Iterate the right pointer to the left

Code (Python3/C++)

class Solution:
    def trap(self, heights: List[int]) -> int:
        n = len(heights)
        l_max = r_max = 0
        l, r = 0, n - 1
        ans = 0
        while l < r:
            if heights[l] < heights[r]:
                if heights[l] < l_max:
                    ans += l_max - heights[l]
                else:
                    l_max = heights[l]
                l += 1
            else:
                if heights[r] < r_max:
                    ans += r_max - heights[r]
                else:
                    r_max = heights[r]
                r -= 1
        return ans

class Solution {
public:
    int trap(vector<int>& heights)
{
    int left = 0, right = heights.size() - 1;
    int ans = 0;
    int left_max = 0, right_max = 0;
    while (left < right) {
        if (heights[left] < heights[right]) {
            heights[left] >= left_max ? (left_max = heights[left]) : ans += (left_max - heights[left]);
            ++left;
        }
        else {
            heights[right] >= right_max ? (right_max = heights[right]) : ans += (right_max - heights[right]);
            --right;
        }
    }
    return ans;
}

};

Complexity Analysis

• Time Complexity: $O(N)$
• Space Complexity: $O(1)$

Similar Problems

• 84.largest-rectangle-in-histogram

For more solutions, visit my LeetCode Solution Repo (which has 30K stars).

Follow my WeChat official account 力扣加加, which has lots of graphic solutions and teaches you how to recognize problem patterns to solve problems with efficiency.