NeetCode #567LC-994MediumGraphsNC 150NC 250
← Back to All Problems#567 · #994 · Rotting Oranges(腐烂的橘子)
📌 Problem Statement & Constraints
You are given an
m x n grid where 0 is empty, 1 is a fresh orange and 2 is a rotten orange. Each minute, fresh oranges adjacent to a rotten one become rotten. Return the minimum minutes until no fresh orange remains, or -1 if impossible. Constraints: 1 <= m, n <= 10.💡 Core Algorithmic Approaches
- Multi-source BFS from all initially rotten oranges.
- Process the queue level by level, incrementing the minute counter after each level.
- Only enqueue fresh oranges when they rot, so each cell is processed once.
- The answer is the number of levels, or -1 if any fresh orange remains.
💻 Benchmark Python3 Implementation
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
from collections import deque
m, n = len(grid), len(grid[0])
q = deque()
fresh = 0
for i in range(m):
for j in range(n):
if grid[i][j] == 2:
q.append((i, j)) # every rotten orange is a source
elif grid[i][j] == 1:
fresh += 1
minutes = 0
while q and fresh:
# process one whole minute
for _ in range(len(q)):
r, c = q.popleft()
for dr, dc in ((0, 1), (0, -1), (1, 0), (-1, 0)):
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1:
grid[nr][nc] = 2
fresh -= 1
q.append((nr, nc))
minutes += 1
return minutes if fresh == 0 else -1⚡ Complexity Deep Dive
⏱️ Time Complexity
O(m * n): each cell is enqueued at most once.
💾 Space Complexity
O(m * n) for the queue.
⚠️ Interview Pitfalls & Follow-ups
- Incrementing the minute per cell instead of per level: the level grouping is what measures elapsed time.
- Returning
minuteswithout checkingfresh: unreachable fresh oranges must yield -1. - Not including
freshin the loop condition: the loop would keep spinning after the last orange rots. - Marking rotten when enqueuing: required, otherwise the same orange could be enqueued from several neighbours.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.