Related: Walls and Gates
TARGET DECK: Leetcode FILE TAGS:
Intuition
- Multi source BFS wherein:
- Place each rotten orange in a queue
- Infect all of the oranges adjacent to each of the rotten oranges (just once)
- Continue to infect until all are infected.
- Cases:
- If there are no fresh oranges, then there is nothing to infect. Return 0
- If there are no rotten oranges to infect with, but there are fresh oranges, return -1
- Otherwise, use BFS with all the rotten oranges as starting sources.
- If you cannot infect all the oranges by the time you are done with BFS, then it is impossible to infect them all. Return -1
- Else return the number of iterations it took to infect them all. Notice that your iterations must start at -1, since the initial rotten oranges are at time 0, and so you haven’t begun infecting anything yet.
Cards
START Basic Front: Rotting Oranges - LeetCode Back: Multi Source BFS, and you count both the fresh oranges and rotten oranges in the global loop. The final iteration of the while q loop doesn’t matter since you will have already made every fresh orange rotten.
END
Complexity
Runtime
, where M is the rows and N is the columns, since we have to traverse through every row and column to initially find the rotten and fresh oranges. Multi source BFS runs in since every element in the grid is visited once.
Space
since the queue could contain all elements in the grid (every element in the grid is a rotten orange).
Code
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
def adj(r, c):
res = []
for (i, j) in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]:
if 0 <= i < m and 0 <= j < n:
res.append((i, j))
return res
def bfs(q):
nonlocal fresh_oranges
iterations = 0
while q and fresh_oranges > 0:
iterations += 1
for _ in range(len(q)):
rotten_r, rotten_c = q.popleft()
for i, j in adj(rotten_r, rotten_c):
if grid[i][j] == 1:
grid[i][j] = 2
fresh_oranges -= 1
q.append((i, j))
return iterations
# Pass in all initially rotten oranges
fresh_oranges = 0
q = deque()
for r in range(m):
for c in range(n):
if grid[r][c] == 1:
fresh_oranges += 1
elif grid[r][c] == 2:
q.append((r, c))
# Nothing to infect
if fresh_oranges == 0:
return 0
# No rotten oranges to infect with
if not q:
return -1
# Number of iterations to infect all possible oranges
iterations = bfs(q)
# Wasn't able to infect all of them
if fresh_oranges != 0:
return -1
return iterations