Code 101: Number of Islands

Question:

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.

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

You can find the question here.

Solution:

We have given an 2d array, and asked to find number of islands.

What all things can we deduce from the question

1. To count the island we need to check where the land end.
2. All the grid boundaries are considered water.

With this information can we say that we need to traverse the whole array to check where the land is and where the water is?

Also, can we say that whenever we see 1 can we consider it as an Island?

Note: This assumption will count all the '1' as islands.

Will break the answer into smaller parts.

Based on the understanding till now.

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

With this, we have reached half of the solution but we know that we are counting all the 1 as islands and that is wrong.

So let's say we are standing on a square in a grid and we count that as an island and now wherever you see land attached to the 1 you are standing, consider it as water.

Will doing this solve your duplicate counting problem? Because anyway we are iterating the whole grid, so every time while iterating through the grid we encounter a 1, count it as an island, and mark all the connected land as the water we are good.

Also, we don't want to do anything when we see water.

Now to code our understanding.

public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) return 0;
        int noOfIslands = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    noOfIslands++;
                    flippingTheContIslands(grid, i, j);
                }
            }
        }
        return noOfIslands;
}
    
public void flippingTheContIslands(char[][] grid, int i, int j) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0' ) {
            return;
        }
        grid[i][j] = '0';
        flippingTheContIslands(grid, i+1, j);
        flippingTheContIslands(grid, i, j+1);
        flippingTheContIslands(grid, i-1, j);
        flippingTheContIslands(grid, i, j-1);
}

Hope you understood the solution.

#HappyCoding