Practice Problem: Water Volume

I was posed this question during an interview, and despite getting stuck on it then (T_T) it's now on my short list of favorites because I found it both challenging and really satisfying to finally solve! The problem went something like this (in my own words):

Water Volume

You are given an array of non-negative integers representing an elevation map. Imagine that the heights represented by these integers are physical hills and valleys, and when it rains water will accumulate in the valleys. Calculate and return a single integer value that represents the maximum volume of water that could accumulate.

For Example:

Given the array [2, 5, 4, 0, 3, 1, 6, 2, 1, 3], the function should return 15. Below is a visual representation of the elevation map:

             X
   X - - - - X
   X X - - - X
   X X - X - X - - X
 X X X - X - X X - X
_X_X_X_-_X_X_X_X_X_X_

 2 5 4 0 3 1 6 2 1 3

Think of the X’s as the heights, and the dashes as the water level filling up the empty spaces. You’ll see there are fifteen dashes total, and this is the number we are interested in calculating.

My Approach

At first, I could only conceive of a solution in terms of iterating "horizontally" through the array and summing the vertical gaps. I tried finding the first tallest height and then the next, and attempting to account for the spaces between. It is possible to solve that way, but I personally found that approach to be overly complex and convoluted in terms of implementation - I kept tripping over myself.

But!

My "aha" moment happened when I finally saw it "vertically" and iterated from top to bottom, summing along the horizontal axis of the visualized elevation map, instead.

Try solving it on your own! Which approach works best for you?

My Solution

1. First, find the maximum height in the array and set a "current height" variable equal to it. Also, initialize the return value in a "volume" variable.

const elevationMap = [2, 5, 4, 0, 3, 1, 6, 2, 1, 3];

function findVolume (heights) {
  let volume = 0;

  let currentHeight = Math.max(...heights);

  return volume;
}

2. Starting at the current (highest) height level, find the other indices with values at that height, so that we can determine where the gaps are between them. We'll be working our way down from the max height to the lowest level, and I'll use a while loop instead of a for loop for readability, but either would work. We'll define a couple of helper functions as descriptively as possible:

function findVolume (heights) {
  let volume = 0;

  let currentHeight = Math.max(...heights);

  while (currentHeight > 0) {
    const indicesAtHeight = 
    findIndicesAtOrAboveHeight(currentHeight, heights);

    const additionalVolume = 
    determineVolumeAtHeight(indicesAtHeight);

    volume += additionalVolume;

    currentHeight--;
  }

  return volume;
}

3. Our first helper function will find all the height array indices with values at or above our current height:

  findIndicesAtOrAboveHeight = (height, allHeights) => {
    let relevantIndices = [];
    allHeights.forEach((h, idx) => {
      if (h >= height) {
        relevantIndices.push(idx);
      }
    });
    return relevantIndices;
  }

4. The next helper function will take our array of indices at the current height and add up the number of empty spaces between them. We don't even need to pay any attention to the broader array of heights here, we can just add up the difference between the sequential index values (I've tried to name things descriptively here to make it more understandable, but the complete solution at the end will be more concise)

  determineVolumeAtHeight = (indices) => {
    let volAtHeight = 0;

    for (let i = 0; i < indices.length - 1; i++) {
      const currentIndex = indices[i];
      const currentIndexPlusOne = indices[i]+1;
      const nextIndex = indices[i+1];

      if (nextIndex !== currentIndexPlusOne) {
        volAtHeight += (nextIndex - currentIndex - 1);
      }
    }

    return volAtHeight;
  }

5. Our loop should continue until the current height reaches zero, and then we can simply return the volume value.

All Together Now

The solution described above will look like this when everything is put together:

function findVolume (heights) {
  let volume = 0;
  let currentHeight = Math.max(...heights);

  findIndicesAtOrAboveHeight = (height, allHeights) => {
    let relevantIndices = [];
    allHeights.forEach((h, idx) => {
      if (h >= height) {
        relevantIndices.push(idx);
      }
    });
    return relevantIndices;
  }

  determineVolumeAtHeight = (indices) => {
    let volAtHeight = 0;
    for (let i = 0; i < indices.length - 1; i++) {
      if (indices[i+1] !== indices[i]+1) {
        volAtHeight += indices[i+1] - indices[i] - 1;
      }
    }
    return volAtHeight;
  }

  while (currentHeight > 0) {
    let indicesAtHeight = 
    findIndicesAtOrAboveHeight(currentHeight, heights);

    let additionalVolume = 
    determineVolumeAtHeight(currentHeight, indicesAtHeight);

    volume += additionalVolume;

    currentHeight--;
  }

  return volume;
}

Wrap Up

This solution gets the job done, but it could certainly be optimized. You could go about it the other way, summing vertically instead of horizontally by height level, or you could introduce recursion to make it more concise. I won't tackle those here, but I'd love to hear about other approaches that might work well. Thanks for reading!