# LeetCode 994: Rotting Oranges — Step-by-Step Visual Trace

**Medium** — BFS | Queue | Matrix | Graph

## The Problem

Given a 2D grid representing oranges where 0=empty, 1=fresh orange, 2=rotten orange, determine the minimum time in minutes for all fresh oranges to rot, or return -1 if impossible.

## Approach

Use BFS (Breadth-First Search) to simulate the rotting process minute by minute. Start with all initially rotten oranges in a queue, then process each level to rot adjacent fresh oranges until no more oranges can rot.

**Time:** O(m × n) · **Space:** O(m × n)

## Code

```python
class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        if not grid:
            return -1

        rows, cols = len(grid), len(grid[0])
        fresh_count = 0  # Count of fresh oranges
        rotten = deque()  # Queue to store coordinates of rotten oranges
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]  # Possible adjacent cells

        # Initialize the queue with coordinates of rotten oranges
        for row in range(rows):
            for col in range(cols):
                if grid[row][col] == 2:
                    rotten.append((row, col))
                elif grid[row][col] == 1:
                    fresh_count += 1

        minutes = 0  # Timer

        while rotten:
            level_size = len(rotten)

            for _ in range(level_size):
                row, col = rotten.popleft()

                for dr, dc in directions:
                    new_row, new_col = row + dr, col + dc

                    # Check if the new cell is within bounds and has a fresh orange
                    if (
                        0 <= new_row < rows
                        and 0 <= new_col < cols
                        and grid[new_row][new_col] == 1
                    ):
                        grid[new_row][new_col] = 2  # Infect the fresh orange
                        fresh_count -= 1
                        rotten.append((new_row, new_col))

            if rotten:
                minutes += 1

        # If there are fresh oranges left, return -1; otherwise, return the elapsed minutes
        return minutes if fresh_count == 0 else -1
```

## Watch It Run

> **[Open interactive visualization](https://tracelit.dev/app?trace=0994_rotting-oranges)**

> **Try it yourself:** Open [TraceLit](https://tracelit.dev/app?trace=0994_rotting-oranges) and step through every line.

---

*Built with [TraceLit](https://tracelit.dev) — the visual algorithm tracer for LeetCode practice.*