0994.Rotting Oranges

Link: 994. Rotting Oranges - Medium
Track: NeetCode150 Amazon

Question

Restate

• Given a grid:
  • 0 = empty cell
  • 1 = fresh orange
  • 2 = rotten orange
• Every minute, any fresh orange adjacent (up/down/left/right) to a rotten orange becomes rotten.
• Return the minimum minutes until no fresh oranges remain, or -1 if impossible.

Edge Case

• no fresh oranges initially

---

Method	Approach	Time Complexity	Space Complexity
Method 1 ⭐	BFS	$O(m\cdot n)$	$O(m\cdot n)$

Method 1 - BFS

Approach

• Scan the grid once:
  • Count fresh
  • Push all initial rotten oranges (2) into the queue (multi-source BFS)
• Run BFS by layers:
  • Process exactly size = len(queue) nodes for the current minute
  • For each rotten orange, rot its fresh neighbors (1 -> 2), decrement fresh, and enqueue them
• After BFS:
  • If fresh == 0 → return minutes
  • Else → return -1

Complexity

• Time Complexity: $O(m\ast n)$
• Space Complexity: O($m\ast n$)

Code

from collections import deque
 
class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        if not grid or not grid[0]:
            return 0
        
        rows, cols = len(grid), len(grid[0])
        dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
        fresh = 0
        queue = deque()
        for row in range(rows):
            for col in range(cols):
                if grid[row][col] == 1:
                    fresh += 1
                elif grid[row][col] == 2:
                    queue.append((row, col))
        
        if fresh == 0:
            return 0
 
        step = -1
        while queue:
            size = len(queue)
            for _ in range(size):
                r, c = queue.popleft()
                for dr, dc in dirs:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols \
                        and grid[nr][nc] == 1:
                        fresh -= 1
                        grid[nr][nc] = 2
                        queue.append((nr, nc))
            step += 1
        
        return step if fresh == 0 else -1

---

Mistake

• Forgot level-order BFS, process the queue by layer (size = len(queue)),