Rotten oranges (minimum time to rot all)

Medium

Problem

In the grid, 0 is empty, 1 is a fresh orange and 2 is a rotten orange. Every minute, a fresh orange next to a rotten one (up, down, left or right) becomes rotten. Return the minimum number of minutes until no fresh orange remains, or −1 if that never happens.

Example 1

Input:  [[2,1,1], [1,1,0], [0,1,1]]
Output: 4

Example 2

Input:  [[2,1,1], [0,1,1], [1,0,1]]
Output: -1

The bottom-left orange can never be reached.

Also asked as: Minimum time required to rot all oranges

Test cases

Case 1

Input:    [[2,1,1],[1,1,0],[0,1,1]]
Expected: 4

Case 2

Input:    [[2,1,1],[0,1,1],[1,0,1]]
Expected: -1

Case 3

Input:    [[0,2]]
Expected: 0

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Multi-source BFS

Time O(R·C)Space O(R·C)

Seed the queue with every rotten orange at time 0; BFS outward, rotting fresh neighbours. The answer is the last time stamp; return −1 if any fresh orange remains.

function orangesRotting(grid) {
const R = grid.length, C = grid[0].length;
let fresh = 0;
const q = [];
for (let r = 0; r < R; r++)
for (let c = 0; c < C; c++) {
if (grid[r][c] === 2) q.push([r, c, 0]);
else if (grid[r][c] === 1) fresh++;
}
let time = 0;
const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
while (q.length) {
const [r, c, t] = q.shift();
time = Math.max(time, t);
for (const [dr, dc] of dirs) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nc >= 0 && nr < R && nc < C && grid[nr][nc] === 1) {
grid[nr][nc] = 2; fresh--; q.push([nr, nc, t + 1]);
}
}
}
return fresh === 0 ? time : -1;
}