8000 42 Trapping Rain Water · malipramod/leetcode-js@abdef73 · GitHub
[go: up one dir, main page]
Skip to content

Commit abdef73

Browse files
malipramodmalipramod
committed
42 Trapping Rain Water
1 parent 01cf85e commit abdef73

File tree

2 files changed

+84
-0
lines changed

2 files changed

+84
-0
lines changed

‎hard/0042 trapping-rain-water/readme.md

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
# Trapping Rain Water
2+
3+
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.
4+
5+
## Example
6+
7+
Input: [0,1,0,2,1,0,1,3,2,1,2,1]
8+
9+
Output: 6
10+
11+
## More Info
12+
13+
<https://leetcode.com/problems/trapping-rain-water/>

‎hard/0042 trapping-rain-water/trapping-rain-water.js

Lines changed: 71 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,71 @@
1+
/**
2+
* Brute force
3+
* @param {number[]} height
4+
* @return {number}
5+
*/
6+
var trapBF = function (height) {
7+
let result = 0;
8+
for (let i = 1; i < height.length - 1; i++) {
9+
let leftMax = 0, rightMax = 0;
10+
for (let j = i; j >= 0; j--)
11+
leftMax = Math.max(leftMax, height[j]);
12+
13+
for (let j = i; j < height.length; j++)
14+
rightMax = Math.max(rightMax, height[j])
15+
16+
result += Math.min(leftMax, rightMax) - height[i];
17+
}
18+
return result;
19+
};
20+
21+
/**
22+
* Dynamic Programming
23+
* @param {number[]} height
24+
* @return {number}
25+
*/
26+
var trapDP = function (height) {
27+
let result = 0;
28+
let n = height.length;
29+
let leftMax = [], rightMax =[];
30+
31+
leftMax[0] = height[0];
32+
rightMax[n - 1] = height[n - 1];
33+
34+
for (let i = 1; i < n - 1; i++) {
35+
leftMax[i] = Math.max(leftMax[i-1], height[i]);
36+
}
37+
38+
for (let i = n - 2; i >= 0; i--) {
39+
rightMax[i] = Math.max(rightMax[i + 1], height[i]);
40+
}
41+
42+
for (let i = 1; i < n - 1; i++) {
43+
result += Math.min(leftMax[i], rightMax[i]) - height[i];
44+
}
45+
return result;
46+
}
47+
48+
/**
49+
* Two Pointer
50+
* @param {number[]} height
51+
* @return {number}
52+
*/
53+
var trap = function (height) {
54+
let left = 0, right = height.length - 1;
55+
let leftMax=0,rightMax=0;
56+
let result = 0;
57+
58+
while (left < right) {
59+
if (height[left] < height[right]) {
60+
height[left] >= leftMax ? (leftMax = height[left]) : result += (leftMax - height[left]);
61+
left++;
62+
}else{
63+
height[right] >= rightMax ? (rightMax = height[right]) : result += (rightMax - height[right]);
64+
right--;
65+
}
66+
}
67+
return result;
68+
}
69+
70+
console.log(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))
71+
console.log(trap([1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]))

0 commit comments

Comments
 (0)
0