If any fresh orange remains unreachable, we return -1.

Key points:

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"},{"language":"Python","code":"class Solution:\n    def orangesRotting(self, grid):\n        rows, cols = len(grid), len(grid[0])\n        queue = deque()\n        fresh_count = 0\n        \n        # Step 1: Count fresh oranges and add rotten oranges to queue\n        for r in range(rows):\n            for c in range(cols):\n                if grid[r][c] == 2:  # Rotten orange\n                    queue.append((r, c))\n                elif grid[r][c] == 1:  # Fresh orange\n                    fresh_count += 1\n        \n        # Step 2: BFS to rot fresh oranges\n        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]\n        minutes_elapsed = 0\n        \n        while queue and fresh_count > 0:\n            for _ in range(len(queue)):\n                x, y = queue.popleft()\n                for dx, dy in directions:\n                    nx, ny = x + dx, y + dy\n                    if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == 1:\n                        grid[nx][ny] = 2  # Make fresh orange rotten\n                        fresh_count -= 1\n                        queue.append((nx, ny))\n            minutes_elapsed += 1\n\n        # Step 3: Check if all fresh oranges were rotted\n        return minutes_elapsed if fresh_count == 0 else -1"

Related Tags