Rotting Oranges

medium graph bfs grid multi-source

Problem

You are given an m x n grid where each cell can have one of three values: 0 representing an empty cell, 1 representing a fresh orange, or 2 representing a rotten orange. Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten. Return the minimum number of minutes that must elapse until no cell has a fresh orange.

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 oranges_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 orangesRotting(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 orangesRotting(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 orangesRotting(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;
}

Explanation

Rot spreads outward from every rotten orange at the same time, one ring per minute. That "all at once, layer by layer" pattern is exactly what multi-source BFS does, so we treat all the initially rotten cells as starting points and expand together.

First we scan the grid: every cell with value 2 goes into the queue q as a starting source, and we count how many fresh cells (1) exist in fresh.

Then we process the queue one whole layer at a time. For each rotten cell in the current layer we look at its four neighbors; any fresh neighbor turns rotten (set to 2), we decrement fresh, and it joins the next layer. After finishing a layer we add 1 to mins.

Example: 2,1,1 / 1,1,0 / 0,1,1. The single rotten cell at top-left infects its neighbors ring by ring; after 4 minutes the last fresh orange rots, so the answer is 4.

At the end, if fresh is 0 every orange rotted and we return mins; if some fresh orange was unreachable, fresh stays positive and we return -1.

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