Rotting Oranges

1. Step 1: Initialize Solution.orangesRotting

   Replace the empty starter with the first real state owned by Solution.orangesRotting. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.

2. Step 2: Assemble the primary transition

   Extend the initialized state with the next contiguous part of the popular solution. The transition explains how one input element or operation changes the state; boundaries are easier to reason about after this invariant is visible.

3. Step 3: Pass the Four Minutes case

   Complete the readable core algorithm for one representative Interview case. An explicit unresolved count makes the termination invariant visible before the final multiple-source repair.

4. Step 4: Track every unresolved fresh orange

   Replace the final whole-grid scan with an explicit fresh-orange frontier count. An explicit unresolved count makes the termination invariant visible before the final multiple-source repair.

5. Step 5: Harden the Multiple Sources boundary

   Repair the reviewed boundary and pass the complete submission contract. All initially rotten sources and each subsequent frontier expand simultaneously, so BFS levels match minutes. Every newly rotten orange is reached at its earliest time; leftover fresh count exactly identifies impossibility.

• Do not add a minute when the initial grid has no fresh oranges.
• trees and graphs

• LeetCode 994 — Rotting Oranges

• Expand a Multi-Source Frontier(opens in a new tab)

  Expand a Multi-Source Frontier isolates every queued cell already has its minimum distance, because frontiers leave the queue in nondecreasing distance order. That focused state discipline is required when implementing rotting oranges as a complete Interview Problem.

Enqueue all rotten oranges and count fresh ones. While fresh remains and queue is nonempty, process one queue level, rot fresh neighbors, then increment minutes.

Why it works: All initially rotten sources and each subsequent frontier expand simultaneously, so BFS levels match minutes. Every newly rotten orange is reached at its earliest time; leftover fresh count exactly identifies impossibility.

class Solution:
    def orangesRotting(self, grid):
        """
        Checkpoint 1: initialize the state owned by this Interview contract.
        Checkpoint 2: assemble the primary transition without hiding the boundary.
        Checkpoint 3: make the complete frontier invariant explicit before the final boundary.
        """
        from collections import deque
        rows, columns = len(grid), len(grid[0])
        sources = []
        fresh = 0
        for row in range(rows):
            for column in range(columns):
                if grid[row][column] == 2:
                    sources.append((row, column))
                elif grid[row][column] == 1:
                    fresh += 1
        queue = deque(sources)
        minutes = 0
        while fresh and queue:
            for _ in range(len(queue)):
                row, column = queue.popleft()
                neighbors = (
                    (row + 1, column), (row - 1, column),
                    (row, column + 1), (row, column - 1),
                )
                for next_row, next_column in neighbors:
                    inside = 0 <= next_row < rows and 0 <= next_column < columns
                    if inside and grid[next_row][next_column] == 1:
                        grid[next_row][next_column] = 2
                        fresh -= 1
                        queue.append((next_row, next_column))
            minutes += 1
        return minutes if fresh == 0 else -1

• Walls and Gates(opens in a new tab)