\
## 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:**

\
```javascript
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:**

\
```javascript
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](https://miro.medium.com/max/284/1\*mhSJpnmz7YidM2wBzaS9Jw.png)

\
 ![Visualization of the second example](https://miro.medium.com/max/284/1\*XUoVaKh_-HuH4sFcR_vzWw.png)

\
\
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](https://miro.medium.com/max/596/1\*4T2rYZQ3okZFbF3L2c1qKQ.png)

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

\
 ![Empty grid or grid with 0 islands](https://miro.medium.com/max/334/1\*30D9MvLKMPqZfKdGuaxrkg.png)

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

\
 ![Grid with 7 islands](https://miro.medium.com/max/336/1\*jz4Be5GOa_13WVpCIkBoGQ.png)

\
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](https://miro.medium.com/max/336/1\*tYNZIsy4kNm7pXVlK8n-eg.png)

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

\
```java
    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.

\
```java
    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:

\
```java

    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](https://miro.medium.com/max/330/1\*kfwuGOgGG7CMr8Sil9tO6g.png)

\
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](https://miro.medium.com/max/1244/1\*dIvThN_V_s6KsDb-tpX_Ow.png)

\
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](https://levelup.gitconnected.com/number-of-islands-blind-75-leetcode-questions-4a0eb41fb21d).

2022 - HackerNoon Contributor of the Year - Algorithms

2022 - HackerNoon Contributor of the Year - Coding

2022 - HackerNoon Contributor of the Year - Java

Nominated for 2022 - HackerNoon Contributor of the Year - Algorithms

Nominated for 2022 - HackerNoon Contributor of the Year - Java

Nominated for 2022 - HackerNoon Contributor of the Year - Coding

Too Long; Didn't Read

Cassandra Forward a free Cassandra-focused community event

How to Solve Number of Islands From Blind 75 LeetCode Questions

Too Long; Didn't Read

@rakhmedovrs

RELATED STORIES