add a solution for 994

fishercoder1534 · fishercoder1534 · commit 76d2c52ed4e1 · 2021-10-29T09:25:55.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/_994.java b/src/main/java/com/fishercoder/solutions/_994.java
@@ -93,4 +93,51 @@ public int orangesRotting(int[][] grid) {
             return fresh.isEmpty() ? min : -1;
         }
     }
+
+    public static class Solution3 {
+        /**
+         * My original solution on 10/29/2021.
+         */
+        public int orangesRotting(int[][] grid) {
+            int m = grid.length;
+            int n = grid[0].length;
+            int freshOranges = 0;
+            Queue<int[]> queue = new LinkedList<>();
+            boolean[][] visited = new boolean[m][n];
+            for (int i = 0; i < m; i++) {
+                for (int j = 0; j < n; j++) {
+                    if (grid[i][j] == 2) {
+                        queue.offer(new int[]{i, j});
+                        visited[i][j] = true;
+                    } else if (grid[i][j] == 1) {
+                        freshOranges++;
+                    }
+                }
+            }
+            int mins = 0;
+            int[] directions = new int[]{0, 1, 0, -1, 0};
+            while (!queue.isEmpty()) {
+                int size = queue.size();
+                boolean hasOneToRot = false;
+                for (int i = 0; i < size; i++) {
+                    int[] curr = queue.poll();
+                    for (int j = 0; j < directions.length - 1; j++) {
+                        int newx = directions[j] + curr[0];
+                        int newy = directions[j + 1] + curr[1];
+                        if (newx >= 0 && newx < m && newy >= 0 && newy < n && grid[newx][newy] == 1 && !visited[newx][newy]) {
+                            freshOranges--;
+                            grid[newx][newy] = 2;
+                            visited[newx][newy] = true;
+                            queue.offer(new int[]{newx, newy});
+                            hasOneToRot = true;
+                        }
+                    }
+                }
+                if (hasOneToRot) {
+                    mins++;
+                }
+            }
+            return freshOranges == 0 ? mins : -1;
+        }
+    }
 }
diff --git a/src/test/java/com/fishercoder/_994Test.java b/src/test/java/com/fishercoder/_994Test.java
@@ -10,12 +10,14 @@
 public class _994Test {
     private static _994.Solution1 solution1;
     private static _994.Solution2 solution2;
+    private static _994.Solution3 solution3;
     private static int[][] grid;
 
     @BeforeClass
     public static void setUp() {
         solution1 = new _994.Solution1();
         solution2 = new _994.Solution2();
+        solution3 = new _994.Solution3();
     }
 
     @Test
@@ -66,6 +68,7 @@ public void test5() {
     public void test6() {
         grid = CommonUtils.convertLeetCodeIrregularLengths2DArrayInputIntoJavaArray("[2],[1]");
         assertEquals(1, solution2.orangesRotting(grid));
+        assertEquals(1, solution3.orangesRotting(grid));
     }
 
 }

Original file line number	Diff line number	Diff line change
`@@ -10,12 +10,14 @@`
`10`	`10`	`public class _994Test {`
`11`	`11`	`private static _994.Solution1 solution1;`
`12`	`12`	`private static _994.Solution2 solution2;`
	`13`	`+ private static _994.Solution3 solution3;`
`13`	`14`	`private static int[][] grid;`
`14`	`15`
`15`	`16`	`@BeforeClass`
`16`	`17`	`public static void setUp() {`
`17`	`18`	`solution1 = new _994.Solution1();`
`18`	`19`	`solution2 = new _994.Solution2();`
	`20`	`+ solution3 = new _994.Solution3();`
`19`	`21`	`}`
`20`	`22`
`21`	`23`	`@Test`
`@@ -66,6 +68,7 @@ public void test5() {`
`66`	`68`	`public void test6() {`
`67`	`69`	`grid = CommonUtils.convertLeetCodeIrregularLengths2DArrayInputIntoJavaArray("[2],[1]");`
`68`	`70`	`assertEquals(1, solution2.orangesRotting(grid));`
	`71`	`+ assertEquals(1, solution3.orangesRotting(grid));`
`69`	`72`	`}`
`70`	`73`
`71`	`74`	`}`