Trapping Rain Water

Question

This task is taken from Leetcode:

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

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example:

Input: [0,1,0,2,1,0,1,3,2,1,2,1]     

Output: 6

My solution

/**
 * @param {number[]} height
 * @return {number}
 */
function trap(height) {
  let res = 0;
  const LEN = height.length;
  for (let i = 1; i < LEN - 1; i++) {
    let maxLeft = 0, maxRight = 0;
    for (let j = i; j >= 0; j--) {
      maxLeft = Math.max(maxLeft, height[j]);
    }
    for (let j = i; j < LEN; j++) {
      maxRight = Math.max(maxRight, height[j]);
    }
    res += Math.min(maxLeft, maxRight) - height[i];
  }
  return res;
};

Answer 1

You wrote very clear and readable code:

• the variable names express the purpose
• you use const and let instead of the old var
• you encapsulated all the interesting code in a function, which makes it easy to copy and reuse the code

You chose to use as few temporary memory as possible (4 local variables, no arrays or other objects), at the cost of needing more execution time, \$\mathcal O\left(\text{len}(\textit{height})^2\right)\$. If you later need it, you could reduce the execution time to \$\mathcal O\left(\text{len}(\textit{height})\right)\$ by calculating maxRight once for all i and storing it in an array.

You can optimize the inner for loop from the calculation of maxLeft, since it can be calculated by looking only at the previous maxLeft and the current height[i]:

function trap(height) {
    const len = height.length;
    let result = 0;

    if (len === 0)
        return 0;
    let maxLeft = height[0];

    for (let i = 1; i < len - 1; i++) {
        maxLeft = Math.max(maxLeft, height[i]);
        ...
    }
    ...
}

You only need to recalculate maxRight if height[i - 1] is equal to it. Because if it isn't, the maximum height cannot have changed.

These two optimizations destroy the nice-looking symmetry of your current code. Therefore you may or may not want to apply them. In any case, you should know that they exist.

In my above code I named the variable len instead of LEN since it feels more like a normal variable than like a constant. A constant is something whose value is the same over time. This len variable depends on the height parameter, therefore it may differ between multiple calls of the trap function.

Answer 2

• This is purely stylistic, but I'd add some spacing around the loops.

• I'm also not a fan of multiple declarations on the same line, so I'd separate out the maxLeft and maxRight declarations.

• Lastly, the parameter should arguably be called heights. height suggests that it's a single number representing a height, whereas it's actually multiple height values.

---

function trap(heights) {
  let res = 0;
  const LEN = heights.length;

  for (let i = 1; i < LEN - 1; i++) {
    let maxLeft = 0
    let maxRight = 0;

    for (let j = i; j >= 0; j--) {
      maxLeft = Math.max(maxLeft, heights[j]);
    }

    for (let j = i; j < LEN; j++) {
      maxRight = Math.max(maxRight, heights[j]);
    }

    res += Math.min(maxLeft, maxRight) - heights[i];
  }

  return res;
};

The spacing bulks the code up a bit, but I've always found code to be easier to read when it isn't all compacted together.

Answer 3

Reviewing complexity

So far only one answer has addressed the complexity issue, and is a considerable improvement over your solution. As the existing answers have addressed code style I will stick to the complexity as there is a less complex solution.

Looking both ways!?

Your solution is looking in both direction to find the next peak and thus calculate the volume trapped. You do this for each elevation and thus get a complexity of \$O(n^2)\$ and \$O(1)\$ storage.

One answer's suggestion is to store the max values for quick reference which means you will need to increase the storage to \$O(n)\$ in order to get \$O(n)\$ complexity which is a much better approach.

However the extra storage can be avoided.

Look behind.

To solved in \$O(1)\$ storage and \$O(n)\$ complexity use a two pass method that tracks the peak elevation you have already passed over (look behind rather than look both ways)

One that passes from left to right checking all elevations and a second from right to left checking only to the highest peak found in the first pass.

At most you will pass over each elevation twice, and best case is if the right most elevation is the highest you need only pass over each elevation once.

This avoids the memory overhead and improves performance ^_[1], over the best solution so far suggested, by reducing the iterations to an average of \$n * 1.5\$ rather than \$n * 2\$

^{[1] Note performance does not mean complexity}

Example

• \$O(1)\$ storage, \$O(n)\$ complexity solution

I checked its correctness against your function, (farmed to get a good volume of tests, thus far at half a billion tests on random data the two functions agree)

function floodVolume(elevations) {
    var peakIdx, i = 0, peak = 0, volume = 0, total = 0;
    const depth = (i, elevation = elevations[i]) => {
        if (elevation >= peak) {
            peak = elevation;
            peakIdx = i;
            total += volume;
            volume = 0;
        } else { volume += peak - elevation }
    }
    while (i < elevations.length) { depth(i++) }
    const MAX_IDX = peakIdx;
    volume = peak = 0;
    while (i-- >= MAX_IDX) { depth(i) }    
    return total;
}

Answer 4

Here's a more functional approach you might like:

function trappedWater(heights) {
  const maxSoFar = arr => arr.reduce((m, x) => m.concat(Math.max(...m, x)), [])
  const leftWall = arr => [0, ...maxSoFar(arr).slice(0, -1)]
  const l = leftWall(heights)
  const r = leftWall(heights.reverse()).reverse()
  return heights.reduce((m, h, i) => m + Math.max(0, Math.min(l[i], r[i]) - h), 0)
}

Try it online!

The main difference is that we first calculate the left "wall" height and the right "wall" height for every index, using the same leftWall function, which itself uses a "scan sum" utility function, and noticing that the rightWall values can be calculated using the leftWall function, by applying reverse to both the input and the output.

