Solution Developed In:

The Question

For this article we will be covering Leetcode's '200. Number of Islands' question.

Question:

Given an m x n 2D binary grid 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 all surrounded by water.
Example:

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

Explaining The Question

This Question is rated Medium. Which is for the most part accurate. But this is ONLY Medium if you have a good grasp of Depth First Search or Breadth First Search on Graph Theory. Ideally a solid understanding of the Adjacency List and Adjacency Matrix will be helpful.

What we're dealing with here is a Graph with Nodes and Edges which are represented by a M x N 2D Array. Where the relationship between the nodes are by the edges that connect them. That's to say a nodes neighbors are the nodes that are adjacent to it. Meaning, left, right, top, and bottom are the neighbors.

We need to traverse this Graph and count the number of islands. So we're going to traverse this Graph and count the number of islands.

Recommended Knowledge

1. Graph Theory
2. Adjacency List
3. Adjacency Matrix
4. Depth First Search
5. Sets

What do we know?

1. We have a 2D Array of '1's and '0's.
2. It's a M x N Matrix
3. Neighbors are left, right, top, and bottom.
4. We need to find the number of islands.

How we're going to do it:

What we're going to do is traverse each node in the Graph and at each node we're going to check if it's a land or water. In the case of land we're going to perform a Depth First Search. Where we will traverse the entire island all together. Each time we visit a little bit of land, we could add it to a set but in our case, we will just turn this land into water as to not count it again.

Each time we fully complete our Depth First Search, we'll add 1 to our count as we have totally traversed and removed that island.

1. We're going to declare a global variable called number_of_islands which will keep track of the number of islands we're going to visit.
2. We're going to visit every node in the matrix, by iterating through each row and each column.
3. At each node we ask if it's a land or water. 1 or 0. If 0, we've either already visited it / just water.
4. If 1, we've found un-explored land and we need to traverse that entire island.
5. We perform a Recursive Depth First Search on that island. Where we ask recursively if the node above, below, left and right is a 1 or not? If any of those are 1, we visit it and continue the DFS until we have exhausted the island.
6. Now the island is fully explored and we can add 1 to our count.
7. Continue to do this until we have traversed all the nodes in the matrix.

Big O Notation:

• Time Complexity: O(n) | Where n is the number of nodes in the Matrix. As we're going to visit every node in the matrix. Although this could be argued to be O(x * m) where x is the number of rows and m is the number of columns as in the worst case, we will need to visit every node in the matrix multiple times due to a high number of islands.
• Space Complexity: O(h) | Where h is the largest number of nodes within a island, as we will store all of those nodes within the Call Stack to perform our Depth First Search.

The Big O Notation analysis for this problem is a little confusing as it combines a handful of different concepts all with their own Big O Notations. But in general, we reduce it down to the worst complexity being O(n). Feel free to correct me if you feel my analysis is wrong.

Leetcode Results:

See Submission Link:

• Runtime: 88 ms, faster than 85.83% of JavaScript online submissions for Number of Islands
• Memory Usage: 43.8 MB, less than 99.91% of JavaScript online submissions for Number of Islands.

The Solution

var numIslands = function (grid) {

    // Pretty much, we're going to go
    // over each row and each column within the matrix / graph
    // and each time we reach a potential island, we perform a dfs / bfs
    // So we can skip island nodes we have already visited. As they will become water.
    // Once we have explored the entire island, we increment
    // our number of island count.

    let   number_of_islands = 0;
    const num_rows          = grid.length - 1;
    const num_cols          = grid[0].length - 1;

    // This runs DFS
    // Checking our indexes are within the correct bounds
    // Getting the
    // top, left, right, bottom
    // nodes
    const depth_first_search = (row_index, col_index) => {
        // Firstly is the given indexs within range?
        // Cannot be greater than the greatest and cannot be negative. I honestly wish we had a better way of doing this.
        if (row_index > num_rows || col_index > num_cols || row_index < 0 || col_index < 0) {
            return;
        }

        const node = grid[row_index][col_index];

        // So the node is valid, have we been here before?
        // and is it an island node?
        if (node === "0") {
            return;
        }

        // Right, so this is a valid node, let's index it.
        // We do this making it water, meaning, we don't need to explore it any longer
        grid[row_index][col_index] = "0";

        // Go up
        depth_first_search(row_index - 1, col_index);

        // Go down
        depth_first_search(row_index + 1, col_index);

        // Go right
        depth_first_search(row_index, col_index + 1);

        // Go left
        depth_first_search(row_index, col_index - 1);
    };

    // For each row, and column, check if the node
    // is a `1` and if it is we perform a DFS on that island,
    // which will run until that entire island has been explored.
    // Where for each 1 we find we remove it from the grid, so we don't need to check it again.
    // at which point we increment our island counter.
    grid.forEach((row, row_index) => {
        row.forEach((col, col_index) => {
            // Is this a island and we haven't been here before?
            // EXPLORE IT!!
            if (col === "1") {
                // Perform a DFS, which will automatically index this node
                depth_first_search(row_index, col_index);

                // Now we have explored this entire island
                // increment our counter
                number_of_islands += 1;
            }
        });
    });

    return number_of_islands;
};