Island Count

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. Two land spaces are connected if they are adjacent horizontally or vertically, but not diagonally.

Example:

.0...
.00..
....0

Answer: 1 island

..000.
..000.
..000.
.0....
..000.

Answer: 3 islands

Now how would we write a program that takes as input an island map and returns the number of islands?

We notice that at a base level, we will have to examine a position on the grid, evaluate it, and move on to our next. These sorts of problems generally lend themselves to a recursive solution and the algorithm will follow along these lines:

1. Examine the current state, if the current state is a solution:
2. Handle the solution
3. Else, examine all the next decisions and implement them
4. Check if it’s valid and if so,
5. Recursively check if it’s a solution
6. Make the decision and move on to the next one

When coded, we would end up with something like this

function countIslands(islandMap) {
var destroyIsland = function(island, i, j) {
// 3. Else, consider all next decisions and implement them
if (islandArray[i] &&
i < islandArray.length &&
j < islandArray[i].length &&
islandArray[i][j] === '0') {
      // 4. Check if it’s valid and if so,
islandArray[i][j] = 'destroyed';
// 5. Recursively check if it’s a solution
// 6. Make the decision and move on to the next one
destroyIsland(islandArray, i+1, j)
destroyIsland(islandArray, i, j+1)
destroyIsland(islandArray, i-1, j)
destroyIsland(islandArray, i, j-1)
}
}
for (var i = 0; i < islandArray.length; i++) {
for (var j = 0; j < islandArray[i].length; j++) {
// 1. Examine the current state, if the current state is a solution:
if (islandArray[i][j] === '0') {
// 2. Handle the solution
count++
destroyIsland(islandArray, i, j)
}

Let’s examine this one by one.

First, we iterate through every element in the 2d array and examine that element. If that element is indeed an island, we increase the count by 1. Then, we examine all the next decisions with destroyIsland .

for (var i = 0; i < islandArray.length; i++) {
for (var j = 0; j < islandArray[i].length; j++) {
if (islandArray[i][j] === '0') {
count++
destroyIsland(islandArray, i, j)
}

In destroyIsland, we check whether the decision was valid (whether it was an island via ===’0'), and if so we destroy it. Otherwise, we examine all the next decisions and recursively check if each is a solution.

var destroyIsland = function(island, i, j) {
if (islandArray[i] &&
i < islandArray.length &&
j < islandArray[i].length &&
islandArray[i][j] === '0') {
      islandArray[i][j] = 'destroyed';
destroyIsland(islandArray, i+1, j)
destroyIsland(islandArray, i, j+1)
destroyIsland(islandArray, i-1, j)
destroyIsland(islandArray, i, j-1)
}
}
Like what you read? Give Adrienne Tran a round of applause.

From a quick cheer to a standing ovation, clap to show how much you enjoyed this story.