Find Number Of Islands
You are given a 2-dimensional array/list having N rows and M columns, which is filled with ones(1) and zeroes(0). 1 signifies land, and 0 signifies water.

A cell is said to be connected to another cell, if one cell lies immediately next to the other cell, in any of the eight directions (two vertical, two horizontal, and four diagonals).

A group of connected cells having value 1 is called an island. Your task is to find the number of such islands present in the matrix.

Input Format :

The first line of input contains two integer values, 'N' and 'M', separated by a single space. They represent the 'rows' and 'columns' respectively, for the two-dimensional array/list. The second line onwards, the next 'N' lines or rows represent the ith row values. Each of the i-th row constitutes 'M' column values separated by a single space.

Output Format :

The only line of output prints the number of islands present in the 2-dimensional array.

Note :

You are not required to print anything explicitly, it has already been taken care of. Implement the function and return the desired output.

Constraints :

1

Question

Find Number Of Islands

You are given a 2-dimensional array/list having N rows and M columns, which is filled with ones(1) and zeroes(0). 1 signifies land, and 0 signifies water.

A cell is said to be connected to another cell, if one cell lies immediately next to the other cell, in any of the eight directions (two vertical, two horizontal, and four diagonals).

A group of connected cells having value 1 is called an island. Your task is to find the number of such islands present in the matrix.

Input Format :

The first line of input contains two integer values, 'N' and 'M', separated by a single space. They represent the 'rows' and 'columns' respectively, for the two-dimensional array/list.

The second line onwards, the next 'N' lines or rows represent the ith row values.

Each of the i-th row constitutes 'M' column values separated by a single space.

Output Format :

The only line of output prints the number of islands present in the 2-dimensional array.

Note :

You are not required to print anything explicitly, it has already been taken care of. Implement the function and return the desired output.

Constraints :

1 <= N <= 10^3 
1 <= M <= 10^3
0 <= ARR[i][j] <= 1

Time limit: 1sec

Accepted Answer

The problem can be easily solved by applying DFS() on each component. In each DFS() call, a component or a sub-graph is visited. We will call DFS on the next un-visited component. The number of calls to DFS() gives the number of connected components.

Accepted Answer

Flood Fill Algorithm

We can use the flood fill algorithm to check for all connected 1s.

We create two arrays, dx, and dy, in which we store the unit vectors for all eight directions. Thus, when we are at a given cell, we can easily check for all its adjacent cells by simply looping over the two arrays, adding their values to the current position, and checking for this new position recursively.
We will also create a 2D boolean array of the same size as the input array that will keep track of whether a cell has been visited. Initialize an ans variable as 0.
Iterate through the input array. For every cell that is equal to 1 and not visited, first increase ans by 1 and use the flood fill algorithm to mark that cell and every other connected cell that is equal to 1 as visited so we don't count them again
Return the ans variable

Space Complexity: O(m*n) - For 2d arraysExplanation:

O(N * M), where N and M are the dimensions of the array.

We have to maintain a boolean 2D array, which keeps track of whether a cell has been visited before or not.

Time Complexity: O(m*n) - For 2d arraysExplanation:

O(N * M), where N and M are the dimensions of the array.

Traversing each cell of the 2D array once requires O(N * M) time.