994. Rotting Oranges - Detailed Explanation

Problem Statement

We have a grid (matrix) where each cell can be one of three values:

• 0 – an empty cell (no orange).
• 1 – a fresh orange.
• 2 – a rotten orange.

Every minute, any fresh orange that is 4-directionally adjacent (up, down, left, or right) to a rotten orange becomes rotten. The task is to determine the minimum number of minutes required for all fresh oranges to become rotten. If it is impossible for all oranges to rot (i.e., some fresh oranges are completely isolated from any rotten orange), the answer should be -1.

Example 1:

Input: [[2,1,1],[1,1,0],[0,1,1]]
Output: 4
Explanation: In this 3x3 grid, the rot spreads from the initially rotten orange to all others in 4 minutes. Starting with one rotten orange at (0,0), each minute it contaminates adjacent fresh ones until all reachable oranges are rotten.

Example 2:

Input: [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The fresh orange at (2,0) remains isolated by empty cells and can never rot. Hence, not all fresh oranges can become rotten.

Example 3:

Input: [[0,2]]
Output: 0
Explanation: There are no fresh oranges to begin with, so the time required is 0 minutes.

Constraints:

• m == grid.length, n == grid[i].length
• 1 <= m, n <= 10 (grid dimensions are at most 10x10)
• grid[i][j] is only 0, 1, or 2.

Hints to Solve the Problem

1. Think of the rotting process as a spreading infection. One rotten orange will contaminate its neighbors over time, similar to an infection spreading in waves.

2. A Breadth-First Search (BFS) approach is ideal here. In BFS, we process nodes level by level – this naturally fits the idea of "minute by minute" spreading. Each minute corresponds to one level of BFS propagation.

3. Use a queue to keep track of oranges that will rot others in the next minute. Initially, enqueue all rotten oranges (as multiple starting points for BFS). Then, process all oranges in the queue (all those rotten at the current minute) and rot their fresh neighbors, adding those newly rotten oranges to the queue for the next round.

4. Keep track of the total count of fresh oranges. Each time a fresh orange rots, decrement this count. This helps to determine when all oranges have rotted, and also to detect if some remain fresh despite the process (in which case the answer is -1).

Approach 1: Brute Force (Inefficient)

Idea: One straightforward approach is to simulate the rotting process minute by minute in a brute-force manner. In each iteration (minute), scan the entire grid and find all fresh oranges that are adjacent to any rotten orange; then rot all of those fresh oranges simultaneously. Repeat this process until no new oranges become rotten in an iteration. The number of iterations will be the time taken. If there are still fresh oranges left when the process stops, it means they cannot be reached by any rotten orange, and we should return -1.

This brute-force simulation literally iterates the grid minute by minute, rotting fresh oranges that are adjacent to rotten ones. We need to be careful to rot oranges for each minute simultaneously – typically by using a copy of the grid for the next state – so that oranges that rot at minute k don’t immediately rot others in the same minute’s iteration. We continue until either all oranges are rotten or an iteration passes with no change (no new oranges rotted). At that point, if any fresh orange remains, the answer is -1.

Why is this approach inefficient? In the worst case, the spread of rot could take many minutes, and each minute we scan the entire grid. For a grid of size m × n and k minutes of rotting, the time complexity can be about O(k × m × n). In the worst scenario where oranges rot one after another (not concurrently), k could be on the order of m × n, making the complexity ~O((m × n)^2), which is very slow for larger grids. This method also requires additional space to copy the grid state for each iteration, leading to O(m × n) space usage for the grid copy. While this brute-force approach will work for the small grid sizes in our constraints, it’s not optimal.

Approach 2: Optimal BFS Approach

Idea: We can solve the problem much more efficiently using multi-source BFS. Instead of rotting oranges one minute at a time with repeated scans, we treat all initially rotten oranges as starting points (sources) and spread the rot outward in waves. BFS naturally processes nodes in layers (levels), which correspond to minutes in this problem. All oranges that rot after 1 minute form the first layer, those that rot after 2 minutes form the next, and so on. This way, we infect all oranges in the minimum time possible.

How it works: Think of the grid as a graph where each cell is a vertex and edges connect adjacent cells (up, down, left, right). All initially rotten oranges are enqueued to start the BFS. Then:

1. Initialization: Enqueue all rotten oranges' coordinates and set a minutes counter to 0. Count the total number of fresh oranges at the start . If there are no fresh oranges at all, return 0 immediately (nothing to rot).
2. BFS traversal: While the queue is not empty, process all oranges in the queue for the current minute (this represents all oranges that are rotten at this time). For each such orange, look at its 4 neighbors. If a neighbor is a fresh orange (value 1), turn it into rotten (change to 2), decrement the fresh count, and add that neighbor to a temporary list or queue of oranges that will be rotten in the next minute.
3. Increment time: After processing all oranges for the current minute (i.e., the entire queue level), increment the minutes counter, and update the queue with all the newly rotten oranges (the next layer of BFS). This signifies moving to the next minute of infection spread.
4. Continue BFS: Repeat the process until there are no more fresh oranges to rot or the queue becomes empty.

If BFS finishes (queue is empty) and there are still fresh oranges (fresh_count > 0), that means some oranges could never be reached by the rot – they are isolated. In that case, return -1. Otherwise, if all oranges have rotted, the minutes counter holds the minimum time it took. (One nuance: if we counted minutes on each layer change, by the time the loop ends we might have incremented one extra minute, so sometimes the result is minutes - 1 depending on implementation. In our approach below, we handle the increment such that minutes will be the correct count when the process ends.)

Why this is efficient: BFS ensures that each orange becomes rotten at the earliest possible time, and we visit each cell at most once when it turns from fresh to rotten. Thus, the time complexity is O(m × n) – each cell is processed a constant number of times (at most once when it rots). The space complexity is also O(m × n) in the worst case for the queue (if all oranges rot at about the same time, they could all be in the queue). This is much better than the brute force approach. The BFS approach is the standard optimal solution for this problem.

Code Implementations

Python Implementation: