AlgoLounge

Rotting Oranges

medium

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 All oranges rot in 4 minutes as the rot spreads from (0,0) outward.

Example 2

Input:  grid = [

[2,1,1], [0,1,1], [1,0,1] ] Output: -1 The orange at bottom-left can never rot (isolated by empty cells).

Example 3

Input:  grid = [[0,2]]
Output: 0

No fresh oranges, so 0 minutes needed.

Constraints

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 10
  • grid[i][j] is 0, 1, or 2
TypeScript
Loading editor…
List of test cases (9)
Case 1
grid = [[2,1,1],[1,1,0],[0,1,1]]
Case 2
grid = [[2,1,1],[0,1,1],[1,0,1]]
Case 3
grid = [[0,2]]
Case 4
grid = [[2,2],[1,1],[0,0],[2,1]]
Case 5
grid = [[0,0,0],[0,0,0],[0,0,0]]
Case 6
grid = [[1,1,1],[1,1,1],[1,1,1]]
Case 7
grid = [[2]]
Case 8
grid = [[1]]
Case 9
grid = [[2,1,1,1,1],[1,1,1,1,1],[1,1,1,1,2]]