Time for Rot to Spread Through a Grid

medium graph bfs grid multi-source

Problem

A grid contains empty (0), fresh (1), and rotten (2) cells. Each minute, every fresh cell with a rotten neighbour becomes rotten. Return the minutes until none are fresh, or -1 if some never rot. Multi-source BFS from every initially rotten cell.

Inputgrid (rows by ';') = "2,1,1; 1,1,0; 0,1,1"

Output4

Spread expands from top-left rotten cell layer by layer.

grid (rows by ';', cells 0/1/2)

from collections import deque
def rotting(grid):
    m, n = len(grid), len(grid[0])
    q = deque(); fresh = 0
    for r in range(m):
        for c in range(n):
            if grid[r][c] == 2: q.append((r, c))
            elif grid[r][c] == 1: fresh += 1
    mins = 0
    dirs = [(1,0),(-1,0),(0,1),(0,-1)]
    while q and fresh:
        nxt = deque()
        for r, c in q:
            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                if 0<=nr<m and 0<=nc<n and grid[nr][nc] == 1:
                    grid[nr][nc] = 2; fresh -= 1; nxt.append((nr, nc))
        q = nxt; mins += 1
    return mins if fresh == 0 else -1

function rotting(grid) {
  const m = grid.length, n = grid[0].length;
  let q = [], fresh = 0;
  for (let r = 0; r < m; r++) for (let c = 0; c < n; c++) {
    if (grid[r][c] === 2) q.push([r, c]);
    else if (grid[r][c] === 1) fresh++;
  }
  let mins = 0;
  const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
  while (q.length && fresh > 0) {
    const next = [];
    for (const [r, c] of q) for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr<0||nc<0||nr>=m||nc>=n||grid[nr][nc] !== 1) continue;
      grid[nr][nc] = 2; fresh--; next.push([nr, nc]);
    }
    q = next; mins++;
  }
  return fresh === 0 ? mins : -1;
}

class Solution {
    public int rotting(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        Deque<int[]> q = new ArrayDeque<>();
        int fresh = 0;
        for (int r = 0; r < m; r++) for (int c = 0; c < n; c++) {
            if (grid[r][c] == 2) q.offer(new int[]{ r, c });
            else if (grid[r][c] == 1) fresh++;
        }
        int mins = 0;
        int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
        while (!q.isEmpty() && fresh > 0) {
            Deque<int[]> next = new ArrayDeque<>();
            for (int[] f : q) for (int[] dd : dirs) {
                int nr = f[0] + dd[0], nc = f[1] + dd[1];
                if (nr<0||nc<0||nr>=m||nc>=n||grid[nr][nc] != 1) continue;
                grid[nr][nc] = 2; fresh--; next.offer(new int[]{ nr, nc });
            }
            q = next; mins++;
        }
        return fresh == 0 ? mins : -1;
    }
}

int rotting(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    queue<pair<int,int>> q;
    int fresh = 0;
    for (int r = 0; r < m; r++) for (int c = 0; c < n; c++) {
        if (grid[r][c] == 2) q.push({r, c});
        else if (grid[r][c] == 1) fresh++;
    }
    int mins = 0;
    int dirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
    while (!q.empty() && fresh > 0) {
        queue<pair<int,int>> next;
        while (!q.empty()) {
            auto [r, c] = q.front(); q.pop();
            for (auto& dd : dirs) {
                int nr = r + dd[0], nc = c + dd[1];
                if (nr<0||nc<0||nr>=m||nc>=n||grid[nr][nc] != 1) continue;
                grid[nr][nc] = 2; fresh--; next.push({nr, nc});
            }
        }
        q = next; mins++;
    }
    return fresh == 0 ? mins : -1;
}

Time: O(m·n) Space: O(m·n)