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));
}
}
You can also try this code with Online Java Compiler
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 Algorithm, Number of Islands, Kosaraju’s Algorithm, Get 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!
84+ registered 