Rotting Oranges

mediumGraphs: BFS / DFS179 stepsJava · Python · C++

Every minute, rotten oranges rot their fresh neighbours. Start a BFS from all rotten oranges at once; each BFS layer is one minute. If fresh oranges remain at the end, return -1.

▶ Watch the animated trace

Traced input: grid = [[2, 1, 1], [1, 1, 0], [0, 1, 1]] → 4. Original problem: neetcode.io/problems/rotting-fruit

Complexity

BestO(m·n)

AverageO(m·n)

WorstO(m·n)

SpaceO(m·n)

Each orange enters the queue at most once.

Key idea

All initially rotten oranges spread at the same time: put them all in the queue first.
Process the queue level by level; each level is one minute.
Count fresh oranges up front and decrement as they rot.
Fresh oranges left over can't be reached: -1.

Common mistakes

Running a separate BFS from each rotten orange gives wrong times.
Counting a minute for the last level even though nothing new rotted.
Returning 0 vs -1 when there are no fresh oranges at all (answer 0).

Solution

Java

// DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}: down, up, right, left
int orangesRotting(int[][] grid) {
    int m = grid.length, n = grid[0].length, fresh = 0;
    Queue<int[]> queue = new ArrayDeque<>();
    for (int r = 0; r < m; r++)
        for (int c = 0; c < n; c++) {
            if (grid[r][c] == 2) queue.offer(new int[]{r, c});
            if (grid[r][c] == 1) fresh++;
        }
    int minutes = 0;
    while (!queue.isEmpty() && fresh > 0) {
        minutes++;
        for (int size = queue.size(); size > 0; size--) {
            int[] cell = queue.poll();
            for (int[] d : DIRS) {
                int r = cell[0] + d[0], c = cell[1] + d[1];
                if (r < 0 || c < 0 || r >= m || c >= n || grid[r][c] != 1) continue;
                grid[r][c] = 2;
                fresh--;
                queue.offer(new int[]{r, c});
            }
        }
    }
    return fresh == 0 ? minutes : -1;
}

Python

# DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]: down, up, right, left
def orangesRotting(grid: List[List[int]]) -> int:
    m, n = len(grid), len(grid[0])
    queue = deque((r, c) for r in range(m) for c in range(n) if grid[r][c] == 2)
    fresh = sum(row.count(1) for row in grid)
    minutes = 0
    while queue and fresh > 0:
        minutes += 1
        for _ in range(len(queue)):
            r, c = queue.popleft()
            for dr, dc in DIRS:
                nr, nc = r + dr, c + dc
                if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1:
                    grid[nr][nc] = 2
                    fresh -= 1
                    queue.append((nr, nc))
    return minutes if fresh == 0 else -1

C++

// DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}: down, up, right, left
int orangesRotting(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size(), fresh = 0;
    queue<pair<int, int>> q;
    for (int r = 0; r < m; r++)
        for (int c = 0; c < n; c++) {
            if (grid[r][c] == 2) q.push({r, c});
            if (grid[r][c] == 1) fresh++;
        }
    int minutes = 0;
    while (!q.empty() && fresh > 0) {
        minutes++;
        for (int size = q.size(); size > 0; size--) {
            auto [r0, c0] = q.front(); q.pop();
            for (auto& d : DIRS) {
                int r = r0 + d[0], c = c0 + d[1];
                if (r < 0 || c < 0 || r >= m || c >= n || grid[r][c] != 1) continue;
                grid[r][c] = 2;
                fresh--;
                q.push({r, c});
            }
        }
    }
    return fresh == 0 ? minutes : -1;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Unreachable orange The bottom-left orange is cut off by empty cells.	`grid = [[2, 1, 1], [0, 1, 1], [1, 0, 1]]`	`-1`
No fresh oranges Nothing needs to rot.	`grid = [[0, 2]]`	`0`
No rotten oranges Nothing can start the rot.	`grid = [[1]]`	`-1`
Two sources Both ends rot inward in the same minute.	`grid = [[2, 1, 1, 2]]`	`1`