Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction 
2.
The problem statement
3.
Algorithm
3.1.
Pseudo Code
3.2.
Implementation in Java
4.
Frequently asked questions
5.
Key takeaways
Last Updated: Mar 27, 2024

Number of Islands

Author Alisha Chhabra
3 upvotes
Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

Introduction 

The challenge for today is to calculate the number of Islands in the given 2-D grid. 

The problem statement

Given an m x n 2D binary grid, a grid representing a map of '1's (land) and '0's (water) returns the number of islands.

A collection of connected 1s forms an island.

Example 1:

Input: grid = [

  ["1","1","1","1","0"],

  ["1","1","0","1","0"],

  ["1","1","0","0","0"],

  ["0","0","0","0","0"]

]

Output: 1

Explanation:

Example 2:

Input: grid = [

  ["1","1","0","0","0"],

  ["1","1","0","0","0"],

  ["0","0","1","0","0"],

  ["0","0","0","1","1"]

]

Output: 3

Explanation:


 

It is recommended to attempt the problem on your own first before moving to the solution. 

The problem is quite similar to the common problem: “Counting the number of connected components in an undirected graph.”

Before we go into the problem, let's define a connected component that will be helpful to solve the current problem:-

A component of an undirected graph is an induced subgraph in which any two vertices are connected by paths but are not connected to any other vertices in the graph. The graph in the picture, for example, contains three components. 
 

Source:- Wikipedia

Furthermore, a vertex with no incident edges is a component in and of itself. 

Let's revisit the Equivalence Relation’s discrete mathematics topic and examine how the components form a connection in a graph or other data structure.

So, a relation is an equivalence relation if it is ReflexiveSymmetric, and Transitive. If a component follows any of the properties, it is referred to as a connected component. Let's look at how:

Reflexive Property:- From any vertex to itself, there is a simple route of length zero.
 


 

Symmetric Property:- If a path exists from u to v, the same edges also exist from v to u.

 

Transitive Property:- If there are pathways from u to v and v to w, the two paths can be joined to produce a path from u to w.


 

All of the stated examples can also be referred to as the connected components as said above. 

Now how is this related to our problem?

If we concentrate on our task, we need to count the total number of 1's connected to others 1's in any way.

The idea is to apply DFS Algorithm to each component. Each DFS call visits a component or a sub-graph. We'll call DFS to the next un-visited component. The number of DFS calls represents the number of connected components.

A cell in a 2D matrix can have up to 8 neighbours. In contrast to standard DFS, which recursively calls for all neighbouring vertices, we can only recursively call for 8 neighbours here. We keep track of the visited 1s so that they do not need to be revisited.

Let’s discuss the algorithm now:

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

Algorithm

 

Step 1:- Initialize a 'count' variable as 0 to keep track of the number of islands found after each query.

Step 2:- Declare a 2D boolean array 'visited[][]' with ‘N’ rows and ‘M’ columns to keep track of the visited 1s. 

Step 3:- Create a function named numIslands() that will accept one parameter as the 2-D grid,  and inside the function, run two loops to iterate through each component on the 2-D array and check whether it has 1 or not. 

Step 3.1:- If the element isn’t explored yet and is (1), then explore its connection using the DFS call and increment the count by 1.

Step 4:- Create a function dfsTraverse() which will accept four parameters: the grid[][], row, column, and visited[][] array. 

Step 4.1:- The base case to keep the component safe from the failure cases. The program will return to the respective function call if

Row < 0 or Row == grid.length or col < 0 or col == grid[0].length or grid[row][col] == ‘0’ or visited[row][col] == true.

Step 4.1:- Otherwise, each time when it jumps to the next recursive call,

update the visited status of the particular element as TRUE. 

Step 4.2:- Make a recursive call to check for the elements Up, Down, Left, and Right for checking whether there are connected 1’s or not. 

This approach is inspired by the Flood Fill algorithm

For moving up:- col-1

For moving down:- col+1

For moving left:- row-1

For moving right:- row+1
 

Step 5:- Return count. 

Pseudo Code

public int numIslands(char[][] grid)
        Create a 2-d boolean array visited[][]
        Initialize the count variable as 0
    for(int i=0;i<grid.length;i++)
        for(int j=0;j<grid[0].length;j++)
            if(visited[i][j]==false and grid[i][j]=='1')
              DFStraverse(grid, i, j, visited)
              count++
    return count

    static void DFStraverse(char[][] grid, int row, int col , boolean visited[][])   
        if(row<0 or col <0 or row==grid.length or col == grid[0].length or grid[row][col]=='0' or visited[row][col] == true)
            return
      else 
        visited[row][col]=true
        DFStraverse(grid , row , col-1 , visited)
        DFStraverse(grid, row, col+1, visited)
        DFStraverse(grid, row-1, col, visited)
        DFStraverse(grid, row+1, col , visited)

Implementation in Java

