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.lengthn == grid[i].length1 <= m, n <= 300grid[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:
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.
As I always do, I suggest you start from extremely simple examples, foolish if you will.
The example above doesn’t have any land, so the answer is 0 island.
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:
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:
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).
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.