DSA sheet · Graphs · Multi-source BFS, level by level

Rotting Oranges

Rot spreads from every rotten orange to its neighbours, one minute at a time. "How many minutes until everything is rotten?" is really "how many BFS layers does it take?". The teacher uses this problem to show three things: why the word minimum here doesn't mean DP, why all rotten oranges start together (multi-source BFS), and how to count minutes by processing the queue one level at a time, exactly like level order traversal in a binary tree. A small fresh counter then tells us whether some orange could never be reached.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting (graphs, BFS, grids)
• · inside Part 0: why BFS layers = shortest time
• · inside Part 0: multi-source BFS, and why all sources start together
• · inside Part 0: processing a queue level by level
• Part A · Multi-source BFS, one level per minute
• Part B · Revision page

Part 0 · Before starting

Graph words in one place

• Node: a point. Edge: a connection between two nodes.
• Undirected (0)—(1): both ways. Directed (0)→(1): one way.
• Weighted (0)—3—(1): the edge has a cost. Unweighted: every edge costs 1. Here, rot moving one cell always takes exactly 1 minute, so this grid is an unweighted graph.

For normal graphs we read an edge list and build an adjacency list (each node → list of neighbours):

n = 3
edges = [[0, 1], [1, 2]]
adj = [[] for _ in range(n)]
for u, v in edges:
    adj[u].append(v)
    adj[v].append(u)
print(adj)   # [[1], [0, 2], [1]]

A grid is a graph without an adjacency list

Every cell (r, c) is a node. Its neighbours are up, down, left, right. The teacher's point: an adjacency list is for when we don't know a node's children. In a grid we always do, by adding (dr, dc) offsets, so no list is needed.

            (r-1,c)
               ↑
  (r,c-1) ← (r,c) → (r,c+1)        directions = (0,-1) (-1,0) (0,1) (1,0)
               ↓
            (r+1,c)

Always check bounds before reading a neighbour: 0 <= nr < m and 0 <= nc < n.

Visited, and a free way to mark it

Without a "visited" mark, BFS would keep revisiting the same cells. The teacher's checklist always asks: do I need a separate visited array, or can a value in the grid tell me? In many problems you must build one. Here, turning a fresh orange (1) into rotten (2) is the visited mark. We only ever step into 1s, so a cell that's now 2 is never entered again.

A connected component is a group of cells that can reach each other. Empty cells (0) break the grid into pieces. A fresh orange in a piece with no rotten orange can never rot, so the answer becomes −1.

BFS and DFS

• BFS: a queue (collections.deque). Everything 1 step away, then 2 steps, then 3… in rings.
• DFS: recursion or a stack. Follow one path as deep as it goes, then come back.

Why BFS layers = shortest time

The queue gets cells in order of distance: everything at distance d is popped before anything at distance d+1, because new cells are always added at the back with distance d+1. So the first time BFS reaches a cell is the earliest possible moment. In this problem that is exactly what happens in real life too: an orange rots the first minute any rotten neighbour touches it, never later. So BFS layer number = the minute it rots.

Multi-source BFS: why all sources start in the queue together

If several oranges are rotten at minute 0, they all spread at the same time. The teacher stresses this: it isn't one orange spreading and then the next one. Every rotten orange infects its neighbours in the same minute.

R = rotten, F = fresh             all R start together      start from the left R only
R F F F F R                       minute 1: R R F F R R     minute 1: R R F F F R
                                  minute 2: R R R R R R     ...
                                  answer 2 ✓                 minute 4: R R R R R R → 4 ✗

Putting every rotten orange in the queue before the loop starts makes layer 0 = "all rotten at the start". Then layer 1 = everything one step from any of them, and so on. That copies the real spreading exactly. Starting from one at a time would either give a wrong (too large) time, or need a whole new BFS per rotten orange.

Processing a queue level by level

To count minutes we need to know where one layer ends. Trick from level order traversal of a binary tree: at the start of each round, read size = len(queue). Exactly those size items belong to the current level. Pop only that many. Anything pushed during the round is the next level and waits for the next round.

from collections import deque

adj = [[1, 2], [0, 3], [0], [1]]
queue = deque([0])
seen = {0}
level = 0
while queue:
    size = len(queue)                # how many nodes are in THIS level
    names = []
    for _ in range(size):
        u = queue.popleft()
        names.append(u)
        for v in adj[u]:
            if v not in seen:
                seen.add(v)
                queue.append(v)      # goes to the NEXT level
    print(level, names)
    level += 1
