Rotten oranges (minimum time to rot all)
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
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;}