Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Example
4.
Approach and Explanation
5.
Java Implementation
6.
Complexities
6.1.
Time Complexity
6.2.
Space Complexity
7.
Frequently Asked Questions
8.
Key Takeaways
Last Updated: Mar 27, 2024

Find the number of islands

Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

Introduction

In this article, we will discuss how to find the number of islands in a given 2D matrix containing the positions of land and water. We shall do so by performing Depth First Search(DFS). Concepts like Recursion and Graph Traversal have also been used in this article.
Readers with no prior knowledge of these concepts may visit the given links to understand the same better.

Problem Statement

You are provided with a 2D matrix representing a map (containing 1s and 0s). The 1s represent land, and the 0s represent water. Your task is to find the number of islands. 
An island is a land or a group of lands surrounded by water. The lands can be connected horizontally, vertically, or diagonally.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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!

Previous article
Number of Islands
Next article
Find Number of Islands
Live masterclass