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 can collect, we can calculate a total answer that fits within the Integer range (< 2^32) in O(n) time and O(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 arrays left[] and right[] 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[] and right[] arrays, and sum them up during the iteration.
• The time complexity is O(n), and the space complexity is also O(n) due to the creation of two additional arrays of the same size as the input array height.
• We sum up the min of two values calculated from heights, while subtracting heights[i], and check 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

}

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

  );

Alright, well done! Try another walk-through.

If you had any problems with this tutorial, check out the main forum thread here.