Number of Islands - LeetCode Explained (With Animations & Visualizations)

In this guide, we will look at the Leet Code problem: 200. Number of Islands.

As you probably know this is an important problem since it also features in the Blind Curated List of Top 75 LeetCode Questions to Save Your Time. This was a list created by a Facebook engineer to help people prepare for Coding Interviews. It’s a very popular list of just 75 questions from Leetcode. And if you really understand how to solve these 75 problems, in theory, you should be well prepared for coding interviews at FAANG, MANGA, or any other place you would like to apply.

Via this guide, the “Number Of Islands” problem from Leetcode will be explained in detail using visualizations and a little demo that you can play with. Let’s get started.

The Problem & The Plan – A Simple Intuitive Real-World Approach

So the problem statement says:

Given an m x n 2D binary grid which represents a map of '1's (land) and '0's (water), return 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 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

So there is an array with sub-arrays that represents a “world”. Each “block” in the world can be “land” or “water”. And our task is to count the number of islands.

Okay, so imagine that the “world” from the problem is something like this:

Imagine that you have a little boat and you are starting from some corner of this world. What would your plan be in order to find out the number of islands? Maybe it would be something like this:

Sail from one block to another until you find a block with land.
When you find a block with land, conquer it and put a flag on it.
Cover all blocks of the island and put flags everywhere so that you can keep track of what you have conquered and what you have not.
When you run out of land you can conquer on the current island, get back into your boat and sail to the next block where you can find land. At this point, you can add 1 island to the “number of islands” count.
Keep doing this until you have conquered the whole world.

Below is a visualization of how the plan might look in action.

2 Sub-Problems

As I see it, there are 2 subproblems.

How to move over all the water blocks one by one in an organized way?
How to “conquer” or “cover” all the land on an island once you find the first land block?

Sub-Problem 1: How to move over all the water blocks in an organized way?

This one is the simpler-to-understand subproblem. You do it like a snake. Let’s visualize this with a world that has mainly water and little or no land.

To understand how this is implemented, we first have to properly understand what the following code means:

block[0][5]

The “world” is defined as an Array of Arrays.

[ 
    ["1","1","1","1","0"], 
    ["1","1","0","1","0"], 
    ["1","1","0","0","0"], 
    ["0","0","0","0","0"] 
]

Let us call each of the individual arrays: “sub-arrays”. And the outer Array we will just call “Array”

In “block[0][5]“, we are saying that we want the 0th sub-array. And in that, we want the element at the 5th index.

If we are on the same page about all this terminology, we can start to see how we would move over all the water blocks in an organized way.

The plan to move to the next block based on where you are would be something like this:

Most of the time, going to the next block is going to be: “Just increase the sub-array index by 1“
This will fail if you are already at the end of the current sub-array.
So, if you find yourself at the end, you need to go to the start of the next sub-array. So, increase the array index by 1 and make the sub-array index 0.
If you find yourself wanting to move to the next sub-array, but you are already on the last one, you are done!

All of this can be expressed in JS code as follows:

const moveToTheNextBlock = () => {
    let currentBlock = currentTraversalIndexes;

    let newSubArrayElementIdx = undefined;
    let newSubArrayIdx = undefined;

    if ( currentBlock.subArrayElementIdx == (worldSize - 1) ) {
        // We are at the end of the current sub-array
        // we need to move to the next one
        if ( currentBlock.subArrayIdx == ( worldSize - 1 ) ) {
            // There is nowhere else to go
        } else {
            newSubArrayElementIdx = 0;
            newSubArrayIdx = currentBlock.subArrayIdx + 1;
        }
    } else {
        newSubArrayElementIdx = currentBlock.subArrayElementIdx + 1;
        newSubArrayIdx = currentBlock.subArrayIdx;
    }

    let newBlock = {
        subArrayIdx: newSubArrayIdx,
        subArrayElementIdx: newSubArrayElementIdx
    }

    return newBlock;
}

Sub Problem 2: Once You Find Some Land, How Do You Conquer All Of It In An Organized Way?

Now this second sub-problem is the “heart” of the matter. So, what is a good way to do this? Let’s try to build up an intuition.

Let’s ask another question: Assume that, you need to go from your home to the doctor’s clinic. You are suddenly blind for some strange reason. But, a friend from out of town is with you. Now, what you can do is give them verbal instructions like:

Drive out onto the main road.
Go straight till you see the big tree.
Then turn right.
Then stay on that road for the next 5 mins until you see…

You see, you have broken down the task of reaching the doctor’s office into little steps. Where your friend needs to complete the steps in the order you give them to him/her. They have to follow the order because the steps are “related” to each other. Your friend will only be able to see the tree once he goes on to the main road for example.

