Rotting Oranges

LeetCode: https://leetcode.com/problems/rotting-oranges/

You are given an m x n grid where:

0 = empty
1 = fresh orange
2 = rotten orange

Every minute, fresh oranges adjacent to rotten oranges become rotten. Return the minimum minutes needed, or -1 if impossible.

Example:

Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4

1from collections import deque
2
3def orangesRotting(grid: List[List[int]]) -> int:
4    rows, cols = len(grid), len(grid[0])
5    q = deque()
6    fresh = 0
7    
8    for r in range(rows):
9        for c in range(cols):
10            if grid[r][c] == 2:
11                q.append((r, c))
12            elif grid[r][c] == 1:
13                fresh += 1
14    
15    minutes = 0
16    dirs = [(1,0), (-1,0), (0,1), (0,-1)]
17    
18    while q and fresh > 0:
19        for _ in range(len(q)):
20            r, c = q.popleft()
21            for dr, dc in dirs:
22                nr, nc = r + dr, c + dc
23                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
24                    grid[nr][nc] = 2
25                    fresh -= 1
26                    q.append((nr, nc))
27        minutes += 1
28    
29    return minutes if fresh == 0 else -1

Flood Fill

Chess Moves

minutes=0

fresh=6

Step 1 / 3

Step 1:

Initialize the BFS frontier with all rotten oranges and count fresh ones.

Focus: select @ [0]

minutes=0fresh=6