⚠️ This visualization was AI-generated and may contain inaccuracies. Please verify against the original LeetCode problem (#994) before relying on it.

Rotting Oranges

An interactive visualization of multi-source BFS. Watch how rot spreads simultaneously from all initially rotten oranges, level by level, one minute at a time.

BFS LeetCode 994 ↗ Medium

The Problem

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

0 — an empty cell
1 — a fresh orange
2 — 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.

Interactive Visualization

Grid (2D Array)

Preset

Speed:

Grid

Minutes 0

Fresh Left 0

Empty (0)

Fresh (1)

Rotten (2)

Code

fun orangesRotting(grid: Array<IntArray>): Int {    val rows = grid.size; val cols = grid[0].size    val queue = ArrayDeque<Pair<Int,Int>>()    var fresh = 0    for (r in 0 until rows)     // scan grid        for (c in 0 until cols)            if (grid[r][c] == 2)                queue.add(r to c)            else if (grid[r][c] == 1)                fresh++    var minutes = 0    val dirs = listOf(0 to 1, 0 to -1, 1 to 0, -1 to 0)    while (queue.isNotEmpty() && fresh > 0) {        repeat(queue.size) {            val (r, c) = queue.removeFirst()            for ((dr, dc) in dirs) {                val nr = r+dr; val nc = c+dc                if (nr in 0 until rows && nc in 0 until cols && grid[nr][nc]==1) {                    grid[nr][nc] = 2                    fresh--                    queue.add(nr to nc)        } } }; minutes++ }    return if (fresh > 0) -1 else minutes

def orangesRotting(grid):    rows, cols = len(grid), len(grid[0])    queue = deque()    fresh = 0    for r in range(rows):        # scan grid        for c in range(cols):            if grid[r][c] == 2:                queue.append((r, c))            elif grid[r][c] == 1:                fresh += 1    minutes = 0    dirs = [(0,1),(0,-1),(1,0),(-1,0)]    while queue and fresh > 0:        for _ in range(len(queue)):            r, c = queue.popleft()            for dr, dc in dirs:                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 -1 if fresh > 0 else minutes

BFS Queue

Empty

Current Step

Press Step or Play to begin.

How It Works

Key Insight

This is a classic multi-source BFS problem. Instead of starting BFS from a single node, we enqueue all initially rotten oranges at once. Each BFS level represents one minute of time passing, during which all currently rotten oranges spread rot to their fresh neighbors simultaneously.

The Algorithm

Scan the grid to find all initially rotten oranges and add them to the queue. Also count the total number of fresh oranges.
BFS level by level: Process all oranges currently in the queue (one full "minute"). For each rotten orange, check its 4 neighbors (up, down, left, right).
Spread the rot: If a neighbor is a fresh orange, mark it as rotten, decrement the fresh count, and add it to the queue for the next minute.
Increment minutes after processing each full level.
Termination: When the queue is empty or no fresh oranges remain, check: if fresh > 0, return -1 (impossible). Otherwise, return minutes.

Why Multi-Source BFS?

By starting with all rotten oranges in the queue at "time 0", the BFS naturally simulates the simultaneous spread of rot. Each level of the BFS corresponds to exactly one minute. This is equivalent to adding a virtual "super source" node connected to all initial rotten oranges, then running standard BFS.

Complexity

Time O(m * n)

Space O(m * n)

Every cell is visited at most once during BFS, giving O(m*n) time. The queue can hold at most all cells in the worst case, so space is O(m*n).