If you think about it, conquering the land on the island you reach is kind of like that. In the real world, if you were trying to conquer an island and stick flags all over the island, you would have to walk a little, then you would see more land. You would stick your flag in. Then you would walk some more and you would see more land. Every time you move in some direction, you will see more land you can conquer based on where you are. Here also the previous step is related to the current step.

Because the steps are related, you can represent the whole problem in terms of a “graph”. As you probably know, a “graph” is a data structure that shows up a LOT in many applications and in the field of Computer Science. This problem is also a way to test your knowledge of graphs and see if you can recognize that a graph can be used to solve this problem.

Here are some great videos on the topic:

What Kind Of Graph Do We Have In This Problem?

I hope that by this point, you are able to see that each “land block” in the “world” is a node on a graph. And we can sort of move from node to node if there is land connecting it. There are vertices also in this graph, but they are implied. What we mean is that we can move from one block of land to another, because they are “adjacent” either “horizontally” or “vertically”. We can imagine that these nodes are connected by vertices.

The original problem says:

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically

You can think of all the islands as little graphs. In our “sailing” across the world, if we come across one of the “land” nodes, we stop sailing and traverse the graph and conquer all the land. We only stop when there is no more land to conquer or the graph is fully traversed.

Okay. So, we gotta use graphs. Also, we now know that every island is a little graph. So, next question:

What Algorithms Can We Use To Visit All The Nodes In The Graph Efficiently

Well, there are 2 main algorithms we can choose from. As you probably know they are: Depth First Search (DFS) and Breath First Search (BFS).

Let me share a few videos I found where these concepts are well explained:

So, having understood the BFS and DFS algorithms, which one should you use? Which one is faster?

Which One To Use? Which one is faster? DFS or BFS?

Well, the answer is, both are equally fast. There are applications and situations where DFS is better than BFS or the other way around. But in this case, it does not matter. In this case, all you want to do is go over all the nodes in the graph.

So, in this case, since all you want to do is cover every node in the graph, it does not matter which one you use. Both are equally fast.

Let’s try to visualize this:

So to help you deeply understand DFS and BFS and see how they both work and why they take the same amount of time, you can actually play with the visualization below:

See the Pen
DFS vs BFS Visulization by Khoj Badami (@khoj-badami)
on CodePen.

If you click the “Next” button you will move ahead one step. And as you keep moving ahead one step at a time, you will see that the “Number Of Blocks Covered” in both cases stays exactly the same. Even though the algorithms have very different approaches to cover all the nodes.

So, I hope that by now I have convinced you that you can use BFS or DFS, whichever one you feel you like.

Putting It All Together

So, let me summarize the plan now with all the things we have learned:

The plan is to move from index to index, (or block to block) and search for land.
Once we find land, we want to use DFS or BFS to traverse the land (because both are equally fast). Because we are treating the islands like graphs like we saw above.
Once we have traversed the whole graph/island, we go back to finding land from the point we left off. And just before we start the search for land again, we increment the number of islands count by one.
We keep doing this until we reach the end of the world.

So, in order to deeply understand this plan, I have made another visualization you can play with.

See the Pen
Number of Islands – LeetCode Explained by Khoj Badami (@khoj-badami)
on CodePen.

You might find the above box restrictive. So, I have also hosted the above on a separate URL so that you can play with it in a new window.

I have created a slider that allows you to control the ratio of land to water so that you can see how the algorithm acts in different worlds. Also, you can click: “Next” one at a time in order to see what the algorithm will do in the next step.

I have recorded 3 different videos for different types of worlds. You can see them below:

Finally, Let’s Look At The Code That Passes On Leetcode

Now, I hope that at this point, you have a good intuitive understanding of how to solve this problem.

So there is one thing left, coding it up.

Now, I have written the code below with readability in mind. (Which I hope has been achieved). Keeping in mind all the things we have seen so far, the code should make sense.

A Note About The Code: The code below will pass the Leetcode checks and is an Accepted solution. But, it is not super fast. It’s in fact on the slower end of accepted solutions. But as I said above, my goal was clarity and reliability.

Using BFS (in JS):

See in full screen in a new tab.

Using DFS (in JS):

See in full screen in a new tab.

Now, as you have probably seen there is almost no difference between the DFS and the BFS code except for the “stack” and the “queue” that needs to be used in the algorithms.

Conclusion

I hope that with this you feel that the number of island leet code problem has been well explained and understood.

Number of Islands – LeetCode Explained (With Animations & Visualizations)