Prison Cells After N Days
Description
You are given an m × n grid where each cell contains one of three values:
- 0 — an empty cell with no orange
- 1 — a fresh orange
- 2 — a rotten orange
Every minute, any fresh orange that is 4-directionally adjacent (up, down, left, right) to a rotten orange becomes rotten.
Return the minimum number of minutes that must pass until no cell contains a fresh orange. If it is impossible for all oranges to become rotten, return -1.
Examples
Example 1
Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4
Explanation: The single rotten orange starts at position (0, 0). At minute 1, it rots cells (0, 1) and (1, 0). At minute 2, those newly rotten oranges spread to (0, 2) and (1, 1). At minute 3, cell (1, 1) rots cell (2, 1). At minute 4, cell (2, 1) rots the last fresh orange at (2, 2). After 4 minutes, all oranges are rotten.
Example 2
Input: grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The fresh orange at position (2, 0) is completely isolated. The empty cells at (1, 0) and (2, 1) block any path of adjacent fresh oranges leading from the rotten orange at (0, 0) to (2, 0). Since rot only spreads through 4-directional adjacency to fresh oranges, cell (2, 0) can never become rotten. We return -1.
Example 3
Input: grid = [[0,2]]
Output: 0
Explanation: There are no fresh oranges anywhere in the grid. The only orange present is already rotten. Since there is nothing to rot, zero minutes are needed.
Constraints
- m == grid.length
- n == grid[i].length
- 1 ≤ m, n ≤ 10
- grid[i][j] is 0, 1, or 2
Editorial
Brute Force
Intuition
Imagine you have a tray of oranges on a table. Some are already spoiled (rotten), and the rot spreads to any fresh orange touching a rotten one — but only after one full minute passes.
The simplest way to simulate this is to repeatedly scan the entire tray. In each scan, every rotten orange tries to infect its four direct neighbors (up, down, left, right). If a neighbor is a fresh orange, it becomes rotten. We keep repeating these scans until a full pass completes with zero new infections — meaning the rot has spread as far as it can.
To prevent freshly-rotted oranges from infecting others during the same minute (they should only start infecting in the next minute), we temporarily mark them with a different value (like 3) and convert them back to 2 after each pass completes.
At the end, if any fresh orange remains in the grid, we know it was unreachable and return -1. Otherwise, the number of passes we performed gives us the minimum time.
Step-by-Step Explanation
Let's trace through with grid = [[2,1,1],[1,1,0],[0,1,1]]:
Step 1: Initialize. The grid has one rotten orange at (0,0) and six fresh oranges. Set time = 0.
Step 2: Pass 1 — scan the entire grid for rotten oranges (value 2). We find (0,0).
Step 3: From (0,0), check its right neighbor (0,1) — it is fresh (value 1). Mark it as 3 (newly rotten). fresh count drops to 5.
Step 4: From (0,0), check its down neighbor (1,0) — it is fresh. Mark it as 3. fresh count drops to 4.
Step 5: Pass 1 scan complete. We made changes, so convert all 3s back to 2s and increment time to 1. Grid is now [[2,2,1],[2,1,0],[0,1,1]].
Step 6: Pass 2. Scan for rotten oranges. Process (0,1): rot (0,2) and (1,1). Mark both as 3. Fresh count drops to 2.
Step 7: Process (1,0): neighbors are (0,0)=rotten, (2,0)=empty, (1,1)=already marked 3. No new infections from (1,0). Pass 2 complete. Convert 3s to 2s, time = 2. Grid: [[2,2,2],[2,2,0],[0,1,1]].
Step 8: Pass 3. Process (1,1): rot (2,1). Fresh count = 1. Process (0,2): no fresh neighbors. Convert, time = 3. Grid: [[2,2,2],[2,2,0],[0,2,1]].
Step 9: Pass 4. Process (2,1): rot (2,2). Fresh count = 0. Convert, time = 4. Grid: [[2,2,2],[2,2,0],[0,2,2]].
Step 10: Pass 5. Scan entire grid — no fresh oranges adjacent to rotten ones. No changes made. Exit loop.
Step 11: Check for remaining fresh oranges: none found. Return time = 4.
Brute Force — Iterative Grid Simulation — Watch how each pass through the grid spreads rot from existing rotten oranges to their fresh neighbors, one layer at a time.
Algorithm
- Repeat the following until no changes occur in a pass:
a. Scan every cell in the grid
b. For each rotten cell (value 2), check its four neighbors
c. If a neighbor is fresh (value 1), mark it with a temporary value 3
d. After the full scan, convert all 3s back to 2s
e. If any changes were made, increment the time counter - After the loop ends, scan the grid one final time
- If any cell still has value 1 (fresh), return -1
- Otherwise, return the time counter
Code
class Solution {
public:
int orangesRotting(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int time = 0;
while (true) {
bool changed = false;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 2) {
for (int d = 0; d < 4; d++) {
int ni = i + dx[d], nj = j + dy[d];
if (ni >= 0 && ni < m && nj >= 0 && nj < n
&& grid[ni][nj] == 1) {
grid[ni][nj] = 3;
changed = true;
}
}
}
}
}
if (!changed) break;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (grid[i][j] == 3) grid[i][j] = 2;
time++;
}
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (grid[i][j] == 1) return -1;
return time;
}
};class Solution:
def orangesRotting(self, grid: list[list[int]]) -> int:
m, n = len(grid), len(grid[0])
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
time = 0
while True:
changed = False
for i in range(m):
for j in range(n):
if grid[i][j] == 2:
for di, dj in directions:
ni, nj = i + di, j + dj
if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == 1:
grid[ni][nj] = 3
changed = True
if not changed:
break
for i in range(m):
for j in range(n):
if grid[i][j] == 3:
grid[i][j] = 2
time += 1
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
return -1
return timeclass Solution {
public int orangesRotting(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[] dx = {0, 0, 1, -1};
int[] dy = {1, -1, 0, 0};
int time = 0;
while (true) {
boolean changed = false;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 2) {
for (int d = 0; d < 4; d++) {
int ni = i + dx[d], nj = j + dy[d];
if (ni >= 0 && ni < m && nj >= 0 && nj < n
&& grid[ni][nj] == 1) {
grid[ni][nj] = 3;
changed = true;
}
}
}
}
}
if (!changed) break;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (grid[i][j] == 3) grid[i][j] = 2;
time++;
}
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (grid[i][j] == 1) return -1;
return time;
}
}Complexity Analysis
Time Complexity: O((m × n)²)
Each pass scans the entire grid, which takes O(m × n) time. In the worst case, the rot can take up to O(m × n) minutes to spread across the entire grid (imagine a single snaking path of oranges — the rot travels one cell per minute). So we perform O(m × n) passes, each costing O(m × n), giving O((m × n)²) total.
Space Complexity: O(1)
We modify the grid in place using a temporary marker value (3) and use only a few scalar variables. No additional data structures are allocated.
Why This Approach Is Not Efficient
The brute force rescans the entire grid on every pass, even though most cells are either already rotten or empty. When we rot an orange at position (0,1) during pass 1, we already know exactly which cell just became rotten — but in pass 2, we scan every cell from scratch to rediscover it.
Consider a 10×10 grid with a single snaking path of fresh oranges. The rot would need ~100 passes to reach the end, and each pass scans all 100 cells. That is 10,000 cell checks total, compared to the ~100 that are actually necessary.
The core waste is redundant scanning. We keep revisiting cells that cannot contribute anything new. The fix is simple: instead of scanning the grid to find newly rotten oranges, remember where they are. If we put every newly rotten orange into a queue the moment we rot it, the next round can process only those oranges — skipping the entire grid scan. This is exactly what Breadth-First Search (BFS) does: it processes nodes level by level, where each level corresponds to one minute of rot spreading.
Optimal Approach - Multi-Source BFS
Intuition
Think of dropping a stone into a pond. Ripples spread outward in concentric circles — each ring is one step further from the origin. BFS works the same way: it explores all cells at distance 1 first, then distance 2, then distance 3, and so on.
Now imagine dropping multiple stones simultaneously. Each stone creates its own ripple, and the ripples spread outward at the same speed. Where two ripples meet, the cell was reached by whichever source was closer. This is multi-source BFS — we start from all rotten oranges at once, and the rot spreads outward in waves.
Here is the key insight: every rotten orange is a source of rot. We add all initially rotten oranges to a queue at time 0. Then we process them level by level — all oranges at time 0 first, then all oranges that became rotten at time 1, then time 2, etc. Each level corresponds to one minute. When the queue empties, the number of levels processed equals the minimum time.
If any fresh orange remains unreachable (not connected via adjacent fresh oranges to any rotten source), we return -1.
Step-by-Step Explanation
Let's trace with grid = [[2,1,1],[1,1,0],[0,1,1]]:
Step 1: Scan the grid. Find one rotten orange at (0,0). Count 6 fresh oranges. Add (0,0) to the BFS queue. Set time = 0.
Step 2: Begin Level 0 — the queue has 1 element. Dequeue (0,0) and check its neighbors.
Step 3: Right neighbor (0,1) is fresh → mark it rotten (value 2), add to queue. fresh_count = 5.
Step 4: Down neighbor (1,0) is fresh → mark it rotten, add to queue. fresh_count = 4. Level 0 processing complete. Since we rotted oranges, increment time to 1.
Step 5: Level 1 — queue has 2 elements: (0,1) and (1,0). Dequeue (0,1), check neighbors.
Step 6: From (0,1): right (0,2) is fresh → rot it, enqueue. fresh_count = 3.
Step 7: From (0,1): down (1,1) is fresh → rot it, enqueue. fresh_count = 2.
Step 8: Dequeue (1,0). Check neighbors: up (0,0) already rotten, down (2,0) is empty, right (1,1) already rotted this level. No new infections from (1,0). Level 1 complete. time = 2.
Step 9: Level 2 — queue has (0,2) and (1,1). Dequeue (0,2). No fresh neighbors (all rotten, empty, or out of bounds).
Step 10: Dequeue (1,1). Down neighbor (2,1) is fresh → rot it, enqueue. fresh_count = 1. Level 2 complete. time = 3.
Step 11: Level 3 — queue has (2,1). Dequeue (2,1). Right neighbor (2,2) is fresh → rot it, enqueue. fresh_count = 0. time = 4.
Step 12: Level 4 — queue has (2,2). Dequeue it. No fresh neighbors. Queue is now empty.
Step 13: fresh_count = 0, so all oranges are rotten. Return time = 4.
Multi-Source BFS — Level-by-Level Rot Spreading — Watch how BFS processes all rotten oranges at the same distance simultaneously, spreading rot in concentric waves from every source at once.
Algorithm
- Scan the grid: add all initially rotten oranges (value 2) to a queue, and count the total number of fresh oranges
- If fresh count is 0, return 0 immediately (nothing to rot)
- While the queue is not empty:
a. Record the current queue size (this is the number of cells at the current BFS level)
b. Process exactly that many cells from the queue
c. For each cell, check its 4 neighbors — if a neighbor is fresh, mark it rotten, decrement fresh count, and add it to the queue
d. If any new oranges were rotted in this level, increment the time counter - If fresh count is 0, return the time counter
- Otherwise, return -1 (some oranges were unreachable)
Code
class Solution {
public:
int orangesRotting(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
queue<pair<int, int>> q;
int fresh = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 2) q.push({i, j});
else if (grid[i][j] == 1) fresh++;
}
}
if (fresh == 0) return 0;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int time = 0;
while (!q.empty()) {
int size = q.size();
bool rotted = false;
for (int k = 0; k < size; k++) {
auto [i, j] = q.front();
q.pop();
for (int d = 0; d < 4; d++) {
int ni = i + dx[d], nj = j + dy[d];
if (ni >= 0 && ni < m && nj >= 0 && nj < n
&& grid[ni][nj] == 1) {
grid[ni][nj] = 2;
q.push({ni, nj});
fresh--;
rotted = true;
}
}
}
if (rotted) time++;
}
return fresh == 0 ? time : -1;
}
};from collections import deque
class Solution:
def orangesRotting(self, grid: list[list[int]]) -> int:
m, n = len(grid), len(grid[0])
queue = deque()
fresh = 0
for i in range(m):
for j in range(n):
if grid[i][j] == 2:
queue.append((i, j))
elif grid[i][j] == 1:
fresh += 1
if fresh == 0:
return 0
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
time = 0
while queue:
size = len(queue)
rotted = False
for _ in range(size):
i, j = queue.popleft()
for di, dj in directions:
ni, nj = i + di, j + dj
if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == 1:
grid[ni][nj] = 2
queue.append((ni, nj))
fresh -= 1
rotted = True
if rotted:
time += 1
return time if fresh == 0 else -1import java.util.LinkedList;
import java.util.Queue;
class Solution {
public int orangesRotting(int[][] grid) {
int m = grid.length, n = grid[0].length;
Queue<int[]> queue = new LinkedList<>();
int fresh = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 2) queue.offer(new int[]{i, j});
else if (grid[i][j] == 1) fresh++;
}
}
if (fresh == 0) return 0;
int[] dx = {0, 0, 1, -1};
int[] dy = {1, -1, 0, 0};
int time = 0;
while (!queue.isEmpty()) {
int size = queue.size();
boolean rotted = false;
for (int k = 0; k < size; k++) {
int[] cell = queue.poll();
for (int d = 0; d < 4; d++) {
int ni = cell[0] + dx[d];
int nj = cell[1] + dy[d];
if (ni >= 0 && ni < m && nj >= 0 && nj < n
&& grid[ni][nj] == 1) {
grid[ni][nj] = 2;
queue.offer(new int[]{ni, nj});
fresh--;
rotted = true;
}
}
}
if (rotted) time++;
}
return fresh == 0 ? time : -1;
}
}Complexity Analysis
Time Complexity: O(m × n)
The initial scan of the grid takes O(m × n). During BFS, each cell is enqueued and dequeued at most once, and for each cell we check 4 neighbors — a constant amount of work. So the BFS phase is also O(m × n). The total time is O(m × n).
Space Complexity: O(m × n)
In the worst case, all cells could be rotten initially (or become rotten quickly), meaning the queue could hold up to O(m × n) elements at once. Additionally, the deadend set (if applicable) uses O(m × n) space. The grid itself is modified in place.