Rotting Oranges

Problem#

Grid cells: 0 empty, 1 fresh, 2 rotten. Each minute, every fresh adjacent to a rotten becomes rotten. Return the minutes until no fresh remain, or -1 if some can’t rot.

Examples#

[[2,1,1],[1,1,0],[0,1,1]] → 4.
[[2,1,1],[0,1,1],[1,0,1]] → -1; [[0,2]] → 0.

Constraints#

1 <= m, n <= 10.

Approach#

Multi-source BFS. Seed the queue with all initially rotten cells. Track fresh count. Process level by level; on rotting a fresh neighbor, decrement fresh. Answer is the level count when queue empties; if any fresh remain at end, return -1.

Solution#

class Solution {
public:
    int orangesRotting(vector<vector<int>>& g) {
        int m = g.size(), n = g[0].size(), fresh = 0;
        queue<pair<int,int>> q;
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j) {
                if (g[i][j] == 1) ++fresh;
                else if (g[i][j] == 2) q.push({i, j});
            }
        if (fresh == 0) return 0;
        int dr[4] = {-1, 1, 0, 0}, dc[4] = {0, 0, -1, 1};
        int minutes = 0;
        while (!q.empty()) {
            int sz = q.size();
            bool changed = false;
            while (sz--) {
                auto [r, c] = q.front(); q.pop();
                for (int k = 0; k < 4; ++k) {
                    int nr = r + dr[k], nc = c + dc[k];
                    if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
                    if (g[nr][nc] != 1) continue;
                    g[nr][nc] = 2;
                    --fresh;
                    q.push({nr, nc});
                    changed = true;
                }
            }
            if (changed) ++minutes;
        }
        return fresh == 0 ? minutes : -1;
    }
};

func orangesRotting(g [][]int) int {
    m, n := len(g), len(g[0])
    fresh := 0
    q := [][2]int{}
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if g[i][j] == 1 {
                fresh++
            } else if g[i][j] == 2 {
                q = append(q, [2]int{i, j})
            }
        }
    }
    if fresh == 0 {
        return 0
    }
    dr := []int{-1, 1, 0, 0}
    dc := []int{0, 0, -1, 1}
    minutes := 0
    for len(q) > 0 {
        sz := len(q)
        changed := false
        for ; sz > 0; sz-- {
            r, c := q[0][0], q[0][1]
            q = q[1:]
            for k := 0; k < 4; k++ {
                nr, nc := r+dr[k], c+dc[k]
                if nr < 0 || nr >= m || nc < 0 || nc >= n {
                    continue
                }
                if g[nr][nc] != 1 {
                    continue
                }
                g[nr][nc] = 2
                fresh--
                q = append(q, [2]int{nr, nc})
                changed = true
            }
        }
        if changed {
            minutes++
        }
    }
    if fresh == 0 {
        return minutes
    }
    return -1
}

from collections import deque
from typing import List

class Solution:
    def orangesRotting(self, g: List[List[int]]) -> int:
        m, n = len(g), len(g[0])
        fresh = 0
        q = deque()
        for i in range(m):
            for j in range(n):
                if g[i][j] == 1:
                    fresh += 1
                elif g[i][j] == 2:
                    q.append((i, j))
        if fresh == 0:
            return 0
        dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        minutes = 0
        while q:
            sz = len(q)
            changed = False
            for _ in range(sz):
                r, c = q.popleft()
                for dr, dc in dirs:
                    nr, nc = r + dr, c + dc
                    if nr < 0 or nr >= m or nc < 0 or nc >= n:
                        continue
                    if g[nr][nc] != 1:
                        continue
                    g[nr][nc] = 2
                    fresh -= 1
                    q.append((nr, nc))
                    changed = True
            if changed:
                minutes += 1
        return minutes if fresh == 0 else -1

function orangesRotting(g) {
    const m = g.length, n = g[0].length;
    let fresh = 0;
    const q = [];
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (g[i][j] === 1) fresh++;
            else if (g[i][j] === 2) q.push([i, j]);
        }
    }
    if (fresh === 0) return 0;
    const dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]];
    let minutes = 0;
    let head = 0;
    while (head < q.length) {
        let sz = q.length - head;
        let changed = false;
        while (sz-- > 0) {
            const [r, c] = q[head++];
            for (const [dr, dc] of dirs) {
                const nr = r + dr, nc = c + dc;
                if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
                if (g[nr][nc] !== 1) continue;
                g[nr][nc] = 2;
                fresh--;
                q.push([nr, nc]);
                changed = true;
            }
        }
        if (changed) minutes++;
    }
    return fresh === 0 ? minutes : -1;
}

class Solution {
    public int orangesRotting(int[][] g) {
        int m = g.length, n = g[0].length, fresh = 0;
        Deque<int[]> q = new ArrayDeque<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (g[i][j] == 1) fresh++;
                else if (g[i][j] == 2) q.offer(new int[]{i, j});
            }
        }
        if (fresh == 0) return 0;
        int[] dr = {-1, 1, 0, 0}, dc = {0, 0, -1, 1};
        int minutes = 0;
        while (!q.isEmpty()) {
            int sz = q.size();
            boolean changed = false;
            while (sz-- > 0) {
                int[] cell = q.poll();
                int r = cell[0], c = cell[1];
                for (int k = 0; k < 4; k++) {
                    int nr = r + dr[k], nc = c + dc[k];
                    if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
                    if (g[nr][nc] != 1) continue;
                    g[nr][nc] = 2;
                    fresh--;
                    q.offer(new int[]{nr, nc});
                    changed = true;
                }
            }
            if (changed) minutes++;
        }
        return fresh == 0 ? minutes : -1;
    }
}

function orangesRotting(g: number[][]): number {
    const m = g.length, n = g[0].length;
    let fresh = 0;
    const q: [number, number][] = [];
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (g[i][j] === 1) fresh++;
            else if (g[i][j] === 2) q.push([i, j]);
        }
    }
    if (fresh === 0) return 0;
    const dirs: [number, number][] = [[-1, 0], [1, 0], [0, -1], [0, 1]];
    let minutes = 0;
    let head = 0;
    while (head < q.length) {
        let sz = q.length - head;
        let changed = false;
        while (sz-- > 0) {
            const [r, c] = q[head++];
            for (const [dr, dc] of dirs) {
                const nr = r + dr, nc = c + dc;
                if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
                if (g[nr][nc] !== 1) continue;
                g[nr][nc] = 2;
                fresh--;
                q.push([nr, nc]);
                changed = true;
            }
        }
        if (changed) minutes++;
    }
    return fresh === 0 ? minutes : -1;
}

Editorial#

Multi-source BFS naturally handles “spread simultaneously from all infected sources” — each level corresponds to one minute. Only increment minutes when a level actually rotted something to avoid an off-by-one.

Complexity#

Time: O(m * n).
Space: O(m * n).

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#