Problem statement

In a grid, 0 is empty, 1 is a fresh orange, and 2 is a rotten orange. Every minute, fresh oranges 4-directionally adjacent to a rotten one become rotten.

Return the minimum minutes until no fresh orange remains, or -1 if that never happens.

Example 1

Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4

Example 2

Input: grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The bottom-left orange can never rot.

Example 3

Input: grid = [[0,2]]
Output: 0

Constraints

• 1 <= rows, cols <= 8
• grid[i][j] is 0, 1, or 2.

Hints for Rotting Oranges

1. Hint 1

   Multi-source BFS starting from ALL rotten oranges at once.

2. Hint 2

   Each BFS level is one minute; count remaining fresh oranges at the end.

How to solve Rotting Oranges

Rot spreads from every rotten orange simultaneously, so this is a multi-source BFS. Seed the queue with all initially rotten oranges at once and expand one full level per minute; the number of levels is the answer, and any fresh orange left unreached means it never rots.

Approach

1. Scan the grid: count the fresh oranges and enqueue every rotten one.
2. If there are no fresh oranges, return 0 immediately.
3. Process the queue level by level — each level is one minute.
4. For each rotten orange in the level, rot every fresh 4-directional neighbour, decrement the fresh count and enqueue it.
5. After the BFS, return the number of minutes if no fresh oranges remain, otherwise -1.

Why it works

Seeding all sources together makes the BFS compute, for every cell, the distance to its nearest rotten orange — which is exactly when it rots, since rot arrives along the shortest path. Because BFS visits cells in non-decreasing distance, counting levels counts minutes correctly. Any orange still fresh at the end is unreachable from every source, so no amount of waiting will rot it.

Complexity

• Time — O(rows · cols)
• Space — O(rows · cols)

Pitfalls

• Seed all rotten oranges before starting; running BFS from each one separately gives wrong times.
• A grid with no fresh oranges answers 0 even if there are no rotten ones either.
• Count levels, not cells — incrementing the minute per orange massively over-counts.
• Do not increment the minute for the seed level; the initial rotten oranges are at time zero.

Reference solution

Python

from typing import List
from collections import deque

def orangesRotting(grid: List[List[int]]) -> int:
    g = [row[:] for row in grid]
    R, C = len(g), len(g[0])
    fresh = 0
    queue = deque()
    for i in range(R):
        for j in range(C):
            if g[i][j] == 1:
                fresh += 1
            elif g[i][j] == 2:
                queue.append((i, j))
    minutes = 0
    while fresh > 0 and queue:
        nxt = deque()
        for i, j in queue:
            for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                ni, nj = i + di, j + dj
                if 0 <= ni < R and 0 <= nj < C and g[ni][nj] == 1:
                    g[ni][nj] = 2
                    fresh -= 1
                    nxt.append((ni, nj))
        queue = nxt
        if nxt:
            minutes += 1
    return minutes if fresh == 0 else -1

Java

public static int orangesRotting(int[][] grid) {
    int rows = grid.length, cols = grid[0].length;
    int[] dr = {-1, 1, 0, 0};
    int[] dc = {0, 0, -1, 1};
    int fresh = 0;
    List<int[]> queue = new ArrayList<>();
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (grid[i][j] == 1) fresh++;
            else if (grid[i][j] == 2) queue.add(new int[]{i, j});
        }
    }
    if (fresh == 0) return 0;
    int head = 0, minutes = 0;
    while (head < queue.size() && fresh > 0) {
        int levelEnd = queue.size();
        while (head < levelEnd) {
            int[] cell = queue.get(head++);
            for (int d = 0; d < 4; d++) {
                int nr = cell[0] + dr[d], nc = cell[1] + dc[d];
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1) {
                    grid[nr][nc] = 2;
                    fresh--;
                    queue.add(new int[]{nr, nc});
                }
            }
        }
        minutes++;
    }
    return fresh == 0 ? minutes : -1;
}

C++

int orangesRotting(vector<vector<int>>& grid) {
    int rows = (int) grid.size(), cols = (int) grid[0].size();
    int dr[4] = {-1, 1, 0, 0};
    int dc[4] = {0, 0, -1, 1};
    int fresh = 0;
    vector<pair<int, int>> queue;
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (grid[i][j] == 1) fresh++;
            else if (grid[i][j] == 2) queue.push_back(make_pair(i, j));
        }
    }
    if (fresh == 0) return 0;
    size_t head = 0;
    int minutes = 0;
    while (head < queue.size() && fresh > 0) {
        size_t levelEnd = queue.size();
        while (head < levelEnd) {
            pair<int, int> cell = queue[head++];
            for (int d = 0; d < 4; d++) {
                int nr = cell.first + dr[d], nc = cell.second + dc[d];
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1) {
                    grid[nr][nc] = 2;
                    fresh--;
                    queue.push_back(make_pair(nr, nc));
                }
            }
        }
        minutes++;
    }
    return fresh == 0 ? minutes : -1;
}

JavaScript

var orangesRotting = function(grid) {
    const g = grid.map(function(r) { return r.slice(); });
    const R = g.length, C = g[0].length;
    let fresh = 0;
    let queue = [];
    for (let i = 0; i < R; i++) {
        for (let j = 0; j < C; j++) {
            if (g[i][j] === 1) fresh++;
            else if (g[i][j] === 2) queue.push([i, j]);
        }
    }
    let minutes = 0;
    const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
    while (fresh > 0 && queue.length > 0) {
        const next = [];
        for (const cell of queue) {
            for (const d of dirs) {
                const ni = cell[0] + d[0], nj = cell[1] + d[1];
                if (ni >= 0 && nj >= 0 && ni < R && nj < C && g[ni][nj] === 1) {
                    g[ni][nj] = 2;
                    fresh--;
                    next.push([ni, nj]);
                }
            }
        }
        queue = next;
        if (next.length > 0) minutes++;
    }
    return fresh === 0 ? minutes : -1;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium