# LeetCode 994: Rotting Oranges ## Problem Restatement We are given an `m x n` grid. Each cell can have one of three values: | Value | Meaning | |---|---| | `0` | Empty cell | | `1` | Fresh orange | | `2` | Rotten orange | Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten. The four directions are: ```python up, down, left, right ``` Diagonal cells do not count. We need to return the minimum number of minutes needed until no fresh orange remains. If some fresh orange can never become rotten, return `-1`. The official constraints are `1 <= m, n <= 10`, and each cell is `0`, `1`, or `2`. ([leetcode.com](https://leetcode.com/problems/rotting-oranges/)) ## Input and Output | Item | Meaning | |---|---| | Input | A 2D grid of integers | | Output | Minimum minutes until no fresh orange remains | | Empty cell | `0` | | Fresh orange | `1` | | Rotten orange | `2` | | Impossible case | Return `-1` | Function shape: ```python def orangesRotting(grid: list[list[int]]) -> int: ... ``` ## Examples Example 1: ```python grid = [ [2, 1, 1], [1, 1, 0], [0, 1, 1], ] ``` Minute `0`: ```text 2 1 1 1 1 0 0 1 1 ``` After minute `1`: ```text 2 2 1 2 1 0 0 1 1 ``` After minute `2`: ```text 2 2 2 2 2 0 0 1 1 ``` After minute `3`: ```text 2 2 2 2 2 0 0 2 1 ``` After minute `4`: ```text 2 2 2 2 2 0 0 2 2 ``` Answer: ```python 4 ``` Example 2: ```python grid = [ [2, 1, 1], [0, 1, 1], [1, 0, 1], ] ``` The fresh orange in the bottom-left corner cannot be reached from any rotten orange because rotting only spreads through 4-directional adjacency. Answer: ```python -1 ``` Example 3: ```python grid = [[0, 2]] ``` There are no fresh oranges at the start. Answer: ```python 0 ``` ## First Thought: Simulate Minute by Minute A direct way is to repeatedly scan the whole grid. During each minute: 1. Find all rotten oranges. 2. Mark all adjacent fresh oranges to become rotten. 3. Apply those changes. 4. Repeat until no fresh oranges remain or no new oranges rot. This works, but it scans the grid again and again. ```python class Solution: def orangesRotting(self, grid: list[list[int]]) -> int: rows = len(grid) cols = len(grid[0]) minutes = 0 while True: to_rot = [] for r in range(rows): for c in range(cols): if grid[r][c] == 2: for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]: nr = r + dr nc = c + dc if 0 <= nr < rows and 0 <= nc < cols: if grid[nr][nc] == 1: to_rot.append((nr, nc)) if not to_rot: break for r, c in to_rot: grid[r][c] = 2 minutes += 1 for row in grid: if 1 in row: return -1 return minutes ``` This follows the process, but it does more work than needed. ## Problem With Repeated Scanning Every minute, the brute force simulation scans the full grid. But only newly rotten oranges can spread rot in the next minute. Old rotten oranges do not need to be processed repeatedly. This is a shortest-distance spread problem on a grid, so BFS is the natural fit. ## Key Insight All initially rotten oranges begin spreading at the same time. That makes this a multi-source BFS problem. We start the BFS queue with every rotten orange already in the grid. Each BFS layer represents one minute. When we process all oranges currently in the queue, they rot their fresh neighbors. Those newly rotten oranges become the next layer. So: | BFS concept | Problem meaning | |---|---| | Source nodes | Initially rotten oranges | | Neighbor | 4-directionally adjacent cell | | BFS layer | One minute | | Unvisited fresh orange | Fresh orange that has not rotted yet | ## Algorithm First scan the grid. During this scan: 1. Add all rotten oranges to a queue. 2. Count all fresh oranges. If there are no fresh oranges, return `0`. Then run BFS: 1. Process one full queue layer at a time. 2. For each rotten orange in the current layer, check four neighbors. 3. If a neighbor is fresh: - mark it rotten - decrease the fresh count - add it to the queue 4. After processing the layer, increment the minute count only if at least one fresh orange rotted. At the end: - If `fresh == 0`, return `minutes`. - Otherwise, return `-1`. ## Correctness The queue initially contains every rotten orange present at minute `0`. BFS processes the grid layer by layer. Every cell added during one layer is exactly one minute farther from some initially rotten orange than the cells in the previous layer. When a fresh orange is first reached by BFS, it is reached in the minimum possible number of minutes, because BFS explores all positions reachable in `t` minutes before any position reachable in `t + 1` minutes. The algorithm marks a fresh orange rotten when it is first reached, then never processes it as fresh again. Therefore, every orange is rotted at its earliest possible minute. If all fresh oranges are reached, the last BFS layer that rotted an orange gives the minimum time needed for the whole grid. If some fresh orange remains after BFS ends, then it was not reachable from any initially rotten orange through non-empty adjacent cells. Therefore, it can never rot, so returning `-1` is correct. ## Complexity Let `m = len(grid)` and `n = len(grid[0])`. | Metric | Value | Why | |---|---:|---| | Time | `O(mn)` | Each cell is scanned once and processed at most once in BFS | | Space | `O(mn)` | The queue can store many cells in the worst case | ## Implementation ```python from collections import deque class Solution: def orangesRotting(self, grid: list[list[int]]) -> int: rows = len(grid) cols = len(grid[0]) queue = deque() fresh = 0 for r in range(rows): for c in range(cols): if grid[r][c] == 2: queue.append((r, c)) elif grid[r][c] == 1: fresh += 1 if fresh == 0: return 0 minutes = 0 directions = [(1, 0), (-1, 0), (0, 1), (0, -1)] while queue and fresh > 0: level_size = len(queue) rotted_this_minute = False for _ in range(level_size): r, c = queue.popleft() for dr, dc in directions: nr = r + dr nc = c + dc if nr < 0 or nr >= rows or nc < 0 or nc >= cols: continue if grid[nr][nc] != 1: continue grid[nr][nc] = 2 fresh -= 1 queue.append((nr, nc)) rotted_this_minute = True if rotted_this_minute: minutes += 1 if fresh == 0: return minutes return -1 ``` ## Code Explanation We collect all initial rotten oranges: ```python queue = deque() fresh = 0 ``` During the first scan, rotten oranges become BFS sources: ```python if grid[r][c] == 2: queue.append((r, c)) ``` Fresh oranges are counted: ```python elif grid[r][c] == 1: fresh += 1 ``` If there are no fresh oranges, no time is needed: ```python if fresh == 0: return 0 ``` The BFS runs while there are rotten oranges that can spread and fresh oranges still remain: ```python while queue and fresh > 0: ``` Each loop processes one minute: ```python level_size = len(queue) ``` For each rotten orange, check its four neighbors: ```python for dr, dc in directions: ``` Ignore positions outside the grid: ```python if nr < 0 or nr >= rows or nc < 0 or nc >= cols: continue ``` Ignore cells that are not fresh: ```python if grid[nr][nc] != 1: continue ``` When a fresh orange rots, update the grid and queue: ```python grid[nr][nc] = 2 fresh -= 1 queue.append((nr, nc)) ``` After BFS, if no fresh oranges remain, return the minutes: ```python if fresh == 0: return minutes ``` Otherwise, some fresh orange was unreachable: ```python return -1 ``` ## Testing ```python def run_tests(): s = Solution() assert s.orangesRotting([ [2, 1, 1], [1, 1, 0], [0, 1, 1], ]) == 4 assert s.orangesRotting([ [2, 1, 1], [0, 1, 1], [1, 0, 1], ]) == -1 assert s.orangesRotting([[0, 2]]) == 0 assert s.orangesRotting([[1]]) == -1 assert s.orangesRotting([[2, 1]]) == 1 print("all tests passed") run_tests() ``` | Test | Expected | Why | |---|---:|---| | `[[2,1,1],[1,1,0],[0,1,1]]` | `4` | Standard reachable case | | `[[2,1,1],[0,1,1],[1,0,1]]` | `-1` | One orange is unreachable | | `[[0,2]]` | `0` | No fresh oranges | | `[[1]]` | `-1` | Fresh orange with no rotten source | | `[[2,1]]` | `1` | One adjacent fresh orange rots |