Problem Statement:
You are given an m x n grid where each cell can have one of three values:
0representing an empty cell,1representing a fresh orange, or2representing a rotten orange.
Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.
Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.
Examples:
Example 1:
Input:
grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.
Example 2:
Input:
grid = [[0,2]]
Output: 0
Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.
For more details, refer to LeetCode problem 994.
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 10grid[i][j] is 0, 1, or 2.
Approach:
- Identify rotten oranges (2) and push their positions + time
([i, j, 0])into a queue. - Use BFS to spread rot in 4 directions (up, down, left, right).
- For each direction: If neighbor is a fresh orange (1), rot it (→ 2) and push it into the queue with time +1.
- Track time with
maxMinutes. - After BFS, if any fresh orange
(1)left, return-1. - Else, return
maxMinutes.
Visualisation:
Time Complexity:
Time Complexity = O(m x n)
Space Complexity:
Space Complexity = O(m x n)
Dry Run
Input:
grid = [ [2,1,1], [1,1,0], [0,1,1] ]
State Transitions:
Initialize: m = 3, n = 3 queue = [] → Scanning grid: Found rotten orange at (0,0) → queue = [[0,0,0]] Start BFS: queue = [[0,0,0]] maxMinutes = 0 Pop [0,0,0] → (0,1) is fresh → rot it → queue.push([0,1,1]) → (1,0) is fresh → rot it → queue.push([1,0,1]) maxMinutes = max(0, 0) = 0 Pop [0,1,1] → (0,2) is fresh → rot it → queue.push([0,2,2]) → (1,1) is fresh → rot it → queue.push([1,1,2]) maxMinutes = max(1, 0) = 1 Pop [1,0,1] → (2,0) is 0 (empty) → skip maxMinutes = max(1, 1) = 1 Pop [0,2,2] → (1,2) is 0 → skip maxMinutes = max(2, 1) = 2 Pop [1,1,2] → (2,1) is fresh → rot it → queue.push([2,1,3]) maxMinutes = max(2, 2) = 2 Pop [2,1,3] → (2,2) is fresh → rot it → queue.push([2,2,4]) maxMinutes = max(3, 2) = 3 Pop [2,2,4] → all neighbors are either 0 or already rotten maxMinutes = max(4, 3) = 4 → BFS finished, check for any remaining fresh oranges: → All are rotten or empty
Final Output: 4
Final State: grid = [ [2,2,2], [2,2,0], [0,2,2] ]
var orangesRotting = function(grid) {
let m = grid.length;
let n = grid[0].length;
let queue = [];
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 2) {
queue.push([i, j, 0]);
}
}
}
let maxMinutes = 0;
while (queue.length) {
let [x, y, level] = queue.shift();
if (x > 0 && grid[x - 1][y] === 1) {
grid[x - 1][y] = 2;
queue.push([x - 1, y, level + 1]);
}
if (x < m - 1 && grid[x + 1][y] === 1) {
grid[x + 1][y] = 2;
queue.push([x + 1, y, level + 1]);
}
if (y < n - 1 && grid[x][y + 1] === 1) {
grid[x][y + 1] = 2;
queue.push([x, y + 1, level + 1]);
}
if (y > 0 && grid[x][y - 1] === 1) {
grid[x][y - 1] = 2;
queue.push([x, y - 1, level + 1]);
}
maxMinutes = Math.max(level, maxMinutes);
}
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 1) {
return -1;
}
}
}
return maxMinutes;
};
from collections import deque
def orangesRotting(grid):
m = len(grid)
n = len(grid[0])
queue = deque()
for i in range(m):
for j in range(n):
if grid[i][j] == 2:
queue.append((i, j, 0))
maxMinutes = 0
while queue:
x, y, level = queue.popleft()
if x > 0 and grid[x - 1][y] == 1:
grid[x - 1][y] = 2
queue.append((x - 1, y, level + 1))
if x < m - 1 and grid[x + 1][y] == 1:
grid[x + 1][y] = 2
queue.append((x + 1, y, level + 1))
if y < n - 1 and grid[x][y + 1] == 1:
grid[x][y + 1] = 2
queue.append((x, y + 1, level + 1))
if y > 0 and grid[x][y - 1] == 1:
grid[x][y - 1] = 2
queue.append((x, y - 1, level + 1))
maxMinutes = max(maxMinutes, level)
for row in grid:
if 1 in row:
return -1
return maxMinutes
public int orangesRotting(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
Queue queue = new LinkedList<>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 2) {
queue.add(new int[]{i, j, 0});
}
}
}
int maxMinutes = 0;
while (!queue.isEmpty()) {
int[] curr = queue.poll();
int x = curr[0], y = curr[1], level = curr[2];
if (x > 0 && grid[x - 1][y] == 1) {
grid[x - 1][y] = 2;
queue.add(new int[]{x - 1, y, level + 1});
}
if (x < m - 1 && grid[x + 1][y] == 1) {
grid[x + 1][y] = 2;
queue.add(new int[]{x + 1, y, level + 1});
}
if (y < n - 1 && grid[x][y + 1] == 1) {
grid[x][y + 1] = 2;
queue.add(new int[]{x, y + 1, level + 1});
}
if (y > 0 && grid[x][y - 1] == 1) {
grid[x][y - 1] = 2;
queue.add(new int[]{x, y - 1, level + 1});
}
maxMinutes = Math.max(level, maxMinutes);
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) return -1;
}
}
return maxMinutes;
}
int orangesRotting(vector>& grid) {
int m = grid.size();
int n = grid[0].size();
queue> q;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 2) {
q.push({i, j, 0});
}
}
}
int maxMinutes = 0;
while (!q.empty()) {
auto [x, y, level] = q.front();
q.pop();
if (x > 0 && grid[x - 1][y] == 1) {
grid[x - 1][y] = 2;
q.push({x - 1, y, level + 1});
}
if (x < m - 1 && grid[x + 1][y] == 1) {
grid[x + 1][y] = 2;
q.push({x + 1, y, level + 1});
}
if (y < n - 1 && grid[x][y + 1] == 1) {
grid[x][y + 1] = 2;
q.push({x, y + 1, level + 1});
}
if (y > 0 && grid[x][y - 1] == 1) {
grid[x][y - 1] = 2;
q.push({x, y - 1, level + 1});
}
maxMinutes = max(level, maxMinutes);
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 1) return -1;
}
}
return maxMinutes;
}
int orangesRotting(int** grid, int gridSize, int* gridColSize) {
int m = gridSize;
int n = gridColSize[0];
int queue[m * n][3];
int front = 0, rear = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 2) {
queue[rear][0] = i;
queue[rear][1] = j;
queue[rear][2] = 0;
rear++;
}
}
}
int maxMinutes = 0;
while (front < rear) {
int x = queue[front][0];
int y = queue[front][1];
int level = queue[front][2];
front++;
if (x > 0 && grid[x - 1][y] == 1) {
grid[x - 1][y] = 2;
queue[rear][0] = x - 1;
queue[rear][1] = y;
queue[rear][2] = level + 1;
rear++;
}
if (x < m - 1 && grid[x + 1][y] == 1) {
grid[x + 1][y] = 2;
queue[rear][0] = x + 1;
queue[rear][1] = y;
queue[rear][2] = level + 1;
rear++;
}
if (y < n - 1 && grid[x][y + 1] == 1) {
grid[x][y + 1] = 2;
queue[rear][0] = x;
queue[rear][1] = y + 1;
queue[rear][2] = level + 1;
rear++;
}
if (y > 0 && grid[x][y - 1] == 1) {
grid[x][y - 1] = 2;
queue[rear][0] = x;
queue[rear][1] = y - 1;
queue[rear][2] = level + 1;
rear++;
}
if (level > maxMinutes) maxMinutes = level;
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 1) return -1;
}
}
return maxMinutes;
}
public int OrangesRotting(int[][] grid) {
int m = grid.Length;
int n = grid[0].Length;
Queue<(int, int, int)> queue = new();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 2) {
queue.Enqueue((i, j, 0));
}
}
}
int maxMinutes = 0;
while (queue.Count > 0) {
var (x, y, level) = queue.Dequeue();
if (x > 0 && grid[x - 1][y] == 1) {
grid[x - 1][y] = 2;
queue.Enqueue((x - 1, y, level + 1));
}
if (x < m - 1 && grid[x + 1][y] == 1) {
grid[x + 1][y] = 2;
queue.Enqueue((x + 1, y, level + 1));
}
if (y < n - 1 && grid[x][y + 1] == 1) {
grid[x][y + 1] = 2;
queue.Enqueue((x, y + 1, level + 1));
}
if (y > 0 && grid[x][y - 1] == 1) {
grid[x][y - 1] = 2;
queue.Enqueue((x, y - 1, level + 1));
}
maxMinutes = Math.Max(level, maxMinutes);
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) return -1;
}
}
return maxMinutes;
}