The amount of water at any index is then the minimum of the left and right wall heights minus the height at the point, or zero if that quantity is negative. Then we just sum all of those.

Answer 5

Going even more functional, splitting out mapping functions, spicing with a bit of curry.

// Curried initialization of the current max value
const maxSoFar = max => n => max = Math.max(max, n)
// The max previous value; like max current but shifted to the right with a zero first
const maxPrevious = arr => [0, ...(arr.map(maxSoFar(0)))].slice(0, -1)
// Note the [...arr] - .reverse() changes the original. Not very functional
const maxFollowing = arr => maxPrevious([...arr].reverse()).reverse()
// Function to get mapping function subtracting two arrays
const subtract = otherArr => (n, index) => n - otherArr[index]
// Like above, but taking the minimum value
// Non-currying to make the main function more readable
const min = (arr, other) => arr.map((n, index) => Math.min(n, other[index]))

const trappedWater = heights => min(maxPrevious(heights), maxFollowing(heights))
          .map(subtract(heights))
          .filter(n => n > 0) // Positive only
          .reduce((a,b) => a + b, 0) // Sum the array

console.log(trappedWater([0,1,0,2,1,0,1,3,2,1,2,1]))
console.log(trappedWater([0,1,1,0]))

Edit a couple years later. Happened on this and saw it could be a lot simpler, though losing some efficiency

const maxBefore = (a, i) => Math.max(...a.slice(0,i+1))
const maxAfter = (a, i) => Math.max(...a.slice(i))

const trappedWater = heights => heights
  .map((n, i) => Math.min(maxBefore(heights, i), maxAfter(heights, i)) - n)
  .reduce((a,b) => a + b, 0) // Sum the array

console.log(trappedWater([0,1,1,0]))
console.log(trappedWater([0,1,0,2,1,0,1,3,2,1,2,1]))

or inlining the maxes

const trappedWater = heights => heights
  .map((n, i) => Math.min(Math.max(...heights.slice(0,i+1)), Math.max(...heights.slice(i))) - n)
  .reduce((a,b) => a + b, 0) // Sum the array

console.log(trappedWater([0,1,1,0]))
console.log(trappedWater([0,1,0,2,1,0,1,3,2,1,2,1]))

or just using the fact that the max can include the current height to improve the original

const maxSoFar = max => n => max = Math.max(max, n)

const trappedWater = heights => {
  const before = heights.map(maxSoFar(0))
  const after = heights.reverse().map(maxSoFar(0)).reverse()
  return heights
   .map((n, i) => Math.min(before[i], after[i]) - n)
   .reduce((a,b) => a + b, 0) // Sum the array
}
console.log(trappedWater([0,1,1,0]))
console.log(trappedWater([0,1,0,2,1,0,1,3,2,1,2,1]))

Answer 6

I stumbled upon your question by accident (I normally only visit StackOverflow) and finally decided to make an account.

The Idea

After I saw @Blindman67's answer (which I cannot comment on since I do not have enough reputation), I was wondering if we could reduce the iterations from \$n* 1.5\$ to just \$n\$. Thus, I propose this idea. Instead of evaluating all the way to the right and then coming back, create 2 different pointers.

Pointer i would go from left to right, and pointer j would go from right to left. The idea is to get the first and last block, and figure out which one is higher. Then, use the lowest one for our walls. If maxL < maxR, we move up, and compare height[i] to maxL, since we know for sure that there is a wall somewhere to the right side which will retain the water. On the other side, if maxR < maxL, we do the opposite. By moving i up every time we compare it to maxL and j down every time we compare it to maxR, when i=j it means we evaluated every single point from our array.

Example Code

I believe the solution is still \$O(n)\$ complexity and \$O(i)\$ storage, but I have little knowledge in this field, so if anyone could confirm I would appreciate it.

var trap = function(height) {
  const len = height.length;
  let rainWater = 0;
  let maxL = height[0];
  let maxR = height[len - 1];
  let i = 1;
  let j = len - 2;
  
  while ( i <= j ) { 
      if ( maxL < maxR ) {
          maxL = height[i] > maxL ? height[i] : maxL;      
          rainWater += maxL - height[i];
          i++;  
      } else {
          maxR = height[j] > maxR ? height[j] : maxR;  
          rainWater += maxR - height[j];
          j--;    
      }
  }
  return rainWater;
};

Answer 7

I liked the idea of doing this in a way which is analogous to the way the image is drawn, that is to say, creating a data structure which is somewhat similar to the image you have above, and then using that to count which spaces would hold water.

This isn't so much of a code review, as a presentation of an alternative way of doing the same thing (as are many of the answers here). I don't know that I'd say it's better, but it was interesting to me at least.

The code maps the size array to a grid of ones and zeroes, trims any initial zeroes, and then counts how many are left in each row. I'm fairly sure this will always give a correct result, but then, I may well have missed something.

const data = [1,0,2,1,0,1,3,2,1,2,1];

const sizesToRows = sizeArray => [...Array(Math.max(...sizeArray))]
  .map((_, i) => sizeArray.map(s => s > i ? 1 : 0))

const trimArray = condition => array => array.slice(
  array.findIndex(condition),
  array.length - array
    .reduce((ary, ele) => {ary.unshift(ele); return ary}, [])
    .findIndex(condition)
);

const removeLeadingAndTrailingZeroes = trimArray(x => x !== 0);

const countConditionMatches = condition => array => array
  .reduce((p, c) => condition(c) ? p + 1 : p, 0);
  
const countZeroes = countConditionMatches(x => x === 0);

const sum = (p, c) => p + c

const result = sizesToRows(data)
  .map(removeLeadingAndTrailingZeroes)
  .map(countZeroes)
  .reduce(sum, 0);
  
console.dir(result)