Rotting Oranges — Multi-Source BFS

Problem

Grid with 0 (empty), 1 (fresh orange), 2 (rotten). Each minute, rotten oranges infect adjacent fresh ones. Return min minutes until no fresh remain, or -1 if impossible.

Approach — Multi-Source BFS

Push all rotten oranges into queue at time 0. BFS spreads rot layer by layer. Count fresh oranges; if any remain after BFS, return -1.

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

Solutions

C++

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int R=grid.size(),C=grid[0].size(),fresh=0,time=0;
        queue<pair<int,int>> q;
        for(int r=0;r<R;r++) for(int c=0;c<C;c++) {
            if(grid[r][c]==2) q.push({r,c});
            else if(grid[r][c]==1) fresh++;
        }
        int dr[]={0,0,1,-1},dc[]={1,-1,0,0};
        while(!q.empty()&&fresh>0) {
            int sz=q.size(); time++;
            while(sz--) {
                auto[r,c]=q.front();q.pop();
                for(int i=0;i<4;i++){
                    int nr=r+dr[i],nc=c+dc[i];
                    if(nr>=0&&nr<R&&nc>=0&&nc<C&&grid[nr][nc]==1){
                        grid[nr][nc]=2; fresh--; q.push({nr,nc});
                    }
                }
            }
        }
        return fresh==0?time:-1;
    }
};

Java

class Solution {
    public int orangesRotting(int[][] grid) {
        int R=grid.length,C=grid[0].length,fresh=0,time=0;
        Queue<int[]> q=new LinkedList<>();
        for(int r=0;r<R;r++) for(int c=0;c<C;c++) {
            if(grid[r][c]==2) q.add(new int[]{r,c});
            else if(grid[r][c]==1) fresh++;
        }
        int[][] dirs={{0,1},{0,-1},{1,0},{-1,0}};
        while(!q.isEmpty()&&fresh>0) {
            time++; int sz=q.size();
            while(sz-->0) {
                int[] cur=q.poll();
                for(int[] d:dirs){
                    int nr=cur[0]+d[0],nc=cur[1]+d[1];
                    if(nr>=0&&nr<R&&nc>=0&&nc<C&&grid[nr][nc]==1){
                        grid[nr][nc]=2; fresh--; q.add(new int[]{nr,nc});
                    }
                }
            }
        }
        return fresh==0?time:-1;
    }
}

Python

from collections import deque
class Solution:
    def orangesRotting(self, grid: list[list[int]]) -> int:
        R,C=len(grid),len(grid[0])
        q=deque(); fresh=0
        for r in range(R):
            for c in range(C):
                if grid[r][c]==2: q.append((r,c))
                elif grid[r][c]==1: fresh+=1
        time=0
        while q and fresh:
            time+=1
            for _ in range(len(q)):
                r,c=q.popleft()
                for dr,dc in[(1,0),(-1,0),(0,1),(0,-1)]:
                    nr,nc=r+dr,c+dc
                    if 0<=nr<R and 0<=nc<C and grid[nr][nc]==1:
                        grid[nr][nc]=2; fresh-=1; q.append((nr,nc))
        return time if fresh==0 else -1

Complexity

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