Rotting Oranges

MEDIUM✓ CHIP-TIMEDLC #994 — FULL STATEMENT ↗

The drill: Rotten oranges spread to orthogonally adjacent fresh ones once per minute, all at once. Return the number of minutes until no fresh orange remains, or −1 if some fresh orange can never be reached.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A grid of oranges holds three states per cell: empty, fresh, or rotten. Every minute, each rotten orange turns every orthogonally adjacent fresh orange rotten too, and this happens simultaneously across the whole grid, minute by minute.

The task is to report how many minutes pass until no fresh orange is left anywhere on the grid — a fresh orange with no path of adjacency back to any rotten one, ever, means the spread can't finish.

When that happens — some fresh orange permanently unreachable — the answer is −1 instead of a minute count. A grid that starts with zero fresh oranges takes zero minutes.

EX 01

grid = [[0, 2], [2, 0]]

→ 0

NO FRESH ORANGES AT ALL

EX 02

grid = [[1]]

→ -1

SINGLE FRESH ORANGE, NO ROT TO SPREAD

EX 03

grid = [[2, 1]]

→ 1

ONE ROTTEN SPREADS TO ONE FRESH

grid up to a few hundred cells per side
each cell is 0 (empty), 1 (fresh), or 2 (rotten)
spread is 4-directional and happens all at once each minute
an unreachable fresh orange makes the whole answer −1

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Every rotten orange spreads to its neighbours at the same moment — minute by minute, not one orange chasing the whole grid alone. What search naturally processes things ring by ring?

HINT 2 THE STRUCTURE

Multi-source BFS starting from every rotten orange at once: each BFS layer is exactly one minute, and a fresh orange rots the first — and only — time it's reached.

HINT 3 ONE STEP FROM THE ANSWER

Seed the queue with every rotten orange at minute 0, expand outward turning fresh neighbours rotten and enqueuing them; track the minute of the last cell rotted, and if any fresh orange never gets visited, the answer is −1.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE MINUTE-BY-MINUTE SPREADPATTERN · MULTI-SOURCE BFSgrid = [[2,1,1],[1,1,1],[1,1,1]]

STEP 1

One rotten orange seeds the queue at minute 0. Every rotten cell spreads to its fresh neighbors simultaneously, layer by layer.

STEP 1 / 6 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/rotting-oranges.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        queue = collections.deque()
        fresh = 0
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 2:
                    queue.append((r, c, 0))
                elif grid[r][c] == 1:
                    fresh += 1

        minutes = 0
        while queue:
            r, c, t = queue.popleft()
            minutes = max(minutes, t)
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                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, t + 1))
        return minutes if fresh == 0 else -1

TIME O(ROWS·COLS)SPACE O(ROWS·COLS)PYTHON · RACE PACE · 23 LN

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        grid = [row[:] for row in grid]  # work on a copy, never mutate the caller's grid
        minutes = 0
        while True:
            fresh_exists = any(cell == 1 for row in grid for cell in row)
            if not fresh_exists:
                return minutes
            to_rot = []
            for r in range(rows):
                for c in range(cols):
                    if grid[r][c] == 2:
                        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                            nr, nc = r + dr, c + dc
                            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                                to_rot.append((nr, nc))
            if not to_rot:
                return -1  # fresh oranges remain but nothing can reach them
            for nr, nc in to_rot:
                grid[nr][nc] = 2
            minutes += 1

TIME O((ROWS·COLS)²) WORST CASESPACE O(ROWS·COLS)PYTHON · TRAINING PACE · 22 LN

class Solution {
    public int orangesRotting(int[][] grid) {
        int rows = grid.length, cols = grid[0].length;
        Deque<int[]> queue = new ArrayDeque<>();
        int fresh = 0;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == 2) queue.add(new int[]{r, c, 0});
                else if (grid[r][c] == 1) fresh++;
            }
        }

        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        int minutes = 0;
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            minutes = Math.max(minutes, cur[2]);
            for (int[] d : dirs) {
                int nr = cur[0] + d[0], nc = cur[1] + d[1];
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1) {
                    grid[nr][nc] = 2;
                    fresh--;
                    queue.add(new int[]{nr, nc, cur[2] + 1});
                }
            }
        }
        return fresh == 0 ? minutes : -1;
    }
}

TIME O(ROWS·COLS)SPACE O(ROWS·COLS)JAVA · RACE PACE · 29 LN

class Solution {
    public int orangesRotting(int[][] input) {
        int rows = input.length, cols = input[0].length;
        int[][] grid = new int[rows][cols];
        for (int r = 0; r < rows; r++) grid[r] = input[r].clone();

        int minutes = 0;
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        while (true) {
            boolean freshExists = false;
            for (int[] row : grid) for (int cell : row) if (cell == 1) freshExists = true;
            if (!freshExists) return minutes;

            List<int[]> toRot = new ArrayList<>();
            for (int r = 0; r < rows; r++) {
                for (int c = 0; c < cols; c++) {
                    if (grid[r][c] == 2) {
                        for (int[] d : dirs) {
                            int nr = r + d[0], nc = c + d[1];
                            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1) {
                                toRot.add(new int[]{nr, nc});
                            }
                        }
                    }
                }
            }
            if (toRot.isEmpty()) return -1;
            for (int[] cell : toRot) grid[cell[0]][cell[1]] = 2;
            minutes++;
        }
    }
}

TIME O((ROWS·COLS)²) WORST CASESPACE O(ROWS·COLS)JAVA · TRAINING PACE · 32 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED