LeetCode: Rotting Oranges Solution
Simultaneously spread from rotten cellsApproach: BFS
Final
res - 1
is to exclude the last step where there is no fresh cell leftImplementation
1var orangesRotting = function (grid) {2 const [m, n] = [grid.length, grid[0].length]3 const cellOutbound = (row, col) => row < 0 || row >= m || col < 0 || col >= n4 const cellNotFresh = (row, col) => [0, 2].includes(grid[row][col])56 const dirs = [7 [-1, 0],8 [1, 0],9 [0, -1],10 [0, 1],11 ]12 const queue = []13 let res = 014 let countFresh = 01516 for (let row = 0; row < m; row++) {17 for (let col = 0; col < n; col++) {18 if (grid[row][col] === 2) queue.push([row, col])19 if (grid[row][col] === 1) countFresh++20 }21 }2223 if (countFresh === 0) return 02425 while (queue.length > 0) {26 res++27 let currentQueueLength = queue.length28 while (currentQueueLength--) {29 const cell = queue.shift()30 for (const dir of dirs) {31 const [row, col] = [cell[0] + dir[0], cell[1] + dir[1]]32 if (cellOutbound(row, col) || cellNotFresh(row, col)) continue3334 grid[row][col] = 235 countFresh--36 queue.push([row, col])37 }38 }39 }4041 return countFresh === 0 ? res - 1 : -142}
References
Similar problems
Walls and Gates
Detonate the Maximum Bombs
Escape the Spreading Fire
Comments
Loading comments...
Tags
leetcode
array
matrix
bfs
Apply and earn a $2,500 bonus once you're hired on your first job!
Clients from the Fortune 500 to Silicon Valley startups
Choose your own rate, get paid on time
From hourly, part-time, to full-time positions
Flexible remote working environment
A lot of open JavaScript jobs!!
Fact corner: Referred talent are 5x more likely to pass the Toptal screening process than the average applicant.
Still hesitate? Read HoningJS author's guide on dealing with Toptal interview process.