Skip to content

Latest commit

 

History

History
executable file
·
130 lines (101 loc) · 3.53 KB

42.trapping-rain-water.en.md

File metadata and controls

executable file
·
130 lines (101 loc) · 3.53 KB

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.

42.trapping-rain-water-1

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

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 volumn = 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++) {
        volumn = volumn +  Math.min(leftMax[i], rightMax[i]) - height[i]
    }

    return volumn;
};

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:

class Solution {
public:
    int trap(vector<int>& height) {
        //check for empty input array
        if(height.empty())
            return 0;
        int size = height.size();
        int leftMax[size], rightMax[size];
        //initialization
        leftMax[0] = height[0];
        rightMax[size - 1] = height[size - 1];
        //find leftMax for each element i
        for(int i = 1; i < size; ++i)
            leftMax[i] = max(leftMax[i-1], height[i]);
        //find rightMax for each element i
        for(int i = size - 2; i >= 0; --i)
            rightMax[i] = max(rightMax[i+1], height[i]);
        //caculating the result
        int ans = 0;
        for(int i = 0; i < size; ++i)
            ans += min(leftMax[i], rightMax[i]) - height[i];
        return ans;
    }
};

Similar Problems