// Java program to count the number of islands in a 2D grid
import java.util.*;
import java.lang.*;
import java.io.*;

class Islands {
    //primary function, which returns the total number of Islands
    public int numIslands(char[][] grid) {
        // boolean array of equal size of the grid to keep track of the visited or un-visited elements
        boolean visited[][] = new boolean[grid.length][grid[0].length];
        // Variable count that will hold the number of Islands
        int count = 0;
        // Loop to iterate the elements in a grid
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                // if the element is 1 and hasn't been visited yet, its adjacent vertices will be checkout using the utility function
                if (visited[i][j] == false && grid[i][j] == '1') {

                    DFStraverse(grid, i, j, visited);
                    // After the function, call count will get incremented by 1
                    count++;
                }
            }
        }
        // Returning the final count
        return count;
    }
    // Utility function to check for the element's neighbor
    static void DFStraverse(char[][] grid, int row, int col, boolean visited[][]) {
        // If any of the conditions satisfy then the return statement will be called out to the respective function call
        if (row < 0 || col < 0 || row == grid.length || col == grid[0].length || grid[row][col] == '0' || visited[row][col] == true) {
            return;
        }
        // Otherwise, update the element's status from unvisited to visited
        visited[row][col] = true;
        // Recursive call to move up
        DFStraverse(grid, row, col - 1, visited);
        // Recursive call to move down
        DFStraverse(grid, row, col + 1, visited);
        // Recursive call to move left
        DFStraverse(grid, row - 1, col, visited);
        // Recursive call to move right
        DFStraverse(grid, row + 1, col, visited);
    }
    // main function
    public static void main(String[] args) throws java.lang.Exception {
        // Scanner class to take the input from the user
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter the number of rows: ");
        int rows = sc.nextInt();
        System.out.println("Enter the number of columns: ");
        int cols = sc.nextInt();

        char grid[][] = new char[rows][cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                System.out.println("Enter [" + i + "] [" + j + "] element: ");
                // Take the character input from the user
                grid[i][j] = sc.next().charAt(0);
            }
        }
        // Create the class object
        Islands I = new Islands();
        // Printing the grid
        System.out.println("Grid:- ");
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                System.out.print(grid[i][j] + " ");
            }
            System.out.println();
        }
        // Final function call
        System.out.println("Number of islands is: " + I.numIslands(grid));
    }
}

Input Test-Case-1:-

Enter the number of rows: 
2
Enter the number of columns: 
2
Enter [0] [0] element: 
1
Enter [0] [1] element: 
0
Enter [1] [0] element: 
1
Enter [1] [1] element: 
0

Output

Grid:-
1 0
1 0
Number of islands is: 1

Explanation:-

Input Test-case-2:-

Enter the number of rows: 
2
Enter the number of columns: 
3
Enter [0] [0] element: 
1
Enter [0] [1] element: 
0
Enter [0] [2] element: 
1
Enter [1] [0] element: 
0
Enter [1] [1] element: 
1
Enter [1] [2] element: 
1

Output

Grid:- 
1 0 1 
0 1 1 
Number of islands is: 2

Explanation:-

Time Complexity: O(Row x col), Row, and col are the total number of rows and columns in the grid.

Space Complexity: O(n), where n is the total number of lands(1’s). In the worst-case scenario, O(Row x Col) if the grid map is filled with lands(1’s) where DFS runs by Row x Col deep. 

Frequently asked questions

  • What is the use of graphs in data structure?

Graphs are data structures you encounter daily via Google Search, Google Maps, GPS, and social media. They are used to depict items that are linked together. The graph's elements are known as Nodes, and the connections between them are known as Edges.

 

 

Flood fill, also known as seed fill, is an algorithm that finds and modifies the area of a multidimensional array associated with a particular node with some matching attribute.

 

  • On a graph, how does DFS work?

Depth-first search (DFS) is a method for traversing or exploring data structures such as trees or graphs. The algorithm begins at the root node (or, in the case of a graph, selects any random node as the root node) and explores as far as possible down each branch before retreating.

 

  • How does the return statement work in recursion?

A return statement returns a value to the current function's call-immediate frame's caller. This immediate caller can be another invocation of the same function in the event of recursion.

Key takeaways

To summarise the session, we took a deep dive into the problem of the Number of Islands. It’s time to have a look at the other problems and boost the power of problem-solving. 

Similar Problems that you can look upon:-

Flood Fill AlgorithmNumber of IslandsKosaraju’s AlgorithmGet DFS path.

The finest advice anyone can provide is to solve all code problems with pen and paper. Make it a practice to run your code through a dry run. 

Furthermore, With Coding Ninjas Studio as your toolset, you are now ready to go on your quest to join your ideal firm. While Coding Ninjas Studio can equip you with all you need, your perseverance and hard work will propel you to success.

Continue to study and improve!
 

Previous article
Difference between the shortest and second shortest path in an Unweighted Bidirectional Graph
Next article
Find the number of islands
Live masterclass