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 filter; 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.
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
Visual Representation of above:
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.
// vol = 7
const a = [0,0,1,2,4,3,2,5,0,0,2,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));- This is one case where you should consider drawing the diagram out for your partner. Not having the visual aid for this problem can be a huge blocker. You can draw out a smaller version of the above example if you wish.
- Most candidates will likely see the sum by height solution first.
- Try to let them come to the conclusion that they want to sum the height at each level, or guide them to that if needed.
- Then see if they can see the relationship between using the indices to find the amount of water at each level.
- It might be helpful to have them think in terms what each helper function below does to turn their thought processes into code.
- Some advice for guiding candidates through the
O(n)solution where they scan the array once forward and backward:- See if they can identify the 3 attributes that can affect the amount of water collected at any index.
- Max height to its left, max height to the right, and its own wall height
- It might help to ask leading questions like -- "What if I change the wall height here? How much more/less water do I collect?"
- See if they can identify the 3 attributes that can affect the amount of water collected at any index.
- If a candidate finishes and has not implemented the optimal
O(n)solution, see if they can identify what 3 attributes contribute to the height of the water at each index and have them talk through that, even if they don't have time to implement the full solution.
Before we begin to sum the total water volume of the collector, it is important to use our understanding of water itself. Water will only gather up to the height of its reservoir walls. Therefore we should think about this problem in terms of height. Initially one might attempt to loop through the array and try to sum the volumes of the vertical columns of water. This approach quickly breaks down whenever the complexity of calculating the size of each reservoir is encountered.
Time Complexity: O(n*a)
Instead of summing the volume vertically we will think about how much volume exists in a horizontal plane at each incremental height. 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). See individual comments to better understand the solution.
Our totalVol function is our main aggregator function. It will find the 'peak' (max height) of the collection array, then sum the volume at each subsequent level until the 'ground' (height of 0) is reached. We use two helper functions here:
peakIndicesMaker, which takes our blocks and the current height in our loop and returns an array of indices of reservoir walls that exist at that levelvolAtLevel, which takes the array of indices returned frompeakIndicesMakerand returns an integer representing the amount of water at the current height/level
function totalVol (blocks) {
// 'peak' is set to the return of Math.max() when it is applied to the array
const peak = Math.max(...blocks);
let vol = 0;
// this loop starts at the 'peak' height and iterates on each height until we reach 0
for (let height = peak; height > 0; height--) {
const peaksAtHeightLevel = peakIndicesMaker(blocks, height);
vol += volAtLevel(peaksAtHeightLevel);
}
// total volume is returned
return vol;
}As demonstrated above, peakIndicesMaker takes the original array as well as the height level and returns an array of indices where reservoir walls exist
function peakIndicesMaker (blocks, level) {
const peakIndices = [];
// Loop through the array to evaluate the height of the wall at each index
// If the wall height present at each index is at least the height of the given level,
// then that index is pushed to the output array
for (let i = 0; i < blocks.length; i++) {
if(blocks[i] >= level) {
peakIndices.push(i);
}
}
return peakIndices;
}volAtLevel takes care of the meat of the calculation for this problem. The key point to understand is that the distance betwee the two walls at the same height will also be the volume of water held between them. A corollary to that is if two walls of at least the same height are adjacent to one another, then it is not possible for water to be present.
Additionally, while you could also pre-emptively check to see if there is more than one index in the peakIndices array before evaluating your loop--logically, you can't trap water with a single wall!--notice that the way your for-loop is instantiated takes care of that for you.
function volAtLevel(peakIndices) {
let levelVol = 0;
// Because we are comparing adjacent indices, we stop the loop before we reach peakIndices.length - 1
// The last element in the array could not possibly hold water to its right
for (let i = 0; i < (peakIndices.length-1); i++) {
// Instead of simply summing the difference of the indices we have to think about the physical nature of the walls.
// The walls have a width of 1 so we need to measure the right side of one wall to the left side of its neighbor.
levelVol += (peakIndices[i+1] - (peakIndices[i]+1));
};
return levelVol;
}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);
}Time Complexity: O(n)
Space Complexity: O(n)
We can do even better—we can get this down to O(n) time. The approach goes something like this: to determine the water at any given block, look for that block's largest leftwards neighbor, and it's 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: we can 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 subtracting its height from the smaller of its two bounding 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);
}It is possible to simplify the above solution. We can merge 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;
}