# 2D Array: Find the no of islands in a given 2 dimensional array

Program to find the no of islands in a given 2d array/ matrix

In a 2d matrix we have 1's representing land and 0's representing water. We want to count the no of islands.

An island(1's) will be surrounded by water(0's). If a 1 is adjacent to another 1 horizontally or vertically (not diagonally)

then they both form single island and not two different island. All four edges of the grid are surrounded

by water which is 0's.

Example 1

```
1, 1, 0, 1
0, 0, 0, 1
1, 1, 0, 0
0, 0, 0, 1
```

Answer: Island Count: 4

##### Intuition

An island is a connected set of 1s. So if we visit a cell with 1, then we can do a dfs to visit all of its

adjacent cells with 1. This will form one island, and then all the 1s in the island will be marked as visited.

So in order to count the total no of islands, we only have to count the number of times we can run dfs

till all the cells with 1 are marked as visited.

##### Complexity

Time Complexity: O(N * N)

Space Complexity: O(N * N)

Where the given grid is N*N

The Time Complexity of the given problem is O(N * N) as every cell is visited once

The Space Complexity is O(N*N) as we are storing the visited values of each cell in a 2D array of size N*N

##### Java Code

` ````
class FindNoOfIsland{
// Function which marks the current cell as visited and calls its neighboring unvisited
// cells
public static void dfs(int row, int col, boolean[][] visited, int[][] graph) {
// Mark the current cell as visited
visited[row][col] = true;
// Run dfs for all the neighboring nodes
// x and y represents the movement of ith direction
int[] x = {1,-1,0,0};
int[] y = {0,0,1,-1};
// Loop through all the four direction using the x and y array
for (int i = 0; i < 4; i++) {
int neighborRow = row + x[i];
int neighborCol = col + y[i];
// Check if the neighbor row and cell is valid and it is not visited
if(
neighborRow >= 0 && neighborRow < graph.length &&
neighborCol >= 0 && neighborCol < graph[0].length &&
graph[neighborRow][neighborCol] == 1 &&
!visited[neighborRow][neighborCol]
){
// Calling the dfs function for the neighboring cells
dfs(neighborRow, neighborCol, visited, graph);
}
}
}
public static void main(String[] args) {
// Given a n*n matrix, find the number islands made with 1
// In the below example there are 4 islands in the graph
int n = 4;
int[][] graph = {
{ 1, 1, 0, 1 },
{ 0, 0, 0, 1 },
{ 1, 1, 0, 0 },
{ 0, 0, 0, 1 }
};
// An array of boolean having default value as false
// It is used to keep track of the visited cells
boolean[][] visited = new boolean[n][n];
// Variable to keep track of the island count
int isLandCount = 0;
// Iterating through every cell in the graph
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (graph[i][j] == 1 && !visited[i][j]) {
// For every cell which is 1 and is not visited, increment the dfs marks
// all the connected cell as visited the isLandCount
isLandCount++;
// We run dfs from the (i,j) cell
// All the connected cells will be marked as visited and will not be
// counted as island
dfs(i, j, visited, graph);
}
}
}
System.out.println("Island Count: " + isLandCount);
}
}
```

##### Output

Island Count: 4