Total water capacity in a 2D array, which represents a topographical map

Question

I was recently asked this question in an interview and I couldn't figure out how to implement it. I am hoping someone can point me in the right direction on how to approach this problem.

Problem Statement: Given a 2D array of integers find the total water that can be held. The numbers represent the elevation in a map (i.e the heights of a mountain). The water flows from the highest mountain to a valley (highest height to lowest height).

Example 1: This is a 5 x 3 matrix. 10 is the highest peak. You can assume the water flows down and starts collecting at tile 2 which is at co-ordinate (3, 1). This tile will collects 7 units of water. Before spilling over to neighbouring tiles of height 9 at co-ordinates (2, 0) or (3, 0) and flowing into the ocean (assume edges are surrounded by ocean). So the total water that was collected for this map is 7.

9  9  9
9 10  9
9  9  9
9  2  10
10 10 10

Example 2:

    9   9  9  9  9 9
    9  10  9  8  2 4
    9   9  9 10  3 5
    9   2  2 10  3 5
   10 10  10 10  9 9

In this case the water can collect in the following co-ordinates:

1. (3, 1) & (3, 2). So total capacity => 7 + 7 = 14
2. (1, 4) (2, 4) & (3, 4). These co-ordinates can store 2, 1, 1 respectively. Because the max they could hold is 4 before water starts to spill out of the edge at co-ordinate (1, 5). So total capacity => 2 + 1 + 1 = 4

Over all capacity is 14 + 4 = 18.

I tried to tackle this problem using flood fill. By finding a path from highest peak to lowest and use this path to determine the water that can be stores at the lowest height. I wasn't sure if I was on the right path. Any thoughts on how to approach this problem?

Answer 1

You're on the right path with the flood fill. Here's one approach to the problem.

First, mark all the edge tiles as finished.

Then create a sorted list of the inner tiles, lowest first.

For each tile in the list perform a flood fill that

1. finds all tiles that are at the same level as the lowest tile (the valley tiles)
2. finds the minimum surrounding tile (the outlet tile)
3. determines whether any of the outlet tiles are already finished

Then increase the level of the valley tiles to match the level of the outlet tile. If the outlet tile is finished, then all of the valley tiles are now finished. Otherwise, expand the valley to include the outlet tiles.

---

Here's how the algorithm works with the second example from the question. Initially, edge tiles are finished and inner tiles are not.

Assuming that the 2 in the upper right is first. The outlet tile is the 3. So increase the 2 to a 3, adding 1 to the total water. Then the 3s can be increased to 4, adding 3 to the total water. And the 4 is finished, so that valley is now finished.

Next up is one of the 2s in the lower left. The flood fill will find two valley tiles, and the outlet tile is 9. So we can add 7 to two tiles, adding 14 to the total water. And one of the outlets is finished, so that valley is now finished.

At this point every remaining tile is adjacent to an outlet tile that is equal or lower, and also finished. So all remaining tiles are marked as finished. And the total water is 1+3+14 = 18.