Rotting Oranges

Problem

Given a grid where 0 is empty, 1 is a fresh orange and 2 is a rotten orange, return the number of minutes until no fresh orange remains, or -1 if that is impossible.

Run a multi-source BFS from all initially rotten oranges, spreading to four-directional fresh neighbours one layer per minute. Return 0 when there are no fresh oranges.

Hint

Process the queue layer by layer so each full round of spreading counts as one minute.

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: [[[2]]]

expected: 0

case 6

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

expected: 1

Starter codePython

def oranges_rotten_minutes(grid):
    # Your code here
    pass

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