Rotting Oranges Minutes

Problem

In a grid, 0 is empty, 1 is a fresh orange, and 2 is a rotten orange. Every minute, fresh oranges adjacent (4-directionally) to a rotten orange become rotten.

Return the number of minutes until no fresh orange remains, or -1 if that never happens. A grid with no fresh oranges takes 0 minutes.

Hint

Start BFS from every rotten orange at once and process one minute per level.

Test cases

case 1

in: [[[2,1,1],[1,1,0],[0,1,1]]]

expected: 4

case 2

in: [[[2,1,1],[0,1,1],[1,0,1]]]

expected: -1

case 3

in: [[[0,2]]]

expected: 0

case 4

in: [[[1]]]

expected: -1

case 5

in: [[[1,2]]]

expected: 1

Starter codePython

def oranges_rotting(grid):
    # Your code here
    pass

5 test cases · run your code against them in the editor