Time: 4 ms (50.69%), Space: 52.2 MB (14.89%) - LeetHub

py3-coder · py3-coder · commit 5196abe5699c · 2024-11-30T16:20:31.000+05:30
diff --git a/0200-number-of-islands/0200-number-of-islands.java b/0200-number-of-islands/0200-number-of-islands.java
@@ -1,51 +1,35 @@
 class Solution {
-    public int numIslands(char[][] grid){
-        int n=grid.length;
-        int m=grid[0].length;
-		int[][] vis =new int[n][m];
-		int cnt=0;
-		for(int i=0;i<n;i++){
-			for(int j=0;j<m;j++){
-				if(grid[i][j]=='1' && vis[i][j]!=1){
-					cnt++;
-					bfs(i,j,vis,grid);
-				}
-			}
-		}
-		return cnt;
-
-	}
-	public static void bfs(int row,int col,int[][] vis,char[][] grid){
-		int n=grid.length;
-        int m=grid[0].length;
-		Queue<Pair> que = new LinkedList<>();
-		que.offer(new Pair(row,col));
-
-		int drow[] ={0,1,0,-1};
-		int dcol[] ={1,0,-1,0};
-
-		while(!que.isEmpty()){
-			Pair pp =que.poll();
-			int r =pp.val1;
-			int c=pp.val2;
-			for(int i=0;i<4;i++){
-				int nrow =r+drow[i];
-				int ncol =c+dcol[i];
-				if(nrow>=0 && nrow<n && ncol>=0 && ncol<m && vis[nrow][ncol]!=1 && grid[nrow][ncol]=='1'){
-					que.offer(new Pair(nrow,ncol));
-					vis[nrow][ncol]=1;
-				}
-			}
-		}
-		return ;
-	}
-	static class Pair{
-		int val1;
-		int val2;
-
-		Pair(int _val1,int _val2){
-			this.val1=_val1;
-			this.val2=_val2;
-		}
-	}
+    public int numIslands(char[][] grid) {
+        int n = grid.length , m = grid[0].length;
+        int cnt =0;
+        int[][] vis = new int[n][m];
+        
+        for(int i=0;i<n;i++){
+            for(int j=0;j<m;j++){
+                if(grid[i][j]=='1' && vis[i][j]!=1){
+                    cnt++;
+                    dfs(i,j,grid,vis);
+                }
+            }
+        }
+        return cnt;
+        
+        
+        
+    }
+    public void dfs(int x , int y, char[][] grid, int[][] vis){
+        int n = grid.length , m = grid[0].length;
+        int[] dx ={0,-1,0,1};
+        int[] dy ={1,0,-1,0};
+        vis[x][y]=1;
+        for(int i=0;i<4;i++){
+            int nx =x+dx[i];
+            int ny =y+dy[i];
+            
+            if(nx>=0 && ny>=0 && nx<n && ny<m && grid[nx][ny]!='0' && vis[nx][ny]!=1){
+                dfs(nx,ny,grid,vis);
+            }
+        }
+        
+    }
 }
