Medium

Rotting Oranges

LAB

Given a grid of empty cells, fresh oranges, and rotten oranges, return minutes until all fresh oranges rot, or -1.

EXAMPLES

Example 1

Input
{
  "grid": [
    [
      2,
      1,
      1
    ],
    [
      1,
      1,
      0
    ],
    [
      0,
      1,
      1
    ]
  ]
}

Output
4

FUNCTION SHAPE

grid: intMatrix→int

SOLUTION NOTE

Clearly, we want to simulate the process by starting at all rotten oranges and rotting the fresh ones. Because we want the minimum number of moves, this process is best simulated via BFS.

Reveal reference solution +

pythonREFERENCE

def orangesRotting(self, grid: List[List[int]]) -> int:
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0

    # Step 1: Initialize queue with all rotten oranges
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c, 0))  # (row, col, time)
            elif grid[r][c] == 1:
                fresh += 1

    # Step 2: BFS to rot adjacent fresh oranges
    time = 0
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    while queue:
        r, c, t = queue.popleft()
        time = t
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                grid[nr][nc] = 2  # Rot it
                fresh -= 1
                queue.append((nr, nc, t + 1))

    return time if fresh == 0 else -1

TimeO(m*n)

SpaceO(m*n)

Open on LeetCode ↗