ToolMight LogoToolMight
MediumGraphs & Matrix WalksPattern: Multi-Source BFSPattern: Queue Matrix Level Expansion

Rotting Oranges

Determine the minimum minutes needed until all fresh oranges rot. The premier problem for learning Multi-Source Breadth-First Search (BFS) in grid matrices.

Problem Statement

You are given an m x n grid where each cell can have one of three values:

  • 0 representing an empty cell,
  • 1 representing a fresh orange, or
  • 2 representing a rotten orange.

Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.

Examples & Constraints

Example 1
Input: grid = [ [2, 1, 1], [1, 1, 0], [0, 1, 1] ]
Output: 4
Explanation: Minute 0: [0, 0] is rotten. Minute 1: [0, 1] and [1, 0] rot. Minute 2: [0, 2] and [1, 1] rot. Minute 3: [2, 1] rots. Minute 4: [2, 2] rots.
Example 2
Input: grid = [ [2, 1, 1], [0, 1, 1], [1, 0, 1] ]
Output: -1
Explanation: The orange in the bottom left corner (row 2, column 0) is never reached because rotting only happens 4-directionally.
Constraints
  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 10
  • grid[i][j] is 0, 1, or 2.

Multi-Source BFS with Level Snapshot

Optimal Approach
Time:O(m * n)
Space:O(m * n)

Enqueue all initially rotten oranges simultaneously at minute 0. Expand outwards level by level: each level represents 1 minute. Decrement fresh orange count until the queue empties.

Time ComplexityO(m * n)

Every cell in the M x N grid is visited at most once during the initial scan and at most once during the BFS queue operations.

Space ComplexityO(m * n)

The BFS queue can hold at most M x N orange coordinates in the worst case.

Underlying algorithmic logic

Why DFS Fails for Simultaneous Spreading

In problems where multiple sources spread infection simultaneously (wildfires, virus contagion, rotting oranges), a standard DFS will trace one path deep to the end, recording incorrect time timestamps.

Instead, all rotten oranges spread their rot in parallel minute by minute. This is the definition of Multi-Source Breadth-First Search (BFS).

The Algorithm:

  1. Initial Scan:
  • Count the total number of fresh oranges (freshCount).
  • Collect the coordinates of all rotten oranges '2' and push them into a FIFO queue.
  • If freshCount == 0, return 0 immediately (no work needed).
  1. Level-by-Level Expansion:
  • Initialize minutesElapsed = 0.
  • While the queue is not empty and freshCount > 0:
  • Record levelSize = queue.size().
  • For each node in the current level:
  • Inspect all 4 neighbors: Up, Down, Left, Right.
  • If a neighbor is a fresh orange (grid[nr][nc] == 1):
  • Rot it: grid[nr][nc] = 2.
  • Decrement freshCount--.
  • Enqueue (nr, nc).
  • After finishing all nodes in the level, increment minutesElapsed++.
  1. Completion Check:
  • If freshCount == 0, return minutesElapsed.
  • If freshCount > 0, some fresh oranges were isolated and could never be reached; return -1.

Step-by-step execution walkthrough

1
Initial Scan (Minute 0)

Rotten at (0, 0). Enqueue (0, 0). Total fresh oranges = 6. minutes = 0.

queue = [(0, 0)], fresh = 6
2
Minute 1 (First Expansion)

Pop (0, 0). Infect neighbors (0, 1) and (1, 0). Enqueue both. fresh drops to 4. minutes = 1.

queue = [(0, 1), (1, 0)], fresh = 4, minutes = 1
3
Minute 2

Pop (0, 1) and (1, 0). Infect (0, 2) and (1, 1). fresh drops to 2. minutes = 2.

queue = [(0, 2), (1, 1)], fresh = 2, minutes = 2
4
Minutes 3 & 4 (Complete)

Minute 3 infects (2, 1). Minute 4 infects (2, 2). fresh reaches 0! Return 4.

fresh = 0 -> return 4
Advantages
  • •Optimal O(m * n) runtime
  • •Simulates realistic simultaneous time expansion cleanly
Trade-offs
  • •Consumes queue memory proportional to grid size

Code Implementations

Copy & paste production-ready solutions for Multi-Source BFS with Level Snapshot in your language of choice

File: solution.py
Python
from collections import deque
def oranges_rotting(grid: list[list[int]]) -> int:
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0
    # Step 1: Scan grid
    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 = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    # Step 2: Multi-source BFS
    while queue and fresh > 0:
        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
                    queue.append((nr, nc))
        minutes += 1
    return minutes if fresh == 0 else -1
if __name__ == "__main__":
    grid1 = [
        [2, 1, 1],
        [1, 1, 0],
        [0, 1, 1]
    ]
    grid2 = [
        [2, 1, 1],
        [0, 1, 1],
        [1, 0, 1]
    ]
    print("grid1 minutes:", oranges_rotting(grid1))
    print("grid2 minutes:", oranges_rotting(grid2))
Interactive visualizer available

Understand BFS & DFS Visually

Traverse complex graph networks using level-order queues and depth-first stacks. Test live edge cases and watch memory state transitions step-by-step.

Launch BFS & DFS Visualizer

Frequently Asked Questions

Related Logic & Algorithm Problems

All problems
MediumGraphs & Matrix Walks
Visualizer

Number of Islands

Count the number of distinct islands in a 2D binary grid. The definitive problem for learning connected components and matrix flood-fill traversals.

1 approach(O(m * n))
Learn logic
MediumTrees & BST
Visualizer

Binary Tree Level Order Traversal

Return the level order traversal of a binary tree's node values from left to right, level by level. The premier problem for learning FIFO queue BFS level snapshots.

1 approach(O(n))
Learn logic