noodleProblems/
Rotting Oranges
#146

Rotting Oranges

AlgorithmmediumArrayBreadth First SearchMatrix

You are given an m x n grid where each cell holds one of three values:

- 0 — an empty cell, - 1 — a **fresh** orange, - 2 — a **rotten** orange.

Every minute, any fresh orange that is **4-directionally adjacent** (up, down, left, right) to a rotten orange becomes rotten too. All such rottings happen simultaneously each minute.

Return the **minimum number of minutes** that must elapse until no cell has a fresh orange. If it is impossible for every fresh orange to rot (one is fenced off from all rotten oranges), return -1.

Example cases

  • spreads in 4 minutes
    in grid =
    211
    110
    011
    out 4
    The rot fans out one ring per minute; the last fresh orange (bottom-right) rots at minute 4.
  • one orange unreachable
    in grid =
    211
    011
    101
    out -1
    The fresh orange at (2,0) is cut off by empty cells, so it never rots — return -1.
  • no fresh oranges
    in grid =
    02
    out 0
    Nothing is fresh at the start, so zero minutes elapse.

Constraints

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 10
  • grid[i][j] is 0, 1, or 2.
Saved
grid =
[[2,1,1],[1,1,0],[0,1,1]]