# Rotting Oranges

- **Canonical ID**: `rotting-oranges`
- **Canonical URL**: https://dsacheatsheet.com/problems/rotting-oranges
- **Difficulty**: medium
- **Patterns**: Graphs
- **Version**: 1.0.0 (verified 2026-11-11T21:20:00Z)
- **Original Problem**: https://leetcode.com/problems/rotting-oranges/

## 1. Core Invariant / The Trick

Seed one **multi-source BFS** queue simultaneously with ALL initially rotten cells (`2`) while counting `fresh` cells (`1`). Process level-by-level while `q and fresh > 0`, decrementing `fresh` on each rot.

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(M * N)`
- **Space Complexity**: `O(M * N)`
- **Proof**: Every fresh cell enters the BFS queue at most once in exact shortest-path wavefront order.

## 3. Minimal Idiomatic Code

### Python
```python
def orangesRotting(grid: list[list[int]]) -> int:
    R, C = len(grid), len(grid[0])
    q = deque()
    fresh = 0
    for r in range(R):
        for c in range(C):
            if grid[r][c] == 2:
                q.append((r, c))
            elif grid[r][c] == 1:
                fresh += 1
    mins = 0
    while q and fresh > 0:
        mins += 1
        for _ in range(len(q)):
            r, c = q.popleft()
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] == 1:
                    grid[nr][nc] = 2
                    fresh -= 1
                    q.append((nr, nc))
    return mins if fresh == 0 else -1
```

### TypeScript
```typescript
export function orangesRotting(grid: number[][]): number {
  const R = grid.length, C = grid[0].length;
  let q: Array<[number, number]> = [];
  let fresh = 0;
  for (let r = 0; r < R; r++) {
    for (let c = 0; c < C; c++) {
      if (grid[r][c] === 2) q.push([r, c]);
      else if (grid[r][c] === 1) fresh++;
    }
  }
  let mins = 0;
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
  while (q.length > 0 && fresh > 0) {
    mins++;
    const nextQ: Array<[number, number]> = [];
    for (const [r, c] of q) {
      for (const [dr, dc] of dirs) {
        const nr = r + dr, nc = c + dc;
        if (nr >= 0 && nr < R && nc >= 0 && nc < C && grid[nr][nc] === 1) {
          grid[nr][nc] = 2;
          fresh--;
          nextQ.push([nr, nc]);
        }
      }
    }
    q = nextQ;
  }
  return fresh === 0 ? mins : -1;
}
```

### C++
```cpp
int orangesRotting(vector<vector<int>>& grid) {
    int R = grid.size(), C = grid[0].size(), fresh = 0, mins = 0;
    queue<pair<int,int>> q;
    for (int r = 0; r < R; ++r)
        for (int c = 0; c < C; ++c)
            if (grid[r][c] == 2) q.push({r, c});
            else if (grid[r][c] == 1) fresh++;
    int dr[4] = {1,-1,0,0}, dc[4] = {0,0,1,-1};
    while (!q.empty() && fresh > 0) {
        mins++;
        for (int sz = q.size(); sz--; ) {
            auto [r, c] = q.front(); q.pop();
            for (int k = 0; k < 4; ++k) {
                int nr = r + dr[k], nc = c + dc[k];
                if (nr >= 0 && nr < R && nc >= 0 && nc < C && grid[nr][nc] == 1) {
                    grid[nr][nc] = 2; fresh--; q.push({nr, nc});
                }
            }
        }
    }
    return fresh == 0 ? mins : -1;
}
```

### Java
```java
int orangesRotting(int[][] grid) {
    int R = grid.length, C = grid[0].length, fresh = 0, mins = 0;
    Queue<int[]> q = new ArrayDeque<>();
    for (int r = 0; r < R; r++)
        for (int c = 0; c < C; c++)
            if (grid[r][c] == 2) q.offer(new int[]{r, c});
            else if (grid[r][c] == 1) fresh++;
    int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
    while (!q.isEmpty() && fresh > 0) {
        mins++;
        for (int sz = q.size(); sz > 0; sz--) {
            int[] cur = q.poll();
            for (int[] d : dirs) {
                int nr = cur[0] + d[0], nc = cur[1] + d[1];
                if (nr >= 0 && nr < R && nc >= 0 && nc < C && grid[nr][nc] == 1) {
                    grid[nr][nc] = 2; fresh--; q.offer(new int[]{nr, nc});
                }
            }
        }
    }
    return fresh == 0 ? mins : -1;
}
```

### Go
```go
func orangesRotting(grid [][]int) int {
    R, C, fresh, mins := len(grid), len(grid[0]), 0, 0
    var q [][2]int
    for r := 0; r < R; r++ {
        for c := 0; c < C; c++ {
            if grid[r][c] == 2 { q = append(q, [2]int{r, c}) }
            else if grid[r][c] == 1 { fresh++ }
        }
    }
    dirs := [4][2]int{{1,0},{-1,0},{0,1},{0,-1}}
    for len(q) > 0 && fresh > 0 {
        mins++
        var nq [][2]int
        for _, cur := range q {
            for _, d := range dirs {
                nr, nc := cur[0]+d[0], cur[1]+d[1]
                if nr >= 0 && nr < R && nc >= 0 && nc < C && grid[nr][nc] == 1 {
                    grid[nr][nc] = 2; fresh--; nq = append(nq, [2]int{nr, nc})
                }
            }
        }
        q = nq
    }
    if fresh == 0 { return mins }
    return -1
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Incrementing `minutes` even on the final wave when `fresh == 0` overcounts by 1 minute (guard loop with `while q and fresh > 0`).
- Returning `-1` when `fresh == 0` initially.

### Follow-ups
- Walls and Gates is identical multi-source BFS seeded from all gates (`0`).