Time: 3 ms (14.85%), Space: 42.5 MB (31.81%) - LeetHub

py3-coder · py3-coder · commit c4d8a3c28611 · 2024-11-23T11:06:09.000+05:30
diff --git a/0994-rotting-oranges/0994-rotting-oranges.java b/0994-rotting-oranges/0994-rotting-oranges.java
@@ -1,63 +1,44 @@
 class Solution {
     public int orangesRotting(int[][] grid) {
-        int n  = grid.length;
-        int m =  grid[0].length;
         
-        int[][] vis = new int[n+1][m+1];
-        int max =0;
-        Queue<Triple> que = new LinkedList<>();
-        for(int i=0;i<n;i++){
-            for(int j=0;j<m;j++){
+        //adjacency list ::
+        Queue<List<Integer>> que = new LinkedList<>();
+        
+        for(int i=0;i<grid.length;i++){
+            for(int j=0;j<grid[0].length;j++){
                 if(grid[i][j]==2){
-                    que.offer(new Triple(i,j,0));
-                    vis[i][j]=1;  
+                    que.offer(new ArrayList<>(Arrays.asList(i, j, 0)));
                 }
             }
         }
-        max =bfs(que,vis,grid);
-        //check ::
-        for(int i=0;i<n;i++){
-            for(int j=0;j<m;j++){
-                if(grid[i][j]==1 && vis[i][j]!=1){
-                    return -1;
+        
+        int[] dy ={0,1,-1,0};
+        int[] dx ={1,0,0,-1};
+        
+        int mintime =0;
+        while(!que.isEmpty()){
+            List<Integer> list = que.poll();
+            int x =list.get(0);
+            int y =list.get(1);
+            int time = list.get(2);
+            mintime = Math.max(time , mintime);
+            for(int i=0;i<4;i++){
+                int nx=x+dx[i];
+                int ny=y+dy[i];
+                if(nx>=0 && ny>=0 && nx<grid.length && ny<grid[0].length && grid[nx][ny]==1){
+                    grid[nx][ny]=-1;
+                    que.offer(new ArrayList<>(Arrays.asList(nx, ny, time+1)));
                 }
             }
         }
-        return  max;
         
-    }
-    public int bfs(Queue<Triple> que,int[][] vis,int[][] grid){
-        int[] dx ={0,1,0,-1};
-        int[] dy ={1,0,-1,0};
-        int maxi =0;
-        while(!que.isEmpty()){
-            Triple tt = que.poll();
-            int x =tt.x;
-            int y =tt.y;
-            int time =tt.time;
-            maxi =Math.max(time,maxi);
-            for(int i=0;i<4;i++){
-                int new_x = x+dx[i];
-                int new_y =y+dy[i];
-                
-                if(new_x<grid.length && new_x>=0 && new_y<grid[0].length && new_y>=0 && grid[new_x][new_y]==1 &&vis[new_x][new_y]!=1){
-                    que.offer(new Triple(new_x,new_y,time+1));
-                    vis[new_x][new_y]=1;
+        for(int i=0;i<grid.length;i++){
+            for(int j=0;j<grid[0].length;j++){
+                if(grid[i][j]==1){
+                    return -1;
                 }
             }
         }
-        return maxi;
-    }
-    
-    
-}
-class Triple{
-    int x;
-    int y;
-    int time;
-    Triple(int _x,int _y,int _time){
-        this.x=_x;
-        this.y=_y;
-        this.time =_time;
+        return mintime;
     }
 }
