One Pager Cheat Sheet
- By
solving
the Tetris-like problem of determining how much rain a given elevation map with varying bar heights and uniform widths cancollect
, we can calculate a total answer that fits within the Integer range (<2^32
) inO(n)
time andO(1)
space. - We can find the amount of rainwater trapped in an elevation map by determining the maximum water level at each column, which we can find by taking the minimum value of the maximum height in both directions from any given index.
- By using the same process from
right to left
, the two arraysleft[]
andright[]
are generated, which are used to determine the maximum water level at each column. - We can calculate the total amount of water at each column/index directly using the
left[]
andright[]
arrays, and sum them up during the iteration. - The time complexity is
O(n)
, and the space complexity is alsoO(n)
due to the creation of two additional arrays of the same size as the input arrayheight
. - We sum up the
min
of two values calculated fromheights
, while subtractingheights[i]
, andcheck
for corner/simplest cases before returning the result.
This is our final solution.
To visualize the solution and step through the below code, click Visualize the Solution on the right-side menu or the VISUALIZE button in Interactive Mode.
xxxxxxxxxx
62
}
var assert = require('assert');
​
function trappingRainWater(heights) {
let totalArea = 0;
let maxFromLeft = 0;
let maxAreaFromLeft = 0;
​
for (let height of heights) {
totalArea += height;
maxFromLeft = Math.max(maxFromLeft, height);
maxAreaFromLeft += maxFromLeft;
}
​
let maxFromRight = 0;
let maxAreaFromRight = 0;
​
for (let i = heights.length - 1; i >= 0; i--) {
maxFromRight = Math.max(maxFromRight, heights[i]);
maxAreaFromRight += maxFromRight;
}
​
const boundingArea = heights.length * maxFromLeft;
const leftGap = boundingArea - maxAreaFromLeft;
const rightGap = boundingArea - maxAreaFromRight;
return boundingArea - leftGap - rightGap - totalArea;
}
​
try {
assert.equal(
trappingRainWater([0, 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1, 0, 0]),
6
);
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment
That's all we've got! Let's move on to the next tutorial.
If you had any problems with this tutorial, check out the main forum thread here.