195. Rotten Oranges - Minimum Time for All to Rot

Given a grid where each cell is 0 (empty), 1 (fresh orange), or 2 (rotten orange), every minute every rotten orange rots its 4-directionally adjacent fresh oranges. Find the minimum number of minutes until no fresh orange remains, or print -1 if some fresh orange can never be reached.

Input: The first line contains two integers rows and cols. Each of the next rows lines contains cols space-separated values (0, 1, or 2), the grid. Output: Print a single integer - the minimum minutes until no fresh orange remains, or -1 if some fresh orange can never be reached.

1 <= rows, cols <= 1000

After the BFS completes, checking if ANY fresh orange remains unrotted is essential - a fresh orange isolated by empty (0) cells with no rotten-orange path to it can NEVER be reached, requiring the -1 output.

Find the minimum time needed for every fresh orange in a grid to rot, given that rotten oranges spread rot to their neighbors every minute. Brute force: Simulate minute by minute, re-scanning the ENTIRE grid each minute to find newly-adjacent fresh oranges - this works but re-scans the whole grid unnecessarily every minute, when a proper BFS only processes each orange once. Optimised: Seeding the BFS queue with ALL initially rotten oranges at once (rather than running separate BFS from each one) naturally computes the correct spread timing - since BFS processes level by level, the 'level' at which a fresh orange gets rotted directly corresponds to the exact minute it happens, and multi-source seeding avoids ever needing to compare distances from multiple separate single-source runs.

Instead of rescanning the whole grid every minute, keep an explicit list (frontier) of the oranges that just became rotten. Each minute, process only that frontier's neighbors to find newly-rotten oranges, forming the next minute's frontier, and repeat until a minute produces no new rotten oranges. This is a textbook multi-source breadth-first search processed in synchronized layers/minutes, only ever visiting each fresh orange once in total, instead of repeatedly rescanning cells that already finished rotting. Time: O(rows*cols) Space: O(rows*cols)

Seed a single queue with all initially rotten oranges, each tagged with time 0. Process the queue in standard BFS fashion: pop a cell, and for each fresh 4-directional neighbor, mark it rotten, tag it with time+1, and push it onto the same queue - no need for a separate layer-swapping structure. The answer is simply the maximum time tag ever popped from the queue (or -1 if any fresh orange remains untouched at the end). This performs the same multi-source BFS as before but with simpler bookkeeping (one queue, no manual layer separation), visiting every cell at most once for a time complexity that cannot be improved since every reachable cell must be examined. Time: O(rows*cols) Space: O(rows*cols)

Simulate minute by minute: on each minute, scan the entire grid, and for every rotten orange found, mark its fresh neighbors to become rotten (using a separate 'next state' marker so a newly-rotten orange doesn't rot further neighbors within the same minute). Repeat full-grid scans until an entire pass produces no new rotten oranges. Since each minute can require a full O(rows*cols) scan and the number of minutes can itself be proportional to the grid's size, repeatedly rescanning the whole grid every minute is wasteful. Time: O((rows*cols)^2) Space: O(rows*cols)

1. This is a MULTI-SOURCE BFS: start with EVERY initially rotten orange in the queue simultaneously, all at time 0. 2. Expand outward level by level (minute by minute), rotting adjacent fresh oranges. 3. The answer is the time at which the LAST fresh orange gets rotted - if any fresh orange remains unreached after the BFS finishes, print -1.

Time: O(rows * cols) - every cell is visited and processed at most once during the multi-source BFS. Space: O(rows * cols), for the visited-tracking (or the grid itself doubling as tracking) and the BFS queue.

Test a grid with no fresh oranges at all (answer 0), a fresh orange isolated from any rotten one by 0-cells (expect -1), and rows/cols at the upper bound of 1000.

Be ready to explain WHY seeding the queue with ALL rotten oranges simultaneously (rather than running BFS once per rotten orange and taking the minimum) is both correct and more efficient - it directly models the real-world simultaneous spread, and processes each cell only once overall.