Approach

Rotting Oranges

Problem Statement

You are given an m x n grid where each cell can have one of three values:

0 representing an empty cell
1 representing a fresh orange
2 representing a rotten orange

Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.

Examples

Example 1:

Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4

Example 2:

Input: grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten,
because rotting only happens 4-directionally.

Example 3:

Input: grid = [[0,2]]
Output: 0
Explanation: Since there are already no fresh oranges at minute 0, the answer is 0.

Constraints

m == grid.length
n == grid[i].length
1 <= m, n <= 10
grid[i][j] is 0, 1, or 2

Approach: Multi-Source BFS

Use multi-source BFS to simulate the rotting process. Start with all initially rotten oranges in the queue and process level by level (minute by minute).

Algorithm:

Count fresh oranges and add all rotten oranges to queue
If no fresh oranges, return 0
BFS: For each minute, process all rotten oranges in queue
For each rotten orange, rot adjacent fresh oranges and add to queue
Increment minutes after each level
Return minutes if all fresh oranges rotted, otherwise return -1

Time Complexity: O(m × n) - visit each cell at most once Space Complexity: O(m × n) - queue size in worst case

Solution

java

1import java.util.*;
2
3class Solution {
4    public int orangesRotting(int[][] grid) {
5        if (grid == null || grid.length == 0) return -1;
6
7        int m = grid.length;
8        int n = grid[0].length;
9        Queue<int[]> queue = new LinkedList<>();
10        int freshCount = 0;
11
12        // Count fresh oranges and add rotten oranges to queue
13        for (int i = 0; i < m; i++) {
14            for (int j = 0; j < n; j++) {
15                if (grid[i][j] == 2) {
16                    queue.offer(new int[]{i, j});
17                } else if (grid[i][j] == 1) {
18                    freshCount++;
19                }
20            }
21        }
22
23        // No fresh oranges
24        if (freshCount == 0) return 0;
25
26        int minutes = 0;
27        int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
28
29        // BFS
30        while (!queue.isEmpty()) {
31            int size = queue.size();
32            boolean rotted = false;
33
34            // Process all oranges at current level (minute)
35            for (int i = 0; i < size; i++) {
36                int[] curr = queue.poll();
37                int row = curr[0];
38                int col = curr[1];
39
40                // Check all 4 directions
41                for (int[] dir : directions) {
42                    int newRow = row + dir[0];
43                    int newCol = col + dir[1];
44
45                    // Check boundaries and if orange is fresh
46                    if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n &&
47                        grid[newRow][newCol] == 1) {
48                        grid[newRow][newCol] = 2;  // Make it rotten
49                        queue.offer(new int[]{newRow, newCol});
50                        freshCount--;
51                        rotted = true;
52                    }
53                }
54            }
55
56            // If any orange rotted this minute, increment time
57            if (rotted) minutes++;
58        }
59
60        // Check if all fresh oranges have rotted
61        return freshCount == 0 ? minutes : -1;
62    }
63}
64
65/**
66 * Time Complexity: O(m * n)
67 * - We visit each cell at most once
68 *
69 * Space Complexity: O(m * n)
70 * - Queue can contain all cells in worst case
71 *
72 * Key Insights:
73 * - Multi-source BFS starting from all initially rotten oranges
74 * - Process level by level to track minutes
75 * - Count fresh oranges to determine if all can rot
76 * - Return -1 if some fresh oranges remain isolated
77 */
78