rain-water-collector.md

Prompt: Rain Water Collector

You're an industrious programmer that lives off the grid. The local well that you use to fetch water has gone dry, so you've decided to collect rain water. Unfortunately, your collection device isn't flat.

Given n non-negative integers in an array representing an elevation map, compute how much rain water your collection device can hold. The width of each bar is 1.

Example

Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

Visual Representation of the above array:

Here are some samples to test to be sure the function works. It is helpful to draw them out then walk step-by-step through the solution to help visualize it.

const a = [0,0,1,2,4,3,2,5,0,0,2,1];
// vol = 7

const b = [0,1,0,2,1,0,1,3,2,1,2,1];
// vol = 6

const c =[0,3,0,1,0,0,0,1,0,2];
// vol = 12
 
const d = [0,1,0,3,5,0,0,0,2,0,1];
// vol = 8

const e = [0,5,3,2,8,8,1,1,2,4,3,3,7,1,2,4,3,2];
// vol = 38

Solutions

Basic Approach:

Water will only gather up to the height of its reservoir walls. Therefore we should think about this problem in terms of height. Think about how much water can exist in a horizontal plane at each level.

The solution below goes about this by starting at the highest 'peak' and and summing the total amount of volume at that level then decrementing the height by one and repeating the process until a height of 0 is reached. This produces an O(n*a) solution (n is the size of the array, a is the maximum number in the array).

/* the 'totalVol' function will find the highest point, then sum the volume
at each subsequent level */
   
function totalVol (blocks) {
  // Retrieve the highest number in the array
  const peak = Math.max(...blocks);
  let vol = 0;
  for (let height = peak; height > 0; height--) {
    // 'peakIndicesMaker' returns an array indicating where walls exist 
    // at a given 'level' (e.g. height)
    const peaksAtHeightLevel = peakIndicesMaker(blocks, height);    
    // vol is incremented by the available volume at that level
    vol += volAtLevel(peaksAtHeightLevel);
  }
  return vol;
}


function peakIndicesMaker (blocks, level) { // ([0,0,1,2,4,3,2,5,0,0,2,1], 5)
  const peakIndices = [];
  for (let i = 0; i < blocks.length; i++) {
    // if the wall height present at each index of original array is at least
    // the height of the given level, then that index is pushed to the returned array
    if(blocks[i] >= level) {
      peakIndices.push(i);
    }
  }
  return peakIndices;
}


function volAtLevel(peakIndices) { // [7] then [4,7] then [4,5,7]...
  let levelVol = 0;
  // if there is only one wall there cannot physically be any water at that level
  if (peakIndices.length === 1) {
    return 0;
  } else {
    // levelVol is incremented for each 'set' of walls that can hold water at a given level/height
    for (let i = 0; i < (peakIndices.length - 1); i++) {
      // We need to measure from the right side of one wall to the left side of the other
      // This also ensures that nothing is added for adjacent walls
      levelVol += (peakIndices[i + 1] - (peakIndices[i] + 1));
    };
  }
  return levelVol
}

Recursive Basic Approach:

We could refactor the same approach to more succinct recursive solution like so:

function rainCollector (blocks, level = Math.max(...blocks)) {
  if (level < 1) return 0;
  let prevMatch;
  const atThisLevel = blocks.reduce((collected, block, idx) => {
    if (block < level) return collected;
    if (prevMatch) collected += idx - prevMatch - 1;
    prevMatch = idx;
    return collected;
  }, 0);
  return atThisLevel + rainCollector(blocks, level - 1);
}

Optimized Approach (look @ neighbors):

We can do even better — we can get this down to O(n) time. Look at each block's largest leftwards neighbor, and its largest rightwards neighbor. Each block has these "bounding walls". The water above each block will be the vertical distance between it and the smaller of these bounding walls.

So here's the implementation outline: run through the array of blocks in order to keep track of each block's largest leftwards neighbor, and we can run through them in reverse to determine each block's largest rightwards neighbor. Then we can do one final loop, where we determine the water above each block by getting the difference between the block and the smaller of its two bounding (higher) walls.

function rainCollector (blocks) {
  const rightMaxes = [];
  let rightMax = 0;
  for (let i = blocks.length - 1; i >= 0; i--) {
    rightMax = Math.max(rightMax, blocks[i]);
    rightMaxes[i] = rightMax;
  }
  
  const leftMaxes = [];
  let leftMax = 0;
  for (let i = 0; i < blocks.length; i++) {
    leftMax = Math.max(leftMax, blocks[i]);
    leftMaxes[i] = leftMax;
  }

  return blocks.reduce((waterCollected, block, idx) => {
    const leftMax = leftMaxes[idx];
    const rightMax = rightMaxes[idx];
    return waterCollected + Math.min(leftMax, rightMax) - block;
  }, 0);
}

Simplified Optimized Approach:

We can simplify the above solution by merging the last two loops together. While keeping track of the leftwards maximum for any given block, we can also be calculating the water above it. There's no need to do these two things in separate loops:

function rainCollector (blocks) {
  const rightMaxes = [];
  let rightMax = 0;
  for (let i = blocks.length - 1; i >= 0; i--) {
    rightMax = Math.max(rightMax, blocks[i]);
    rightMaxes[i] = rightMax;
  }
  
  let waterCollected = 0;
  let leftMax = 0;
  for (let i = 0; i < blocks.length; i++) {
    leftMax = Math.max(leftMax, blocks[i]);
    const rightMax = rightMaxes[i];
    waterCollected += Math.min(leftMax, rightMax) - blocks[i];
  }
  
  return waterCollected;
}