Efficient Island Counting Using DFS Traversal
Time complexity: O(M∗N) due to grid traversal. Space complexity: O(M∗N) for visited array. Solution uses depth-first search (DFS) traversal of the matrix/graph.
Problem
Time complexity:
O(M∗N)O(M*N)O(M∗N)
, since we are traversing all the cell in the grid
Space complexity:
O(M∗N)O(M*N)O(M∗N)
, for using additional visited[][] arary
Solution using depth first search traversal of the matrix/graph
class Solution {
public int numIslands(char[][] grid) {
//we can use depth first search for this
int visited[][] = new int[grid.length][grid[0].length];
int count =0;
for(int i =0;i<grid.length;i++){
for(int j =0;j<grid[0].length;j++){
if(grid[i][j] =='1' && visited[i][j] ==0){...