Rotting Oranges

PracticeNeetCode ↗LeetCode ↗

Given a grid where 0 is empty, 1 is a fresh orange, and 2 is a rotten orange, every minute any fresh orange 4-directionally adjacent to a rotten one becomes rotten. Return the minimum minutes until no fresh orange remains, or -1 if that's impossible.

Example

Key Pointers

• This is multi-source BFS again — start with every initially rotten orange in the queue at minute 0.
• Process the grid level by level (minute by minute) so BFS depth directly equals minutes elapsed.
• Track the remaining fresh-orange count; if it's still above 0 once BFS runs out of cells to spread to, some oranges were unreachable — return -1.

Step-by-Step Analysis

1. Scan the grid: enqueue every rotten orange's position and count the fresh oranges.
2. Run BFS level by level; each level is one minute. For every fresh neighbor found, rot it, decrement the fresh count, and enqueue it for the next level.
3. Increment the minute counter once per level, but only while the queue still has cells to process.
4. After BFS finishes, return the minutes elapsed if the fresh count reached 0, otherwise return -1.

Complexity

Time: O(rows · cols) — Space: O(rows · cols)

Code

from collections import deque

def orangesRotting(grid: list[list[int]]) -> int:
    rows, cols = len(grid), 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

    minutes = 0
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    while queue and fresh > 0:
        minutes += 1
        for _ in range(len(queue)):
            r, c = queue.popleft()
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                    grid[nr][nc] = 2
                    fresh -= 1
                    queue.append((nr, nc))

    return minutes if fresh == 0 else -1

Code Explanation

How the solution above works, piece by piece.

1. Queue every rotten orange at the start and count the fresh ones.
2. while queue and fresh > 0: each pass of the outer loop is one minute.
3. for _ in range(len(queue)) handles exactly the oranges that rotted in the previous minute; their fresh neighbours rot now and are queued for the next minute.
4. Each newly rotten orange decrements fresh.
5. If fresh oranges remain at the end, some were unreachable → −1. O(rows × cols) time.

Visual Walkthrough

Running it on grid = [[2, 1, 1], [1, 1, 0], [0, 1, 1]]:

Video Explanation

NeetCode — Rotting Oranges, LeetCode 994