rain-water-collector.md

Rain Water Collector 🌧⛈

---

Prompt

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 to fill it; however, your collection device isn't flat.

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water your collection device is able to trap after raining occurs.

Example

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

Visual Representation of above:

// vol = 4
const a = [0,2,1,4,3,2,5,1]
console.log('collection device "a" can hold', totalVol(a));
 
// vol = 6
const b = [0,1,0,2,1,0,1,3,2,1,2,1];
console.log('collection device "b" can hold', totalVol(b));
 
// vol = 12
const c =[0,3,0,1,0,0,0,1,0,2];
console.log('collection device "c" can hold', totalVol(c));
 
// vol = 8
const d = [0,1,0,3,5,0,0,0,2,0,1];
console.log('collection device "d" can hold', totalVol(d));
 
// vol = 38
const e = [0,5,3,2,8,8,1,1,2,4,3,3,7,1,2,4,3,2];
console.log('collection device "e" can hold', totalVol(e));

What to do with the interviewee:

• It is okay for you to try to get your interviewee to try to explain the logic of this problem. They can walk through it conceptually and/or attempt to psuedo code if they are having trouble with the implementation.
• You should be providing the initial diagram for reference (screen shot or double click the image and share the url).
• You can also try providing the examples above (without the output) and ask them to figure out what the total volume will be and why. (Water will only gather up to the height of its reservoir walls - therefore think about this problem in terms of height.)
• Ask them about the beginning and end of the array? What values should be used to represent them? Why is it important? (Water cannot be held in the first or last bar, due to no "containing" wall on either side.)
• If they still seem stuck take the samples provided to test the function and ask them to draw them out. It can help them visualize a solution.

Hints to provide an interviewee that is attempting implementation:

• It should be clear that the input array is an elevation map and the output array is the total units of water that are contained.

• In order to calculate the amount of water above a single point in the array, the interviewee should know the height of the tallest pillars to its left and the height to the tallest pillars to its right.

• If a value can hold water above it, then the smallest of the two heights (leftMax and rightMax) should lead them to the correct amount of water.

---

Solution 1 (dynamic programming)

Remember 👀 Dynamic programming breaks down the problem into smaller and smaller possible sub-problems. These sub-problems are not solved independently. The results of these smaller sub-problems are remembered and used for overlapping or so that the results can be reused.

function totalVol (blocks) {

// initialize an array to keep track of all of tallest pillars starting from the beginning of the array 
  const leftMaxes = [];

//keep track of the previous height of the value to the left
  let leftMax = 0;

  for (let i = 0; i < blocks.length; i++) {
// update the tallest value of the as we continue incrementing through the elements
//if the next block is higher replace that block, if not keep the current value 
    leftMax = Math.max(leftMax, blocks[i]);
//add that value to our array - the one that is keeping track out how high the blocks are as we increment 
    leftMaxes[i] = leftMax;
  }

// initialize an array to keep track of all of tallest pillars starting from the end of the array and decrement towards the front
	const rightMaxes = [];

//keep track of the previous height of the value to the left
  let rightMax = 0;

  for (let i = blocks.length - 1; i >= 0; i--) {
// update the tallest value of the as we continue decrementing through the elements towards the first element
//if the next block is higher replace that block, if not keep the current value 
    rightMax = Math.max(rightMax, blocks[i]);

//add that value to our array - the one that is keeping track out how high the blocks are as we decrement  
    rightMaxes[i] = rightMax;
  }

// *** reduce refresher 
// waterCollected is the initial value 
// block is the current value we are checking 
// idx is the index of the current element in the blocks array 
  return blocks.reduce((waterCollected, block, idx) => {
    const leftMax = leftMaxes[idx]; // assigning the leftMax to the highest value we found at thet index 
    const rightMax = rightMaxes[idx]; // repeating for the right side

    return waterCollected + Math.min(leftMax, rightMax) - block;
  }, 0); 
  // returning the minimum of the two values we are comparing to see if there is any remaining height on that block
  // if we have any remaining height that will be the amount of water that is "trapped" or contained 
  // set the initial value to zero if we are not able to collect any water 
}

Big 0

• O(n) time and 0(n) space

Visual for interviewer ↓:

---

Solution 2 (pointers - will not be reviewed, just for reference)

const totalVol = (height) => {  //height is list of how tall each pillar is 

    //think of pointers
    let leftIdx = 0;
    let rightIdx = height.length - 1;
    let leftMax = 0;
    let rightMax = 0;
    let water = 0;

    //while the left pointer and the right pointer do not pass eachother check the following 
    while (leftIdx <= rightIdx) {
        //if the the height at this postion is greater than the current tallest pillar to the left 
        if(height[leftIdx] > leftMax){
         //the tallest pillar to the left is now the pillar at this postion
         leftMax =  height[leftIdx]
        }
        //if the the height at this postion is  greater than the current tallest pillar to the right
        if(height[rightIdx] > rightMax){
         //the tallest pillar to the right is now the pillar at this postion
          rightMax = height[rightIdx]
        }
        // if the pillar on the right is taller than the pillar on the left
        if (leftMax > rightMax) {
           //minus the current idx value from the tallest pillar
           // add the sum to the water
            water += (rightMax - height[rightIdx]);
            // then decrement the current right idx
            rightIdx--
        }
        else {
            //the left pillar is the tallest pillar
            //minus the current idx value on the left from the tallest pillar
           // add the sum to the water
            water += (leftMax - height[leftIdx]);
            //increment
            leftIdx++
        }
    }
    // return the collected water 
    return water 
};

Big 0

• O(n) time and 0(1) space

---

Try me out yourself 💻:

https://repl.it/@kyvyCodes/trapping-rain-water