⚡Flashcard Drill➔
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

  1. Multi-source BFS from all initially rotten oranges.
  2. Process the queue level by level, incrementing the minute counter after each level.
  3. Only enqueue fresh oranges when they rot, so each cell is processed once.
  4. 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 minutes without checking fresh: unreachable fresh oranges must yield -1.
  • Not including fresh in 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.
🎯 Drill This Card Now➔

🧩 Related Graphs Problems