23
\$\begingroup\$

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.

enter image description here

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. Thanks Marcos for contributing this image!

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;
};
\$\endgroup\$
  • 2
    \$\begingroup\$ Umm... who's Marcos? \$\endgroup\$ – Justin Jun 2 at 16:45
  • 14
    \$\begingroup\$ The person who contributed that image to leetcode. (I just copied the description from leetcode) @Justin \$\endgroup\$ – thadeuszlay Jun 2 at 16:50
21
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thanks. I know it's not optimal, because the code iterates over the same values mutliple times. I'll improve it later. \$\endgroup\$ – thadeuszlay Jun 2 at 17:13
  • \$\begingroup\$ Why would maxRight need to be stored in an array? Isn't it just a single (scalar) value? \$\endgroup\$ – Solomon Ucko Jun 3 at 1:54
  • 2
    \$\begingroup\$ @Solomon that's in case you want to speed up the algorithm. As a first step, you could recalculate maxRight once at the beginning and later only after height[i] == maxRight. And if that is still not fast enough, you could iterate once over height and remember all indices where maxRight actually changes. This needs time O(n) and space O(n). \$\endgroup\$ – Roland Illig Jun 3 at 6:01
  • \$\begingroup\$ @Solomon the crucial point is that maxRight cannot be calculated by iterating the array in the normal order, the iteration needs to go backwards. \$\endgroup\$ – Roland Illig Jun 3 at 6:02
  • \$\begingroup\$ @RolandIllig I'm slightly confused by your explanation, but I think I understand what you're saying: new elements get added to maxLeft and maxRight from opposite directions, so only one of them (in this case maxLeft) can go in the same direction as the main loop. \$\endgroup\$ – Solomon Ucko Jun 3 at 10:42
21
\$\begingroup\$
  • 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.

\$\endgroup\$
  • \$\begingroup\$ That image I linked to is massive though (30,000x20,000 pixels; ~75mb), so Drive won't be able to preview it properly. \$\endgroup\$ – Carcigenicate Jun 2 at 18:25
  • \$\begingroup\$ Mod note: Comments are strictly for clarification and discussion of the post they are attached to. You're very welcome to socialize in Code Review Chat :) \$\endgroup\$ – Vogel612 Jun 5 at 9:42
14
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ Mod note: Comments are strictly for clarification and discussion of the post they are attached to. You're very welcome to socialize in Code Review Chat :) \$\endgroup\$ – Vogel612 Jun 5 at 9:43
9
\$\begingroup\$

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.

\$\endgroup\$
7
\$\begingroup\$

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]))

\$\endgroup\$
  • 1
    \$\begingroup\$ yes! functionalism!! \$\endgroup\$ – Stefano Jun 3 at 15:10
  • \$\begingroup\$ I have to start practicing FP and currying. As of now, that code is too packed for me \$\endgroup\$ – Carles Alcolea Jun 4 at 20:17
  • \$\begingroup\$ I'm familar with FP, but this is hard to follow. Also, it's slower, which would be acceptable as long as you can write it more concise and readable. But this is not the case here. Also, you forgot to intialize the accumulator in reduce. And some comments are redundant, e.g. the last two. \$\endgroup\$ – thadeuszlay Jun 4 at 21:27
  • 1
    \$\begingroup\$ What happens if the reduce function is called on an empty array( and without an initial value)? \$\endgroup\$ – thadeuszlay Jun 5 at 7:32
  • 1
    \$\begingroup\$ Yes. I think it's best to always provide an initial value \$\endgroup\$ – thadeuszlay Jun 5 at 7:42
4
\$\begingroup\$

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 answer (which I cannot comment 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 fields, so if anyone could confirm I would appreciate.

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;
};
\$\endgroup\$
  • 1
    \$\begingroup\$ I like the idea \$\endgroup\$ – thadeuszlay Jun 5 at 4:42
  • 1
    \$\begingroup\$ Welcome to CR... +1 Yes you have the complexity and storage correct and performance is an average 33% quicker. May I suggest that moveUp can be removed and the statement be if (maxL < maxR) { also i++, j-- can be put into height eg height[j--], and style with spaces while (i <= j) {, if () { and } else { (on same line as closing }) \$\endgroup\$ – Blindman67 Jun 5 at 11:02
  • \$\begingroup\$ @Blindman67 I like your suggestions. I added moveup before, I was calculating it at the end of the loop, but then I realised it made more sense at the beggining and forgot to simplify it. As for height[j--], I can't test it right now, but isn't rainWater += maxL - height[i++] change the expression, or is i++ gonna be applied after it computes maxL - height[i]? \$\endgroup\$ – Gabriel d'Agosto Jun 5 at 20:59
  • \$\begingroup\$ @Gabrield'Agosto post increment i++ and decrement i-- is performed after the expression is evaluated. eg if j = 1 then maxR - height[j--] will get height at index 1. However its a minor change and you are best to stick with what you fell comfortable with. \$\endgroup\$ – Blindman67 Jun 6 at 0:44
1
\$\begingroup\$

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)

\$\endgroup\$
  • 1
    \$\begingroup\$ There is a bug, Array.reduce second optional argument is not optional if the array is empty. eg [0].reduce(sum) works while [].reduce(sum) will throw an error, you need to provide the init value for empty arrays. \$\endgroup\$ – Blindman67 Jun 5 at 11:15
  • \$\begingroup\$ @Blindman67 Thanks, good spot, I've updated that now \$\endgroup\$ – OliverRadini Jun 5 at 11:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.