The problem requires counting the number of islands in a 2D grid. An island is
represented by '1's (land) and is
surrounded by '0's (water). The key
idea is to traverse the grid and use
Depth-First Search (DFS)
to explore all
connected land cells
starting from an
unvisited '1'.
Each DFS call marks all reachable land cells as visited, ensuring they are not counted
again.
Further, we use a
visited matrix
to keep track of visited cells. For each
unvisited '1', we
increment the island count
and perform DFS to mark
all connected land cells.
class Solution { public void dfs(char[][] grid,boolean[][] vis ,int sr, int sc){ if(sr>=grid.length || sr<0 || sc>=grid[0].length || sc<0 || grid[sr][sc]=='0' || vis[sr][sc]==true) return; // Traverse in all four directions vis[sr][sc]=true; dfs(grid,vis,sr+1,sc); dfs(grid,vis,sr-1,sc); dfs(grid,vis,sr,sc+1); dfs(grid,vis,sr,sc-1); } // Basically, we are counting number of connected components public int numIslands(char[][] grid) { int row = grid.length; int col = grid[0].length; boolean[][] vis = new boolean[row][col]; int noOfIslands = 0; for(int i=0;i<row;i++){ for(int j=0;j<col;j++){ // If it is land and it is not visited then visit it. if(grid[i][j]=='1' && vis[i][j]==false){ dfs(grid,vis,i,j); noOfIslands++; } } } return noOfIslands; } }
The algorithm visits each cell in the grid once, where 'n'
is the number of rows and 'm' is the number of
columns.
The algorithm uses a visited matrix of
size
n * m to keep
track of visited cells, where 'n'
is the number of rows and 'm' is the number of
columns.