Rotting Oranges
- 2 min read
- Graph
- LC-Medium
3 years ago
Solution
- Just do a multi-source Breadth-first Search
- We don't need a visited set here to keep track of visited nodes because we can just use the actual grid itself
- Whenever considering a neighbour orange, mark it as rotten. This will serve as our marker for it being visited or not, and since we only check for fresh oranges in our neighbor-finding part of the algorithm, this approach works
- Set the oranges as rotten or mark as visited DURING THE NEIGHBOR FOR LOOP. If you don't, the same orange will be added to the queue multiple times. IMPORTANT!!!
- The queue at all points in time should only contain the rotten oranges.
| Time | Space | Explanation |
|---|---|---|
O(mn) | O(mn) |
def orangesRotting(self, grid: List[List[int]]) -> int:
nrows, ncols = len(grid), len(grid[0])
num_oranges = num_rotten = minutes = 0
q = deque()
for r in range(nrows):
for c in range(ncols):
if grid[r][c] == 2:
q.append((r, c))
if grid[r][c] > 0:
num_oranges += 1
while q:
for _ in range(len(q)):
r, c = q.popleft()
num_rotten += 1
for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
nr, nc = r + dr, c + dc
if nr >= 0 and nr < nrows and nc >= 0 and nc < ncols and grid[nr][nc] == 1:
grid[nr][nc] = 2
q.append((nr, nc))
if q:
minutes += 1
return minutes if num_rotten == num_oranges else -1