Find the number of islands

Example

Consider the given input:

Sample Input 

{  
	          { 0, 1, 0, 1, 0 },
                    { 1, 0, 0, 0, 0 },
                    { 0, 0, 1, 0, 1 },
                    { 1, 0, 0, 1, 0 },
                    { 1, 0, 1, 0, 1 }
  }

The different groups of lands that make valid islands are shown below:

Expected Output: The total number of Islands is: 4
 

Recommended: Try to solve the problem Find Number Of Islands on  Coding Ninjas Studio before heading to the approach and solution code. 

Approach and Explanation

The solution to our problem is simple. We have to check if each cell is 1 or not. If it is 1, then check its surrounding eight cells to find the presence of other 1s. To do so, we will be using a graph traversal technique called DFS Algorithm.

The step-by-step implementation is as follows:

1. Declare a function (say numberOfIslands()) that will take the input matrix as an argument. This function will traverse the given matrix to find the number of islands.
   
   
   1. Inside this function, create a 2D array (say visited[][]). This will mark which cell has already been visited. Also, create a counter variable (say count) that will maintain the count of the islands. 
       
   2. Then using a nested for loop, check for each cell if it is a  land and has been visited or not.
      1. If it is a land and has not been visited yet, perform DFS on that cell and increment the value of count by one.
      2. In any other case, just move ahead to traverse other cells in the matrix.
          
   3. Once both the for loops have exhausted, return count.
       
2. Declare a function (say DFSTraversal()) that will perform the DFS operation and help us recursively find the groups of lands. 
   The function takes the given matrix, the current row, and column, and the array visited[][] as arguments. 
   
   
   1. Set the value of visited TRUE for the current row and column. 
       
   2. To find if the land i.e. matrix[row][col] is connected to other lands or not, we create two new 1D arrays (say rows[] and cols[]).
      1. The values of these matrices is initialized as rows[]={-1, -1, -1, 0, 0, 1, 1, 1} and cols[]={ -1, 0, 1, -1, 1, -1, 0, 1 }.
          
   3.  For each of the valid eight directions, perform DFS.  
      1. Check (using the checkSafe() function) if the adjacent cells are valid land or not. 
      2. If true, then perform recursion on those lands.
          
3. Declare a function (say checkSafe()) that will check whether the given cell is a valid land or not. It takes the given matrix, row, and column and visited[][] as arguments. 
   The function returns a boolean value.
   
   
   1. Inside the function, we check and return the following:
      1. If the values of row and column are greater than or equal to zero, and
      2. If the values of row and column are less than the maximum ROW and COL value, and
      3. If the value of the cell at arr[row][col] is a land, and
      4. If that cell has not been visited yet.
          
   2. We return true or false depending on all these conditions.
       
4. Create the input matrix consisting of the 1s and 0s. The number of rows and columns is set as ROWS and COLS and they don’t change throughout the execution.
    
5. Create an object of the class, call the function numberOfIslands() and pass the given array. Finally, print the desired output.

Java Implementation

public class CountIslands {

  static final int ROWS = 5, COLS = 5;

  boolean checkSafe(int[][] M, int row, int col, boolean[][] visited)
  {
      return (row >= 0) && (row < ROWS) && (col >= 0) && (col < COLS) && (M[row][col] == 1 && !visited[row][col]);
  }

  void DFSTraversal(int[][] M, int row, int col, boolean[][] visited)
  {
      int[] rows = new int[] { -1, -1, -1, 0, 0, 1, 1, 1 };
      int[] cols = new int[] { -1, 0, 1, -1, 1, -1, 0, 1 };

      visited[row][col] = true;

      for (int k = 0; k < 8; ++k)
          if (checkSafe(M, row + rows[k], col + cols[k], visited)) {
              DFSTraversal(M, row + rows[k], col + cols[k], visited);
          }
  }

  int numberOfIslands(int[][] M)
  {
      boolean[][] visited = new boolean[ROWS][COLS];

      int count = 0;
      for (int i = 0; i < ROWS; ++i)
          for (int j = 0; j < COLS; ++j)
              if (M[i][j] == 1 && !visited[i][j])
              {
                  DFSTraversal(M, i, j, visited);
                  count++;
              }

      return count;
  }

  public static void main(String[] args)
  {
      int[][] islands = new int[][] { { 0, 1, 0, 1, 0 },
                                      { 1, 0, 0, 0, 0 },
                                      { 0, 0, 1, 0, 1 },
                                      { 1, 0, 0, 1, 0 },
                                      { 1, 0, 1, 0, 1 }
                                    };

      CountIslands islands1 = new CountIslands();
      System.out.println("The total number of Islands is: " + islands1.numberOfIslands(islands));
  }
}

OUTPUT

The total number of Islands is: 4

Complexities

Time Complexity

We traverse the whole 2D array in the given implementation to perform DFS. We traverse each cell at least once so we will have to perform (ROWS*COLS) operations. Thus, the time complexity comes out to be:

T(n) = O(ROWS * COLS), 

where ROWS is the number of rows and COLS is the number of columns.

Space Complexity

In the given implementation, we perform recursive operations for DFS. Also, we use extra space for a visited array of size ROWS*COLS.

Thus,

Space Complexity = O(ROWS * COLS), 

where ROWS is the number of rows and COLS is the number of columns.

Frequently Asked Questions

1. What does DFS mean?
    Depth First Search(DFS) is a graph traversal technique in which we traverse as far as possible from the source vertex before exploring a new vertex.
    
2. What are the other ways to solve this problem?
   Another approach for solving this problem would be using Breadth-First Search(BFS) instead of DFS. As a practice, you can try it out yourself from here: Find Number Of Islands.

Key Takeaways

To summarize the article, we learned how to find the number of islands in a given 2D matrix. We first saw the problem statement and an example. We saw an approach and its JAVA implementation followed by the time and space complexity. To sum it up, we discussed a few FAQs.
 

Want to improve your coding skills? Start practicing problems of various difficulty levels on our Coding Ninjas Studio today.
 

Learn about various topics like Web Technologies, Programing Fundamentals, Aptitude, DSA, and much more from our CN Library | Free Online Coding Resources. 
 

Happy Coding!