Rotting Oranges
A third multi-source BFS in the same shape as Islands and Treasure, plus a bug worth keeping: 'minutes elapsed' has to increment once per drained level, not once per cell — get that placement wrong and 4 minutes becomes 6.
The problem
Implement `orangesRotting(grid)` where each cell is `0` (empty), `1` (fresh orange), or `2` (rotten orange). Every minute, any fresh orange 4-directionally adjacent to a rotten one becomes rotten. Return the minimum number of minutes until no cell holds a fresh orange, or `-1` if some fresh orange can never be reached.
The approach
Same multi-source BFS shape as `islandsAndTreasure`: every initially rotten cell seeds the queue up front, and the outer/inner `while` pair drains one full level — one minute — at a time. A running `freshFruits` counter (incremented on the initial scan, decremented every time a cell turns rotten) stands in for a distance grid, since the question only wants a count, not per-cell values.
The first draft put `timeTaken++` inside the inner `while (size > 0)` loop, so it counted once per *cell* dequeued instead of once per *level* — five oranges rotting produced five ticks instead of the handful of minutes it actually took. The fix is just moving the increment to after the inner loop closes, so it fires exactly once per BFS level, matching how `distance` already worked in `islandsAndTreasure`.
That alone still overcounts by one: once the last fresh orange rots, the level containing it still finishes and bumps the timer, even though no further minute was needed for anything after it. Guarding the outer loop with `q.length && freshFruits > 0` stops the BFS the instant nothing fresh is left, so the final level's tick is the last one that counted for anything.
The solution
class Solution {
/**
* @param {number[][]} grid
* @return {number}
*/
orangesRotting(grid) {
const visited = new Set()
const q = []
let freshFruits = 0
let timeTaken = 0
// Pushing all the treasure cells as BFS sources
for (let r = 0; r < grid.length; r++) {
for (let c = 0; c < grid[0].length; c++) {
if(grid[r][c] === 1) {
freshFruits++
}
if (grid[r][c] === 2) {
q.push([r, c])
visited.add(`${r},${c}`)
}
}
}
const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
while (q.length && freshFruits > 0) {
let size = q.length
while (size > 0) {
const [cr, cc] = q.shift()
for (let [dr, dc] of directions) {
const [nr, nc] = [cr + dr, cc + dc]
const nColInbound = nc >= 0 && nc < grid[0].length
const nRowInbound = nr >= 0 && nr < grid.length
const inBound = nColInbound && nRowInbound
const neighborPos = `${nr},${nc}`
if (inBound && grid[nr][nc] === 1 && !visited.has(neighborPos)) {
grid[nr][nc] = 2
visited.add(neighborPos)
q.push([nr, nc])
freshFruits--
}
}
size--
}
timeTaken++
}
return freshFruits > 0 ? -1 : timeTaken
}
}Time O(R * C)Space O(R * C)