naive solution
class Solution:
# main idea: count fresh orange ; loop fresh. do BFS to rot oranges by decreasing fresh; count days each loop. each loop check if fresh changes. if not, return -1
# note
# time O(h*w*(h+w)) space O(1)
def orangesRotting(self, grid: List[List[int]]) -> int:
def rot(grid,i,j,days):
if i < 0 or j < 0 or j >= len(grid[0]) or i >=len(grid) or grid[i][j]!=1:
return 0
# # be aware rotten orange neighbour start changing at day 0, in order to make neighbour increment by 1 from 2, days+3
grid[i][j] = days + 3
return 1
fresh,days = 0,0
row = len(grid)
col = len(grid[0])
for i in range(row):
for j in range(col):
if grid[i][j] == 1:
fresh += 1
old_fresh = fresh
while fresh > 0:
old_fresh = fresh
for i in range(row):
for j in range(col):
# find the rotten ones in the beginning
if grid[i][j] == (days +2):
fresh -= rot(grid,i+1,j,days) + rot(grid,i-1,j,days) + rot(grid,i,j+1,days) + rot(grid,i,j-1,days)
if fresh == old_fresh:
return -1
days+=1
return days
edge case: (1)if grid valid: not empty; (2)if no rotten: return 0 (3) set day= -1
step1. iterate all in the grid, get the coordinates of rotten and fresh oranges and save them to set seperately
step2: set up direction
step3: check neighbors of rotten ones (with direction), if they are in fresh set, if yes =>
update to new_rotten; if no => return -1 ; update time ++
step4 loop step 3 until fresh is None, then return
class Solution:
# main idea: record
#time O(m*n) space O(m*n)
def orangesRotting(self, grid: List[List[int]]) -> int:
self.q = collections.deque()
self.cnt_fresh = 0
row = len(grid)
col = len(grid[0])
self.days = -1
def count(grid,q):
numFresh = 0
row = len(grid)
col = len(grid[0])
for i in range(row):
for j in range(col):
if grid[i][j] == 2:
q.append((i,j))
if grid[i][j] == 1:
numFresh += 1
return q, numFresh
self.q,self.cnt_fresh = count(grid,self.q)
#step2: store 4 directions
direction = [(0,1),(0,-1),(1,0),(-1,0)]
if self.cnt_fresh == 0:
return 0
while self.q:
size = len(self.q)
self.days += 1
for i in range(size):
x, y = self.q.popleft()
for a,b in direction:
x_new, y_new = x + a, y + b
# edge case for out of range
if x_new >= row or x_new < 0 or y_new < 0 or y_new >= col:
continue
if grid[x_new][y_new] == 1:
grid[x_new][y_new] = 2
self.cnt_fresh -= 1
self.q.append((x_new, y_new))
if self.cnt_fresh != 0:
return -1
else:
return self.days
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
# bfs time O(MN) space O(MN)
# step0, initialize minutes=0, infected orange = 0
# step1, cnt all goood oranges
# step2 find rotten grid[i][j] == 2, go four directions
# step3 if grid[m][n] == 1, set to 2, update infected and minutes
# step4 return minutes if good == infected else -1
minutes =-1
good = 0
rows = len(grid)
cols = len(grid[0])
if not rows:
return -1
# cnt good ones and cache bad ones coorditnate
q = collections.deque()
for i in range(rows):
for j in range(cols):
if grid[i][j] == 1:
good += 1
elif grid[i][j] == 2:
q.append((i,j))
# early termination
if good == 0:
return 0
while q :
minutes += 1
size = len(q)
for k in range(size):
i,j = q.popleft()
for dx,dy in [[1,0],[-1,0],[0,1],[0,-1]]:
x = i + dx
y = j + dy
if x< 0 or x >= rows or y < 0 or y >= cols :
continue
if grid[x][y] == 1:
grid[x][y] = 2
good -= 1
q.append((x,y))
return minutes if good == 0 else -1