Use a queue to process rotten oranges in layers, as BFS computes the shortest path for graph traversal.
Count the total fresh oranges initially.
If after BFS traversal some fresh oranges are still left, the answer is -1.

Approach

Initial Setup:
- Count the number of fresh oranges.
- Add all rotten oranges to a queue.
- Track time elapsed during the propagation.
Breadth-First Search (BFS):
- For each rotten orange, rot its adjacent fresh oranges.
- Track which oranges become rotten during each minute.
Exit Conditions:
- If the queue is empty but there are fresh oranges remaining, return -1.
- Otherwise, return the total time elapsed.

Code

[{"language":"Java","code":"public class Solution {\n    public int orangesRotting(int[][] grid) {\n        int rows = grid.length, cols = grid[0].length;\n        Queue<int[]> queue = new LinkedList<>();\n        int freshCount = 0;\n        \n        // Step 1: Count fresh oranges and add rotten oranges to the queue\n        for (int r = 0; r < rows; r++) {\n            for (int c = 0; c < cols; c++) {\n                if (grid[r][c] == 2) { // Rotten orange\n                    queue.add(new int[]{r, c});\n                } else if (grid[r][c] == 1) { // Fresh orange\n                    freshCount++;\n                }\n            }\n        }\n        \n        // Step 2: BFS to rot fresh oranges\n        int minutesElapsed = 0;\n        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};\n        \n        while (!queue.isEmpty() && freshCount > 0) {\n            int size = queue.size();\n            for (int i = 0; i < size; i++) {\n                int[] curr = queue.poll();\n                \n                for (int[] dir : directions) {\n                    int nx = curr[0] + dir[0], ny = curr[1] + dir[1];\n                    \n                    if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && grid[nx][ny] == 1) {\n                        grid[nx][ny] = 2; // Make fresh orange rotten\n                        freshCount--;\n                        queue.add(new int[]{nx, ny});\n                    }\n                }\n            }\n            minutesElapsed++;\n        }\n        \n        // Step 3: Check if all fresh oranges were rotted\n        return freshCount == 0 ? minutesElapsed : -1;\n    }\n}","lang":"java","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">public</span><span style=\"color:#D73A49;--shiki-dark:#F97583\"> class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">    public</span><span style=\"color:#D73A49;--shiki-dark:#F97583\"> int</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> orangesRotting</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int

Related Tags