How do you solve the Rotting Oranges problem with multi-source BFS?

Q: How do you solve the Rotting Oranges problem with multi-source BFS?

**Target Audience:** Beginners preparing for coding interviews — you know Python lists, tuples and loops; BFS and grids-as-graphs are explained from scratch. **Difficulty:** Medium **Language:** Python 3 > **How to read this doc:** Every idea is explained in plain language first, then tagged with `📌 Interview term:` so you also learn the exact words an interviewer expects. Every output shown was produced by actually running the code with `python3` (3.13); nothing is typed in by hand. ## 1. Why This Even Matters — A Story First You leave a crate of oranges in the sun. A few are already rotten. Every minute, each rotten orange spoils the fresh oranges directly above, below, left and right of it — not diagonally, and not across an empty slot. How many minutes until no fresh orange is left? And is there an orange that will **never** rot because it is walled off by empty slots? Picture dropping several stones into a pond at the same moment. Ripples spread from **all** of them at once,

The problem

Question presented to candidate: "You have a grid where 0 is an empty cell, 1 is a fresh orange and 2 is a rotten orange. Every minute, each rotten orange rots the fresh oranges directly up, down, left and right of it. Return the minimum number of minutes until no fresh orange is left, or -1 if that is impossible. Please solve it in Python."

What a strong answer should cover:

Seeing the grid as a graph and the spread as BFS levels: level k = the oranges that rot at minute k.
Multi-source BFS: put every rotten orange in the queue at time 0 before the loop — not one BFS per rotten orange.
Counting fresh oranges up front to detect the -1 case, and the 0 case when nothing is fresh.
O(rows × cols) time and space, versus O(minutes × rows × cols) for a minute-by-minute simulation.
Python specifics: collections.deque with popleft(), for _ in range(len(queue)) to process exactly one level, building a 2D grid with a comprehension (never [[-1] * cols] * rows), and saying whether you mutate the caller's grid.

Clarifying questions expected:

Four directions or eight? What if there are no fresh oranges?
May I modify the input grid?

Code / implementation expected: Yes — an oranges_rotting(grid) function in Python using multi-source BFS, tested on the impossible case and the no-fresh case.

dsa
graph
bfs
grid

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Beginners preparing for coding interviews — you know Python lists, tuples and loops; BFS and grids-as-graphs are explained from scratch. Difficulty: Medium Language: Python 3

How to read this doc: Every idea is explained in plain language first, then tagged with 📌 Interview term: so you also learn the exact words an interviewer expects. Every output shown was produced by actually running the code with python3 (3.13); nothing is typed in by hand.

1. Why This Even Matters — A Story First

You leave a crate of oranges in the sun. A few are already rotten. Every minute, each rotten orange spoils the fresh oranges directly above, below, left and right of it — not diagonally, and not across an empty slot. How many minutes until no fresh orange is left? And is there an orange that will never rot because it is walled off by empty slots?

Picture d

The solution is hidden so you can try first

13 min read · 10 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonMulti-source BFS on six grids, plus the minute each orange rotted

Practice

PythonSimulation vs one BFS per rotten orange vs multi-source BFS: counting the work