Rotting Oranges

Problem Description

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
• 2 representing a rotten orange

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

Return the minimum number of minutes that must elapse until no fresh oranges remain. If this is impossible, return -1.

Examples

Constraints

• m == grid.length
• n == grid[i].length
• 1 ≤ m, n ≤ 10
• grid[i][j] is 0, 1, or 2

Multi-Source BFS: Start From All Rotten Oranges at Once

This isn’t a single-source shortest path. All rotten oranges rot their neighbors simultaneously. That’s multi-source BFS: seed the queue with all initially rotten oranges, then expand level by level. Each BFS level corresponds to one minute.

Count fresh oranges upfront. After BFS completes, if any fresh oranges remain, they’re unreachable. Return the number of BFS levels processed (minus 1, since the last level doesn’t increment minutes), or -1 if fresh oranges remain.

Solution: Multi-Source BFS

import java.util.*;

class Solution {
    public int orangesRotting(int[][] grid) {
        int rows = grid.length, cols = grid[0].length;
        Queue<int[]> queue = new LinkedList<>();
        int fresh = 0;

        // seed queue with all initially rotten oranges
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == 2) queue.offer(new int[]{r, c});
                else if (grid[r][c] == 1) fresh++;
            }
        }

        if (fresh == 0) return 0; // no fresh oranges to rot

        int minutes = 0;
        int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};

        while (!queue.isEmpty() && fresh > 0) {
            minutes++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] cell = queue.poll();
                for (int[] d : dirs) {
                    int nr = cell[0] + d[0], nc = cell[1] + d[1];
                    if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1) {
                        grid[nr][nc] = 2; // rot it
                        fresh--;
                        queue.offer(new int[]{nr, nc});
                    }
                }
            }
        }

        return fresh == 0 ? minutes : -1;
    }
}

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

        if fresh == 0:
            return 0

        minutes = 0
        dirs = [(1,0),(-1,0),(0,1),(0,-1)]

        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 < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                        grid[nr][nc] = 2
                        fresh -= 1
                        queue.append((nr, nc))

        return minutes if fresh == 0 else -1

#include <vector>
#include <queue>

class Solution {
public:
    int orangesRotting(std::vector<std::vector<int>>& grid) {
        int rows = grid.size(), cols = grid[0].size();
        std::queue<std::pair<int,int>> q;
        int fresh = 0;

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == 2) q.push({r, c});
                else if (grid[r][c] == 1) fresh++;
            }
        }

        if (fresh == 0) return 0;

        int minutes = 0;
        int dirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};

        while (!q.empty() && fresh > 0) {
            minutes++;
            int sz = q.size();
            while (sz--) {
                auto [r, c] = q.front(); q.pop();
                for (auto& d : dirs) {
                    int nr = r + d[0], nc = c + d[1];
                    if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1) {
                        grid[nr][nc] = 2;
                        fresh--;
                        q.push({nr, nc});
                    }
                }
            }
        }

        return fresh == 0 ? minutes : -1;
    }
};

Complexity Analysis:

• Time Complexity: O(m * n). Every cell is visited at most once.
• Space Complexity: O(m * n) for the queue in the worst case (all cells are rotten).

Where it breaks: if all oranges start fresh and there are no rotten ones, BFS never runs and returns -1 correctly. The if (fresh == 0) return 0 handles the case where there are no fresh oranges at all. Both edge cases must be handled explicitly.

Common Mistakes

• Not tracking the number of BFS levels correctly. Incrementing minutes inside the inner loop (per cell) instead of per level gives wrong results. Process the entire current level before incrementing.
• Returning minutes - 1 as an off-by-one fix. The cleaner approach is to only increment minutes when there are actually fresh oranges to rot, or check fresh == 0 before the outer loop.
• Missing the case where fresh == 0 initially. If there are no fresh oranges, the answer is 0, not -1. The queue might be empty too, so the loop doesn’t run.

Frequently Asked Questions

Why is this multi-source BFS and not single-source? All rotten oranges rot their neighbors in parallel, not sequentially. Multi-source BFS captures this by starting from all rotten oranges simultaneously, so BFS levels correctly represent minutes elapsed.

Does it matter that we modify the grid in place? No, for this problem. The grid is used only for traversal and isn’t needed after the function returns. If the original must be preserved, use a separate visited array.

← All Problems