codejump
MediumPythonJavaScriptTypeScript

Graph — Rotting Oranges

Data StructuresGraphsBFSMatrix

solve(grid) — each cell is 0 (empty), 1 (fresh orange) or 2 (rotten
orange). Every minute, each fresh orange that is 4-directionally adjacent to a
rotten one becomes rotten.

Return the minimum number of minutes until no fresh orange is left, or -1
if some fresh orange can never rot. If there are no fresh oranges at all, the
answer is 0.

The trick is a multi-source BFS: start with *all* rotten oranges in the queue
at once and advance one whole level per minute.

Examples

solve([[2,1,1],[1,1,0],[0,1,1]])  → 4
solve([[2,1,1],[0,1,1],[1,0,1]])  → -1    // the bottom-left orange is isolated
solve([[0,2]])                    → 0
solve([[2,1,1,1]])                → 3

Sample tests

Test #1Classic example
Input: [[[2,1,1],[1,1,0],[0,1,1]]]
Output: 4
Test #2An isolated fresh orange
Input: [[[2,1,1],[0,1,1],[1,0,1]]]
Output: -1
Test #3No fresh oranges
Input: [[[0,2]]]
Output: 0