Generated by Codex with GPT-5

Quick facts

• Difficulty: MEDIUM
• Problem: Rotting Oranges
• Main tags: Array, Breadth-First Search, Matrix

Problem gist

The grid has three kinds of cells: empty (0), fresh oranges (1), and rotten oranges (2). Every minute, any fresh orange touching a rotten orange in the four main directions also becomes rotten.

The goal is to return the minimum number of minutes needed until there are no fresh oranges left. If some fresh orange can never be reached because empty cells block every path from the rotten ones, the answer is -1.

How to derive the optimal solution

The most important observation is that rotting happens in waves. All rotten oranges spread at the same time during minute 1, then all newly rotten oranges spread during minute 2, and so on.

That is exactly the shape of a breadth-first search. Instead of starting BFS from one source, start from every rotten orange at once. This is called multi-source BFS.

The interview path is usually:

1. Scan the grid once.
2. Count how many fresh oranges exist.
3. Put every initially rotten orange into a queue.
4. Process the queue level by level, where one full level means one minute has passed.
5. When a fresh neighbor turns rotten, mark it immediately and push it into the queue for the next minute.

This is optimal because each cell is processed at most once, so the total work is linear in the size of the grid.

Why this works

Each queue layer represents all oranges that are rotten at the start of a particular minute. Those oranges can infect their fresh neighbors during that minute, and the newly infected neighbors form the next layer.

Marking an orange as rotten the moment it is enqueued is important. It prevents the same orange from being added multiple times by different neighbors.

When the BFS ends, there are only two possibilities:

• fresh_count == 0, which means every fresh orange was reached in the earliest possible minute.
• fresh_count > 0, which means some fresh orange was isolated behind empty cells, so the correct answer is -1.

The time complexity is O(m * n) and the queue uses O(m * n) space in the worst case.

Python solution

from collections import deque
from typing import Deque, Iterator, List, Tuple


Coordinate = Tuple[int, int]


class OrangeGridRotter:
    """Compute the minimum time needed to rot every reachable fresh orange."""

    _DIRECTIONS: Tuple[Coordinate, ...] = (
        (1, 0),
        (-1, 0),
        (0, 1),
        (0, -1),
    )

    def min_minutes_to_rot_everything(self, grid: List[List[int]]) -> int:
        if not grid or not grid[0]:
            return 0

        rotten_positions, fresh_orange_count = self._collect_initial_state(grid)
        if fresh_orange_count == 0:
            return 0

        minutes_elapsed = 0

        while rotten_positions and fresh_orange_count > 0:
            minutes_elapsed += 1

            # Every item currently in the queue belongs to the same minute.
            for _ in range(len(rotten_positions)):
                row_index, column_index = rotten_positions.popleft()

                for neighbor_row, neighbor_column in self._fresh_neighbors(
                    grid,
                    row_index,
                    column_index,
                ):
                    grid[neighbor_row][neighbor_column] = 2
                    fresh_orange_count -= 1
                    rotten_positions.append((neighbor_row, neighbor_column))

        return minutes_elapsed if fresh_orange_count == 0 else -1

    def _collect_initial_state(
        self,
        grid: List[List[int]],
    ) -> Tuple[Deque[Coordinate], int]:
        rotten_positions: Deque[Coordinate] = deque()
        fresh_orange_count = 0

        for row_index, row in enumerate(grid):
            for column_index, cell_value in enumerate(row):
                if cell_value == 2:
                    rotten_positions.append((row_index, column_index))
                elif cell_value == 1:
                    fresh_orange_count += 1

        return rotten_positions, fresh_orange_count

    def _fresh_neighbors(
        self,
        grid: List[List[int]],
        row_index: int,
        column_index: int,
    ) -> Iterator[Coordinate]:
        for row_delta, column_delta in self._DIRECTIONS:
            next_row = row_index + row_delta
            next_column = column_index + column_delta

            if self._is_inside_grid(grid, next_row, next_column) and (
                grid[next_row][next_column] == 1
            ):
                yield next_row, next_column

    def _is_inside_grid(
        self,
        grid: List[List[int]],
        row_index: int,
        column_index: int,
    ) -> bool:
        return 0 <= row_index < len(grid) and 0 <= column_index < len(grid[0])


class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        rotter = OrangeGridRotter()
        return rotter.min_minutes_to_rot_everything(grid)

Interview follow-ups

What changes if diagonal neighbors can also rot?

The same multi-source BFS idea still works. The only change is the neighbor list: instead of four directions, use eight directions. BFS is still correct because each edge still represents one minute of travel, so exploring layer by layer still gives the earliest infection time for every orange.

The complexity stays O(m * n) because each cell is still processed at most once. The constant factor is a little larger because each cell has more neighbors to inspect.

What if the interviewer says the input grid must not be mutated?

The cleanest response is to keep the BFS logic the same but copy the grid first, or store infection state in a separate visited structure. The reason this works is that the algorithm only needs two pieces of evolving state: which cells have already turned rotten, and which cells should spread rot in the next minute.

The tradeoff is memory. Mutating the input lets the grid itself serve as visited state. Avoiding mutation usually adds O(m * n) extra space for a copied grid or a separate state matrix.

What if each edge had a different rotting time instead of always taking one minute?

Plain BFS would no longer be the right tool, because BFS assumes every move has the same cost. Once different transitions can take different amounts of time, the correct model becomes shortest paths on a weighted graph.

In that version, start from all initially rotten oranges but run Dijkstra’s algorithm instead of BFS. Dijkstra works because it always expands the next cell with the smallest known infection time. The complexity becomes O(m * n log(m * n)) because of the priority queue.

What if the interviewer wants the actual oranges that rot at each minute?

This falls out naturally from the level-order BFS. During each minute, collect the fresh oranges that were newly infected while processing the current queue layer, then append that list to an output structure.

That works because the queue layer already groups infections by minute. The asymptotic complexity does not change beyond the size of the extra output, since the core BFS traversal is the same.

Takeaway

This is a classic multi-source BFS problem. The right mental shift is to treat every initially rotten orange as a starting point and each BFS layer as one minute of spread. Once that clicks, the implementation becomes straightforward and the impossible case is easy to detect.