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]]) → 3Sample 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