Rotten Oranges | Practice Medium 0 attempts
GeeksforGeeks ↗

Rotten Oranges | Practice

Medium Stack&Queue GeeksforGeeks

You're given a grid where each cell holds 0 (empty), 1 (a fresh orange), or 2 (a rotten orange). Every minute, any rotten orange spreads rot to fresh oranges in the cells directly adjacent to it (up, down, left, right — not diagonally). Determine the minimum number of minutes needed until no fresh orange is left on the grid; if that's impossible, return -1.

Input Format
Implement orangesRotting(grid). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

Input
grid = [[2,1,1],[1,1,0],[0,1,1]]
Output
4

Example 2

Input
grid = [[1]]
Output
-1
Constraints
  • 1 <= m, n <= 500
  • 0 <= grid[i][j] <= 2
Test Cases (2)
Case 1
Args: [[[2,1,1],[1,1,0],[0,1,1]]] Expected: 4
Case 2
Args: [[[1]]] Expected: -1
Topics
Stack&Queue

Multi-source BFS

javascript
function orangesRotting(grid) {
  const m = grid.length, n = grid[0].length, q = [];
  let fresh = 0;
  for (let i=0;i<m;i++) for (let j=0;j<n;j++) {
    if (grid[i][j]===2) q.push([i,j]);
    if (grid[i][j]===1) fresh++;
  }
  if (!fresh) return 0;
  const dirs = [[0,1],[0,-1],[1,0],[-1,0]];
  let time = 0;
  let head = 0;
  while (head < q.length && fresh) {
    time++;
    const size = q.length - head;
    for (let k=0;k<size;k++) {
      const [r,c] = q[head++];
      for (const [dr,dc] of dirs) {
        const nr=r+dr, nc=c+dc;
        if (nr>=0&&nr<m&&nc>=0&&nc<n&&grid[nr][nc]===1) {
          grid[nr][nc]=2; fresh--; q.push([nr,nc]);
        }
      }
    }
  }
  return fresh ? -1 : time;
}

Time: O(mn) | Space: O(mn)

Saved in this browser only. Private to you.

JavaScript