Rotting Oranges - Solution & Explanation

Problem Overview: You are given a grid where 0 represents empty cells, 1 fresh oranges, and 2 rotten oranges. Every minute, rotten oranges infect their 4-directionally adjacent fresh neighbors. The task is to compute the minimum number of minutes required until no fresh oranges remain, or return -1 if some oranges can never rot.

Approach 1: Breadth-First Search (Multi-Source BFS) (Time: O(m*n), Space: O(m*n))

This problem is essentially a level-by-level spread across a grid, which maps perfectly to Breadth-First Search. Start by pushing all initially rotten oranges into a queue. Each BFS layer represents one minute. For every rotten orange, check its four neighbors and convert any fresh orange to rotten, pushing it into the queue for the next minute.

The key insight is treating all rotten oranges as simultaneous starting points (multi-source BFS). Instead of simulating minute-by-minute scanning of the entire grid, BFS only processes cells that actually change state. Track the remaining fresh oranges during traversal; if any remain after BFS finishes, return -1. This approach runs in O(m*n) time because each cell is processed at most once and uses O(m*n) space for the queue in the worst case.

The grid itself behaves like an implicit graph where each cell connects to its four neighbors. Problems involving propagation across a matrix or layered expansion usually signal BFS as the optimal strategy.

Approach 2: DFS with Memoization (Time: O(m*n), Space: O(m*n))

An alternative approach computes the minimum time for each fresh orange to become rotten using depth-first search. Starting from rotten oranges, DFS explores neighbors recursively while memoizing the earliest minute each cell becomes infected. If a DFS path reaches a fresh orange with a shorter infection time than previously recorded, update and continue exploring.

This method treats the grid like a recursive propagation problem on a graph built from the array representation. Memoization prevents recomputing infection times for cells that already have an optimal value. While the theoretical time complexity remains O(m*n), recursion overhead and repeated neighbor checks make it less intuitive than BFS.

DFS works but requires careful handling of cycles and time comparisons to avoid unnecessary recursion. Because the infection spreads simultaneously from multiple sources, DFS does not naturally model the "minute-by-minute" process the way BFS does.

Recommended for interviews: Multi-source BFS is the expected solution. It directly models the spread of rot as a wave expanding outward each minute and guarantees optimal timing naturally through BFS levels. Mentioning a brute-force simulation or DFS idea shows understanding, but implementing the BFS queue approach demonstrates strong grasp of graph traversal on grids.