# prints:
# 0 [0]
# 1 [1, 2]
# 2 [3]

Part A · Multi-source BFS, one level per minute

LeetCode 994

1The question in simple words

You get an m×n grid. Each cell holds:

• 0: empty, no orange
• 1: a fresh orange
• 2: a rotten orange

Every minute, each fresh orange that touches a rotten one (up, down, left or right, not diagonally) becomes rotten. Return the minimum number of minutes until no fresh orange is left. If that can never happen, return −1.

2 1 1
1 1 0
0 1 1

2 1 1
0 1 1
1 0 1
bottom-left is cut off

0 2
no fresh orange
at all

Only rotten oranges spread rot. A fresh orange next to another fresh orange stays fresh.

2What the constraints tell us

• 1 <= m, n <= 10 → at most 100 cells. Anything linear is instant. (Even a slow minute-by-minute simulation would pass, but BFS is the clean way and scales.)
• Values are only 0, 1, 2 → we can safely change 1 into 2 to mean "visited".
• The grid can have no fresh oranges, no rotten ones, or no oranges at all, so we need answers for those too: no fresh → 0; fresh but no rotten → −1.

3Intuition: rings of rot

Picture every rotten orange as a drop of ink. Each minute, every drop spreads one cell outwards, all at once. The answer is the number of rings needed to cover the last fresh orange. That's BFS, started from all rotten oranges at once, counting layers.

The teacher's 3-question checklist:

4Building the logic from her examples

"Minimum" doesn't mean DP

The teacher warns: seeing the word "minimum" doesn't automatically mean dynamic programming. When moving from one cell to the next always costs the same (1 minute), plain BFS gives the minimum. Only when costs differ (weighted edges) do we need something more, like Dijkstra.

Why not DFS?

DFS would push the rot down one long winding path first, then come back and try other directions. The time it reports depends on which direction it happened to pick first, and it can report a much larger time than the real one. A cell next to the start might get reached at the very end of a long path. In real life rot spreads in all directions at once, which is BFS.

2 1 1          DFS going right first:  (0,1)=1 → (0,2)=2 → (1,2)=3 → (1,1)=4 → (1,0)=5 ...
1 1 1          but (1,0) actually rots at minute 1 (it touches the 2 directly)
1 1 1          BFS gives each cell its real minute

Starting the queue: every 2 goes in

Scan the whole grid. Every rotten orange's (row, col) is pushed into the queue. At the same time, count the fresh oranges (we'll see why below). minutes starts at 0: the oranges rotten from the start don't cost any time.

One minute = one level of the queue

The teacher's dry run on Example 1:

• Queue = [(0,0)]. In the next minute, (0,0) rots its two fresh neighbours (0,1) and (1,0). Those go in the queue. One level done → minutes = 1.
• Now both (0,1) and (1,0) spread in the same minute. She stresses that it isn't just the first one: all rotten oranges of a level spread together, at the same speed. (0,1) rots (0,2) and (1,1). (1,0) can reach (1,1) too, but it's already rotten, so it does nothing. Level done → minutes = 2.

So we must pop exactly one level per minute. That's the size = len(queue) trick from Part 0. If we didn't freeze the size, the children pushed during this minute would be popped in the same round and we'd lose track of minutes.

Stepping into a neighbour

For each popped cell, try 4 directions. Enter (nr, nc) only if it's inside the grid and grid[nr][nc] == 1 (a fresh orange). Then:

