Rotting Oranges

Medium~25 min

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

  • 0 — empty cell
  • 1 — fresh orange
  • 2 — rotten orange

Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.

Examples

Example 1
Input: grid = [[2, 1, 1], [1, 1, 0], [0, 1, 1]]
Output: 4
Explanation: The rotten orange at (0,0) spreads to all connected fresh oranges. It takes 4 minutes for the last orange at (2,2) to rot.
Example 2
Input: grid = [[2, 1, 1], [0, 1, 1], [1, 0, 1]]
Output: -1
Explanation: The orange at (2,0) is isolated by empty cells and can never be reached.
Example 3
Input: grid = [[0, 2]]
Output: 0
Explanation: There are no fresh oranges, so 0 minutes are needed.

Constraints

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 10
  • grid[i][j] is 0, 1, or 2
  • Expected time complexity: O(m × n)
Code
Ctrl+EnterRun|Ctrl+⇧+EnterSubmit
Output

Run your code to see results

Use Cmd+Enter to run