Similar to Game of Life. The non rotted oranges get rotted every minutes if one our their 4 neighbors is rotted. As the rotting is done simultaneously every minute for every orange, we should wait until the end of the minute before modifying anything. Hence during the loop we store which non rotted orange will become rotted and we update everything at the end of the loop.
The goal is to find the minimum number of minutes before getting all oranges rotted. We keep a counter of non rotted oranges and we decrease it every minute. If some non rotted oranges remain but no new orange are rotted during a minute that it is impossible for every orange to finish rotted.
def orangesRotting(grid: List[List[int]]) -> int:
# number of non rotted orange
nb_orange = sum([1 for row in grid for orange in row if orange == 1])
minutes = 0
while nb_orange > 0:
set_rotting_orange = set() # keep rotting orange in a set as it will just be rotted at the end of the minute
for i in range(len(grid)):
for j in range(len(grid[0])):
# just check non rotted orange
if grid[i][j] == 1:
# if top or bottom orange is rotted
if (i > 0 and grid[i-1][j] == 2) or (i < len(grid) - 1 and grid[i+1][j] == 2):
set_rotting_orange.add((i, j))
# if left or right orange is rotted
elif (j > 0 and grid[i][j-1] == 2) or (j < len(grid[0]) - 1 and grid[i][j+1] == 2):
set_rotting_orange.add((i, j))
minutes += 1
nb_orange -= len(set_rotting_orange) # update number of non rotted oranges
# update rotted oranges
for (i, j) in set_rotting_orange:
grid[i][j] = 2
# if no orange are rotting this round but oranges remain unrotted hence impossible for every orange to finish rotted
if len(set_rotting_orange) == 0:
return(-1)
return(minutes)