This is the Problem on Leetcode https://leetcode.com/problems/number-of-islands/description/

Tags > DFS | BFS | Union-find

This question asked in the companies like amazon | facebook | google | microsoft | zenefits

Problem

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 :

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

Constraints:

• m == grid.length

• n == grid[i].length

• 1 <= m, n <= 300

• grid[i][j] is '0' or '1'.

Solution

Intuition

If you leave an insect inside a grid it'll only go to land i.e., grid[i][j]=='1' or it'll sink.

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

The below diagram is the representation of the above grid 2D matrix.

grid[i][j] == "1" -> Land

grid[i][j] == "0" -> Water

And the insect can move only in 4 give direction as per the problem statement.

The directions are:
UP : j+1
DOWN : j-1
RIGHT : i+1
LEFT : i-1
All the movement of insect happens in the helper() function.
Adding of insect done in numIslands() function.
The minimum number of bug required to cover whole land grid[i][j]=='1'.

Another visited array of same size of grid, I took that reminds in which cell the insect is added.

It's kind of funny, the approach I followed to solve this problems.

For above grid the solution will be :-

Approach

Then I took a visited array to know which land cell is left to visit.
And then I applied DFS on each cell following the conditions

1. the cell should shouldn't be revisited

2. and the cell must be land then only grid[i][j]=='1'.

As I mentioned before all the movement of the bug will be in the helper function so we can't go out of the grid, so I applied the condition

if( i<0 || i>=grid.length || j<0 || j>=grid[0].length)       return ;

And insect must not go in the visited cell and water cell, so

if(grid[i][j]=='0'|| visited[i][j])     return;

CODE

class Solution {
    int count= 0;
    public int numIslands(char[][] grid) {
        int row = grid.length, col = grid[0].length;
        boolean[][] visited = new boolean[row][col];
        for(int i=0;i<row;i++)
            for(int j=0;j<col;j++)
                if(!visited[i][j] && grid[i][j]=='1'){
                    count++;
                    helper(i,j, visited, grid);
                }

        return count;
    }
    void helper(int i, int j,boolean[][] visited, char[][] grid){
        //Out of bount condition
        if( i<0 || i>=grid.length || j<0 || j>=grid[0].length)
            return ;
        // Island bound
        if(grid[i][j]=='0'|| visited[i][j]) return;

        visited[i][j]= true;
        helper(i+1,j, visited, grid);
        helper(i-1,j, visited, grid);
        helper(i,j+1, visited, grid);
        helper(i,j-1, visited, grid);
    }
}

Hope you understand this solution. Please like it.

Check out my Portfolio Link

If you have any suggestions drop them in the comments.