How to Solve Number of Islands From Blind 75 LeetCode Questionsby@rakhmedovrs
89,091 reads

How to Solve Number of Islands From Blind 75 LeetCode Questions

August 20th 2022
7 min
by @rakhmedovrs 89,091 reads
tldt arrow
EN
Read on Terminal Reader

Too Long; Didn't Read

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.
featured image - How to Solve Number of Islands From Blind 75 LeetCode Questions
Ruslan Rakhmedov HackerNoon profile picture

@rakhmedovrs

Ruslan Rakhmedov

Learn More
LEARN MORE ABOUT @RAKHMEDOVRS'S EXPERTISE AND PLACE ON THE INTERNET.
react to story with heart


Task description:

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 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


Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 300
  • grid[i][j] is '0' or '1'.


Reasoning:

At first, the task seems to be hard, except you already know what to do after seeing this problem before. We don’t consider that scenario here, let’s treat the problem as if we see it for the first time. To make it easier to understand, let’s use a more comprehensive way of describing the problem. I’m going to use a simple table in which blue cells will be representing water and green cells will represent land. 0 in the given grid represents water, and 1 represents the land. Let’s visualize the examples we are given:


Visualization of the first example

Visualization of the first example


Visualization of the second example

Visualization of the second example



The answer for the first grid is 1, whereas the second one is 3. The reason for that is — land must be connected vertically or horizontally. Let’s visualize this as well.


The Left grid has 1 island, and the right one has 5

The Left grid has 1 island, and the right one has 5


As I always do, I suggest you start from extremely simple examples, foolish if you will.


Empty grid or grid with 0 islands

Empty grid or grid with 0 islands


The example above doesn’t have any land, so the answer is 0 island.


Grid with 7 islands

Grid with 7 islands


The example above has 7 islands. How can we programmatically say that? We need to iterate through the entire grid and count how many times we see land. That is all. Sounds easy, right? But let’s take another example:


Grid with 6 islands

Grid with 6 islands


If we use the same logic as we did in previous examples, we get the answer 8, but it is the wrong one. The correct answer is 6 islands. The main drawback of the previous approach is that we count every piece of land, not the islands. Turns out it’s the main problem we need to solve in order to solve the given problem.



Solution:

The general approach consists of 2 general steps.


The first step is we need to iterate through the entire grid cell by cell. There’s no way we can answer the main question without doing it.


    public int numIslands(char[][] grid)
    {
        if (grid == null || grid.length == 0)
        {
            return 0;
        }

        int islands = 0;
        for (int row = 0; row < grid.length; row++)
        {
            for (int column = 0; column < grid[row].length; column++)
            {
                if (grid[row][column] == '1')
                {
                    islands += //some logic here
                }
            }
        }

        return islands;
    }


We start from the top left corner and iterate through each row, when we cannot proceed, we jump to the next row.


It’s time to discuss the logic behind how we calculate how many islands we have. By now it should become obvious that we start by exploring the first piece of any island. We add it to the answer as 1 island we just explored. The next thing we need to do is to prevent attached pieces of land from being counted, as we already incremented the general counter. How we can do it?


The answer is simple. Let’s ERASE it. Yes, you got it right. Once we discover the first piece of land, we start erasing procedure.


    private int eraseLand(char[][] grid, int row, int column)
    {
        if (row < 0 || column < 0 || row >= grid.length || column >= grid[row].length || grid[row][column] == '0')
        {
            return 0;
        }

        grid[row][column] = '0';

        // going up
        eraseLand(grid, row - 1, column);
        
        // going down
        eraseLand(grid, row + 1, column);
        
        // going left
        eraseLand(grid, row, column - 1);
        
        // going right
        eraseLand(grid, row, column + 1);

        return 1;
    }


For each cell, we erase its land by setting the value of the cell to be 0, and from that cell, we continue exploring the grid by going left, right, up, and down. Eventually, we’ll explore all the attached pieces of land.


Here’s the full source code of the solution:



    public int numIslands(char[][] grid)
    {
        if (grid == null || grid.length == 0)
        {
            return 0;
        }

        int islands = 0;
        for (int row = 0; row < grid.length; row++)
        {
            for (int column = 0; column < grid[row].length; column++)
            {
                if (grid[row][column] == '1')
                {
                    islands += eraseLand(grid, row, column);
                }
            }
        }

        return islands;
    }

    private int eraseLand(char[][] grid, int row, int column)
    {
        if (row < 0 || column < 0 || row >= grid.length || column >= grid[row].length || grid[row][column] == '0')
        {
            return 0;
        }

        grid[row][column] = '0';

        // going up
        eraseLand(grid, row - 1, column);
        
        // going down
        eraseLand(grid, row + 1, column);
        
        // going left
        eraseLand(grid, row, column - 1);
        
        // going right
        eraseLand(grid, row, column + 1);

        return 1;
    }


As I mentioned above, we must explore the entire grid, it costs O(rows * columns) + if we consider the worst-case scenario like this one:


Worst case scenario

Worst case scenario


We’ll explore the entire grid one more time with the same time complexity of O(rows * columns). So overall time complexity is O(rows * columns) + O(rows * columns). By rules of big O notation, we can omit one part and the resulting time complexity is O(rows * columns).


Performance of the solution

Performance of the solution


I hope this article will help you to understand the logic behind this problem and use it to solve other tasks.


See you soon!



Also published here.

RELATED STORIES

L O A D I N G
. . . comments & more!
Hackernoon hq - po box 2206, edwards, colorado 81632, usa