DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Rotting Oranges

mediumGraphs Must-do

Problem statement

You get a grid where each cell is 0 (empty), 1 (a fresh orange) or 2 (a rotten orange). Every minute, each fresh orange that is directly up, down, left or right of a rotten orange becomes rotten.

Return the number of minutes until no fresh orange is left. If some fresh orange can never be reached, return -1. If there are no fresh oranges at the start, the answer is 0.

Examples

Example 1

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

Output: 4

Explanation: The rot moves (0,1) at minute 1, (1,1) at 2, (1,2) at 3 and (2,2) at 4.

Example 2

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

Output: -1

Explanation: The empty cell blocks the only path to the fresh orange.

Hints

Approach

Multi-source breadth-first search. Put every initially rotten orange in the queue as the starting frontier, then expand one layer per minute.

  1. Scan once: queue every 2, count every 1 as fresh.
  2. While the queue is not empty and fresh > 0, process exactly the cells currently in the queue (one minute's worth). For each, rot any fresh neighbour, decrement fresh, and queue it.
  3. After each layer, add one minute.
  4. Return the minutes if fresh == 0, otherwise -1.

Each cell enters the queue at most once, so the whole thing is linear. Stopping when fresh hits zero avoids counting an extra, empty minute after the last orange rots.

ComplexityTime O(m * n)Space O(m * n)
Python
from collections import deque
class Solution:
def orangesRotting(self, grid: list[list[int]]) -> int:
rows, cols = len(grid), len(grid[0])
queue = deque()
fresh = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == 2:
queue.append((r, c))
elif grid[r][c] == 1:
fresh += 1
minutes = 0
while queue and fresh > 0:
for _ in range(len(queue)): # one minute = one layer
r, c = queue.popleft()
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
grid[nr][nc] = 2
fresh -= 1
queue.append((nr, nc))
minutes += 1
return minutes if fresh == 0 else -1

Follow-up questions

  • Return the minute at which each individual orange rots.
  • Some cells are walls and the rot can also spread diagonally. What changes in the code?

Frequently asked questions

Because they spread simultaneously. A fresh orange rots at the minute of its nearest rotten source, and a single BFS seeded with every source computes exactly that. Separate searches would repeat work and still need merging.

It models anything that spreads one hop per tick from several starting points: a bad config rolling from a few seeded hosts to their neighbours, a failure cascading across adjacent nodes, or gossip-protocol membership updates. The question "how many rounds until everyone has it, and is anyone unreachable?" is the same.