LeetCode Walkthrough: Number of Islands

Aerial view of The Bahamas

Picture yourself flying over the Bahamas, on your way to a much-needed vacation (I could use one now). You look out your window and see the Sapphire blue waters below, specks of green begin to materialize and grow. As a human, you quickly notice that what you’re looking at is the Islands known as The Bahamas, you can even count how many islands are visible in a matter of seconds. On the other hand, a computer wouldn’t be able to recognize the islands just as easily as our brains make it out to be. It would need a software program to distinguish an island from the rest of the pack. A high-level implementation of that program is what we’ll discuss in the rest of this article. Buckle in and enjoy your flight!

Understanding the problem from a coding perspective

No, we’re not gonna dive into computer vision and image processing, as fun as that would be. Instead, we’ll go over a simple, understandable implementation from LeetCode; arguably the best platform to help you enhance your skills, expand your knowledge and prepare for technical interviews.

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.

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

In the above example, we only have one huge island, denoted by 1’s. If we think of 0’s as water and 1’s as the land it’s much easier to visualize. As long as 1’s are connected vertically or horizontally, they don't form new islands but make the current one larger instead. Even a single 1 that is not connected to another island vertically or horizontally forms an island.

Let’s look at one more example:

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

We can see in the grid above, that there are three different islands, first in the top left, second in the center, and third in the bottom right.

Now that we understand the problem, let’s get to coding!

Breaking down a coding solution

Building our main function

Essentially, the task of the main function is straightforward. We want to iterate our m x n array and count for groups of horizontally or vertically connected 1s. Then we just return our count.

public int numIslands(char[][] grid) {
        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == '1') {
                    search(grid, i, j);
                    count++;
                }
            }
        }
        return count;
    }

So we are dealing with chars, rather than Integers (I don’t know why but that’s the way LeetCode has it), keep that in mind.

Firstly, we create an integer variable, count, to store our count of islands as we navigate the array.

Secondly, we iterate the array and search for cells that contain a 1, this means that we have encountered an island. What we want to do at this point is call our helper function, search, to help search how big this island is. We will pass the array and indexes for our current location onto our function. Search will ensure that we don’t count the same island twice, we will get to that soon.

Thirdly, whenever we encounter a 1, we want to increment the count because we have just stumbled on a new island.

Finally, when all is said and done, we want to return our count of islands.

Building our helper function

I believe it’s much easier to solve a problem when the skeleton has been laid out, that is what we have done here. We know what we are doing and now we’ve narrowed down what we have to do to make our program successful.

For our helper function search, our main goal is to distinguish one island from another. How can we do this? The answer is simpler than it seems. We will just destroy the island completely! Every group of 1’s that is connected to our current island will be converted back to water (0) including the starting point. This ensures that we don’t count the same island twice as we iterate through our array.

void search(char grid[][],int i, int j){
        if(i < 0 || j <0 || i > grid.length-1 || j > grid[i].length-1|| grid[i][j]!='1') return;
        grid[i][j]='0';
        search(grid,i-1,j);
        search(grid,i,j-1);
        search(grid,i+1,j);
        search(grid,i,j+1);
    }

There’s a series of base cases we have to consider with each call of search.

Firstly, we have to make sure that our indexes fall within the grid. We don’t have complete control over the indexes because we are recursively searching the grid for 1s that are either connected vertically or horizontally. Eventually, we will reach the end of the grid and we should be prepared for that. If these base cases fail, we should return because we have reached the end of the grid. (An index ≤ 0 or ≥ array.length will fall out of bounds!)

Secondly, we can only do this after our indexes have been verified, otherwise, we’ll receive an IndexOutOfBoundsException. If the current cell we are on is not land (1) then we have reached the end of the island and need to stop searching.

If we have passed our base cases, then we’re on valid land and need to do the following:

Firstly, set the current cell of land (1) equal to water (0). This will prevent us from recounting the same piece of land again, should we stumble upon it through our iteration.

Secondly, recursively search all horizontal and vertically connected cells. We already know what our search function will do; set connected pieces of land back to water and end our search when there’s no more land left.

And that’s it! We did it! Let’s see what our full program looks like.

Time Complexity: O(m x n) where m is the number of rows and n is the number of columns in our grid.

Space Complexity: O(1)

The main takeaway from all this is that it’s much easier to solve a problem when you break it down. By creating an outline of what we wanted and writing the main function first, we were able to narrow down the problem into a much smaller task.

Wow, if you made it this far then that means I haven’t bored you to death! Thank you for reading my article. Feel free to add a comment and follow me if you like the content.