forked from mberktas/javascript-algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
/
bfRainTerraces.js
33 lines (29 loc) · 1.18 KB
/
bfRainTerraces.js
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
/**
* BRUTE FORCE approach of solving Trapping Rain Water problem.
*
* @param {number[]} terraces
* @return {number}
*/
export default function bfRainTerraces(terraces) {
let waterAmount = 0;
for (let terraceIndex = 0; terraceIndex < terraces.length; terraceIndex += 1) {
// Get left most high terrace.
let leftHighestLevel = 0;
for (let leftIndex = terraceIndex - 1; leftIndex >= 0; leftIndex -= 1) {
leftHighestLevel = Math.max(leftHighestLevel, terraces[leftIndex]);
}
// Get right most high terrace.
let rightHighestLevel = 0;
for (let rightIndex = terraceIndex + 1; rightIndex < terraces.length; rightIndex += 1) {
rightHighestLevel = Math.max(rightHighestLevel, terraces[rightIndex]);
}
// Add current terrace water amount.
const terraceBoundaryLevel = Math.min(leftHighestLevel, rightHighestLevel);
if (terraceBoundaryLevel > terraces[terraceIndex]) {
// Terrace will be able to store the water if the lowest of two left and right highest
// terraces are still higher than the current one.
waterAmount += Math.min(leftHighestLevel, rightHighestLevel) - terraces[terraceIndex];
}
}
return waterAmount;
}