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