Rotting Oranges 25 XP Medium

LeetCode Ctrl+Enter Run Ctrl+S Save

You have a grid where 0 = empty, 1 = fresh orange, 2 = rotten orange. Every minute, fresh oranges adjacent (4-directionally) to rotten ones become rotten. Return the minimum minutes until no fresh orange remains, or -1 if impossible.

grid = [[2,1,1],
        [1,1,0],
        [0,1,1]]
# Minute 0: Only (0,0) is rotten
# Minute 1: (0,1) and (1,0) rot
# Minute 2: (0,2), (1,1) rot
# Minute 3: (2,1) rots
# Minute 4: (2,2) rots
# Answer: 4 minutes

This is a classic multi-source BFS problem:

Start by adding ALL rotten oranges to the queue (multi-source)
BFS level by level — each level = 1 minute
Each rotten orange spreads to 4 neighbors (up/down/left/right)
If fresh oranges remain after BFS, return -1

Think of it as a flood fill spreading from multiple sources simultaneously. Time: O(m×n).

📋 Instructions

Implement `oranges_rotting(grid)` using multi-source BFS. Test with the provided grid.

First, find all rotten oranges and count fresh ones. Add all rotten to a deque. BFS: for each level, spread rot to 4 neighbors. Track minutes. After BFS, if fresh_count > 0, return -1.

🧪 Test Cases

Input

oranges_rotting(grid)

Expected

4

Test case 1

← Previous Next Exercise →

main.py

Hi! I'm Rex 👋

from collections import deque

def oranges_rotting(grid):
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0
    
    # Find all rotten oranges and count fresh
    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
    
    if fresh == 0:
        return 0
    
    minutes = 0
    directions = [(0,1),(0,-1),(1,0),(-1,0)]
    
    while queue and fresh > 0:
        minutes += 1
        for _ in range(len(queue)):
            r, c = queue.popleft()
            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
                    fresh -= 1
                    # Add newly rotten orange to queue
                    pass
    
    return minutes if fresh == 0 else -1

grid = [[2,1,1],[1,1,0],[0,1,1]]
print(oranges_rotting(grid))

Output

Ready. Press ▶ Run or Ctrl+Enter.

›