You are given a two-dimensional array of potentially unequal height and width. It contains only 0s and 1s. This array represents a map: 0s are land, and 1s are water. A "river" on this map consists of any number of contiguous, adjacent water squares, where "adjacent" means "above", "below", "to the left of", or "to the right of" (that is, diagonal squares are not adjacent). Write a function which returns an array of the sizes of all rivers represented in the input matrix. Note that these sizes do not need to be in any particular order.
It's sorta similar to the flood fill algorithm! Remember the good 'ol paint fill?
For example:
const input = [
[1, 0, 0, 1, 0],
[1, 0, 1, 0, 0],
[0, 0, 1, 0, 1],
[1, 0, 1, 0, 1],
[1, 0, 1, 1, 0]
];
riverSizes(input); // returns [1, 2, 2, 2, 5]That is, in this input, there is one river of size 1, there are three rivers of size 2, and there is one river of size 5.
Hints:
- it is acceptable to mutate the input arrays.
- beware of repeating your checks
- separation of concerns
The solution consists of two parts: an outer function and a recursive helper. The outer function, riverSizes, iterates the multidimensional arrays until it finds the starting point of a river. An inner function, checkNeighbors recursively follows the length of a river, determining its length and returning this number to its caller, whether riverSizes or checkNeighbors.
Here's the outer function. We could use for loops, but the forEach syntax is a bit more readable. Note that we use the extra index argument which forEach passes in to get our x/y position in the multidimensional arrays, counting from zero in the upper-left-hand corner.
const riverSizes = input => {
let results = [];
input.forEach((row, y) => {
row.forEach((cell, x) => {
if (input[y][x] === 1) {
results.push(checkNeighbors(x, y, input));
}
});
});
return results;
};Note that we're committing ourselves, here, to implementing checkNeighbors in such a way that it returns an integer to push into the results array.
Now for checkNeighbors. What does it need to do? It needs to increment a count which it will eventually return, and then call itself for all adjacent cells which are themselves rivers. Whatever mechanism it uses to handle the edge of the map will need to not choke on potential undefineds if the map's bounds are exceeded. And, we'll need to avoid stack overflows that can arise from checking the same cells over and over, meaning we'll need some way to keep track of where we've already been.
We could keep a separate data structure which records cells we've visited. But since we're allowed to mutate the input, and since we'll already be checking to see if cells are water or land, why not just flip visited water cells to land, so we don't visit them again?
There are different ways to handle the syntax for checking neighboring cells. We might hardcode a branching structure with one conditional for each neighbor. Instead, we'll call forEach on an array containing the input cell's neighbors, which allows us to cut down on the repetition that would come with a hard-coded branching approach.
Here's what it might look like:
const checkNeighbors = (x, y, input) => {
input[y][x] = 0; // mark cell as visited
let size = 1;
[[x + 1, y], [x, y + 1], [x - 1, y], [x, y - 1]].forEach(([i, j]) => {
// make sure we don't access a row that doesn't exist &&
// then check to see if we have a river because 1 is truthy
if (input[j] && input[j][i]) {
size += checkNeighbors(i, j, input);
}
});
return size;
};The recursive neighbor-checking technique we've employed in solving this problem is related to a well-known algorithm called "flood fill." Think of the "paint bucket" tool in a program like Microsoft Paint or Photoshop. This tool lets you click on a pixel in an image, after which an algorithm "finds" all recursively contiguous pixels with the same color, which it then changes to a new color. What's going on under the hood here is not unlike our checkAdjacent function, which "flood fills" rivers with land.
The recursive technique we've used here can also be applied to some kinds of problems which involve navigating or solving mazes. If we know where we are in a maze, perhaps represented as a multi-dimensional array, we can "flood fill" our way out from a starting point in a maze until we reach an "exit", perhaps keeping track of the moves we've made along the way.
So, keep this recursive traversal technique in mind if you encounter interview questions involving paint buckets, mazes, or counting contiguous regions on a representation of a map!
You may be aware that, at least in principlee, every problem which can be solved recursively can also be solved iteratively.
Sometimes, recursive solutions are cleaner and easier to understand, while sometimes iterative solutions are best. Trying to rewrite iterative algorithms as recursive and vice versa can help us cultivate a sense for which makes more sense, in a given case. Thus, for kicks, let's try writing checkNeighbors iteratively.
Recursion in Javascript depends on a call stack which keeps track of the lexical scope and its state inside each function. Implementing a recursive solution iteratively usually requires us to set up our own data structure which keeps track of state in a manner similar to the call stack. You may have encountered this when working with trees and lists, in which one often pushes references to a node in the graph to a queue or stack which is then iterated by a while-based structure.
But here our data structure consists in coordinates, rather than complex objects to which we can store references. So we'll need to keep track of where we are on the board; objects or arrays will work but the object syntax makes destructuring a bit cleaner:
const checkNeighbors = (x, y, input) => {
const queue = [{ x, y }];
let size = 0;
while (queue.length) {
const { x, y } = queue.shift();
size += 1;
input[y][x] = 0;
[[x + 1, y], [x, y + 1], [x - 1, y], [x, y - 1]].forEach(([i, j]) => {
if (input[i] && input[i][j]) {
queue.push({ x: i, y: j});
}
});
}
return size;
};The recursive solution is much easier to understand! Letting the call stack keep track of state can be a big help.
When you practice for interviews, try rewriting recusrive solutions as iterative and iterative as recursive; pulling state out of the call stack will help you learn to reason about how to write better recursive code, and will help you see when recursion can help you solve a problem in a simple way.