GitHub

Rotting Oranges medium

Description

You are given an m x n grid where each cell can be one of:

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. Return the minimum number of minutes until no fresh orange remains. If it’s impossible, return -1.

Examples

> Case 1:
    Input:  grid = [[2,1,1],
                    [1,1,0],
                    [0,1,1]]
    Output: 4
 
> Case 2:
    Input:  grid = [[2,1,1],
                    [0,1,1],
                    [1,0,1]]
    Output: -1   # Bottom-left orange is never reached.
 
> Case 3:
    Input:  grid = [[0,2]]
    Output: 0    # Already done — no fresh oranges.

Constraints

1 <= m, n <= 10
Each cell is 0, 1, or 2.

Intuition

Rotting spreads one cell at a time, in all four directions simultaneously. That’s the textbook description of a multi-source breadth-first search.

The twist over normal BFS: instead of starting from one source and finding shortest distances, we start from all rotten oranges at once and find the time until every fresh one is reached.

Algorithm

Sweep the grid once. Push all rotten oranges into the queue as starting points (time 0). Count the fresh oranges.
Run BFS layer by layer. Each layer = “one minute passes.” For every rotten orange popped, infect its 4 neighbors that are still fresh — mark them rotten, decrement the fresh count, enqueue them.
After BFS ends:
- If fresh == 0, return the number of layers we processed (minus 1, since the seed layer is minute 0).
- Otherwise, some orange was unreachable → return -1.

Initial state (minute 0):
[2 1 1]
[1 1 0]
[0 1 1]
queue = [(0,0)], fresh = 6

After minute 1: (0,1) and (1,0) infected.
[2 2 1]
[2 1 0]
[0 1 1]
fresh = 4

After minute 2: (0,2), (1,1) infected.
[2 2 2]
[2 2 0]
[0 1 1]
fresh = 2

After minute 3: (2,1) infected.
[2 2 2]
[2 2 0]
[0 2 1]
fresh = 1

After minute 4: (2,2) infected.
[2 2 2]
[2 2 0]
[0 2 2]
fresh = 0 → answer = 4

Code

The “process a layer at a time” trick

Notice the inner loop: for s in range(len(q)). We capture the queue size at the start of each minute, then only process that many. Everything pushed during this iteration is next minute’s work. This is the standard BFS-with-levels pattern.

Multi-source BFS generalizes single-source BFS by seeding the queue with multiple starting points. The shortest-path-in-layers behavior still works — each cell records the minimum distance to any source. Same algorithm, broader applications: fire spreading, infection modeling, “nearest of any of these points” queries, walls-and-gates, the 01-matrix problem, and more.

Analysis

Time: O(m·n) — every cell is enqueued at most once.
Space: O(m·n) — queue size is bounded by the grid.

First Non-Repeating (Stream)Overview