The Island Algorithm Explained

The island is a pretty famous leet code question. Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

Example 2:

Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

It may seem straightforward at first but unfortunately iterating through the matrix and increasing the number of islands by 1 every time there is a “1” is hit will not cut it. Instead, we’ll start by going through the grid, and when we hit a “1” we will not only increase our number of islands variable by one, we’ll also check above, below, left, and right to see if theres another “1.” If there is another “1,” we’ll know that that land is connected to our original land and not add to our number of islands. Each time we find a new “1,” even if it is above or below our first “1,” we will check if there are “1s” surrounding it as well.

To do this we will make a helper method and call it using recursion. Recursion is when a method calls on a helper method or itself several times to solve a problem. Our helper method will take all visited “1”s and change them to “2s.” They can really be changed to anything but “1”, even “0” would work. In python it our first problem will look like this:

We start with simply defining num of islands as 0, then iterating though our rows, followed by column one at a time until we land on “1”, which is when we increase the number of islands and call on our helper method. It would be better to call the helper method something more descriptive rather than just ‘helper method.’ Since its purpose is to go into our grid and mark the islands we have already visited why don’t we call it marking visited islands. Which would look like this:

Please note, at the end of each if statement, our helper method calls itself. This is the way we can make sure all “1s” that branch out of our original “1” are marked as “2.” If they are marked as “2s” they will not trigger our if statement on the original problem and add 1 to our number of islands variable. Put it all together and the whole thing should look like this.

Remember, breaking an algorithm down into smaller problems makes it much easier to understand and correctly execute.