1. set grid[nr][nc] = 2 (it's rotten now, and also marked visited),
2. decrease fresh by 1,
3. push it, so next minute it spreads rot further.

How do we know it's impossible? The fresh counter

When the queue becomes empty, BFS just stops. It doesn't say whether every orange rotted. The teacher's example: imagine a fresh orange surrounded by empty cells. No rot can reach it, the queue empties, and that orange is still fresh.

Fix: count fresh oranges at the start, subtract one each time one rots. At the end:

• fresh == 0 → every orange rotted → return minutes.
• fresh > 0 → some orange was cut off → return −1.

The loop condition: while queue and fresh > 0

Look at Example 1 at the end: the last fresh orange (2,2) rots at minute 4, and it is pushed into the queue. If the loop kept going, it would pop (2,2), find nothing to rot, and still add +1 minute at the end of that level. The answer would become 5.

The teacher adds fresh > 0 to the loop: once every fresh orange has rotted, there's nothing left to do, even if the queue still holds cells. Those cells can't find any fresh orange. Her reason is "don't waste time", but it matters for correctness too: it stops the extra minute.

from collections import deque

def oranges_without_fresh_check(grid):
    m, n = len(grid), len(grid[0])
    queue = deque()
    fresh = 0
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 2:
                queue.append((i, j))
            elif grid[i][j] == 1:
                fresh += 1
    minutes = 0
    while queue:                                  # no "fresh > 0" here
        for _ in range(len(queue)):
            r, c = queue.popleft()
            for dr, dc in [(0, -1), (-1, 0), (0, 1), (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
                    queue.append((nr, nc))
        minutes += 1
    return minutes if fresh == 0 else -1

print(oranges_without_fresh_check([[2, 1, 1], [1, 1, 0], [0, 1, 1]]))   # 5
print(oranges_without_fresh_check([[0, 2]]))                            # 1

Both are wrong: the right answers are 4 and 0. The last level always adds one minute too many.

Don't count the starting rotten oranges as a minute

The teacher points this out in her dry run: the orange at (0,0) was already rotten. It didn't take a minute to rot, so level 0 adds nothing by itself. Minutes only count spreading: level 1 (minute 1), level 2 (minute 2)…, and the answer is the minute the last fresh orange rots.

5Approach steps

1. Scan the grid: push every 2 into the queue; count every 1 as fresh.
2. minutes = 0.
3. While the queue isn't empty and fresh > 0:
4.   freeze size = len(queue) and pop exactly that many cells;
5.   for each, look 4 ways; every fresh neighbour → set to 2, fresh -= 1, push;
6.   after the level, minutes += 1.
7. Return minutes if fresh == 0, else −1.

6Code (Python)

from collections import deque

class Solution:
    def orangesRotting(self, grid):
        m, n = len(grid), len(grid[0])
        queue = deque()
        fresh = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 2:
                    queue.append((i, j))        # every rotten orange is a source
                elif grid[i][j] == 1:
                    fresh += 1

        minutes = 0
        directions = [(0, -1), (-1, 0), (0, 1), (1, 0)]
        while queue and fresh > 0:
            size = len(queue)                   # oranges that spread THIS minute
            for _ in range(size):
                r, c = queue.popleft()
                for dr, dc in directions:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1:
                        grid[nr][nc] = 2        # rots now (and is marked visited)
                        fresh -= 1
                        queue.append((nr, nc))
            minutes += 1                        # one whole level = one minute

        return minutes if fresh == 0 else -1

7Code line by line

8Dry run (her Example 1)

grid               index map
2 1 1              (0,0) (0,1) (0,2)
1 1 0              (1,0) (1,1) (1,2)
0 1 1              (2,0) (2,1) (2,2)
start: queue = [(0,0)], fresh = 6, minutes = 0

2 2 1
2 1 0
0 1 1

2 2 2
2 2 0
0 1 1

2 2 2
2 2 0
0 2 2

In the video she reads a couple of cell indexes a bit loosely while pointing at the board. The table above uses the exact indexes.

Example 2 quickly: the bottom-left 1 at (2,0) has a 0 above it and a 0 to its right. No rotten orange can ever touch it. BFS rots the other 5, the queue runs dry, fresh is still 1 → −1.

Example 3: [[0, 2]] has no fresh orange, so fresh = 0, the loop never runs → 0.

9Complexity & remember

• Time O(4 · m · n): each cell enters the queue at most once (only when it turns from 1 to 2, or at the start), and each pop looks in 4 directions, valid or not. Plus one O(m·n) scan at the start.
• Space O(m · n): in the worst case (all fresh, one rotten corner) almost every cell passes through the queue. No visited array, since the 2s do that job.

Part B · Revision page

s = Solution()
print(s.orangesRotting([[2, 1, 1], [1, 1, 0], [0, 1, 1]]))   # 4
print(s.orangesRotting([[2, 1, 1], [0, 1, 1], [1, 0, 1]]))   # -1
print(s.orangesRotting([[0, 2]]))                            # 0
print(s.orangesRotting([[0]]))                               # 0
print(s.orangesRotting([[1]]))                               # -1
print(s.orangesRotting([[2, 1, 1, 1, 2]]))                   # 2

Based on this video: Rotting Oranges | Multi-source BFS