The pond-counting problem

One of my previous posts focused on the rainwater trapping problem. This time, keeping with the water theme, I worked through the pond counting problem.

Here it is (paraphrased from Cracking the Coding Interview ):

You have a 2-dimensional integer matrix representing a plot of land with a number of ponds on it. A zero represents “water”, and any other integer represents solid ground. A “pond” is any region of connected water, and can be connected vertically, horizontally, or diagonally. The “size” of a pond is the total number of connected water cells in the pond. Write a function which computes the sizes of all ponds in the matrix and outputs it to the console as an array of pond sizes. The order is not important as long as you have the right number of ponds in the correct sizes.

Here is a sample input and its expected output:

Sample Input:  [ [0,2,1,0],
                 [0,1,0,1],
                 [1,1,0,1],
                 [0,1,0,1] ];

Expected Output: [2,4,1]

Try it now, if you like.

…

My Solution

The basic approach to this problem is to iterate through the 2-d array and find all water squares. Then propagate out to the neighbors of those squares, counting all the zeros. Keep going until there are no water neighbors and add that pond size to the list. Keep track of all visited squares in some way in order to avoid visiting (or counting) them again. Once you have iterated through the array, and assuming you did the counting and tracking correctly, you should have all the pond sizes.

Note that I used a “revealing module” pattern in my JavaScript in this case — this is certainly not necessary for a one-off problem like this but is a good practice for larger projects where having a distinction between public and private variables and functions is a good idea. You would call PondSize.pondSizes(inputArray) to get the answer.

I used a stack (actually a JavaScript array functioning as a stack) and while loops to find the size of each pond. This is basically a depth-first search on a graph. The “graph” is really just the array and a function to predictably find the neighboring cells, but it functions similarly.

Another Approach

Another approach (which I looked up after solving it in the above way) would be to take care of tracking visited cells using a second array (or if you don’t mind modifying the input array, by putting a -1 in the visited cells). This might be slightly more efficient than my approach (as it wouldn’t involve splicing values out of an array, which in some cases can be an expensive operation). You could also use recursion rather than iteration to do the pond-size calculation. Otherwise, other solutions seem to be pretty similar to mine.

Time Complexity

The time complexity for all solutions seems to be O(W*H), with W and H referring to the width and height of the input array. While there are several other steps involved, the nested for loops would dominate in large data sets. Using copious loops seems unavoidable. The while loops might seem at first to contribute to a higher complexity, but the number of iterations quickly decreases as more squares are visited.

Next Steps

I hope you enjoyed this problem. It’s my last one as part of Viking Code School’s teaching problems. Now I will be looking for jobs! I’ll surely be doing more as part of interviews and interview prep. It’s hard to believe my journey as a Viking is nearly complete, but I am looking forward to coding professionally!