321. Rotting Oranges

Start BFS from all initially rotten oranges simultaneously. Each BFS level represents one minute of spreading.

Approach

1. Find all initially rotten oranges and count fresh ones.
2. BFS from all rotten oranges at once.
3. Each level = 1 minute. When a fresh orange is reached, it becomes rotten.
4. If fresh count reaches 0, return minutes. Otherwise -1.

Complexity

• Time: O(m*n)
• Space: O(m*n)

import java.util.*;

class Solution {
    public int orangesRotting(int[][] grid) {
        int rows = grid.length, cols = grid[0].length;
        Queue<int[]> queue = new LinkedList<>();
        int fresh = 0;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == 2) queue.offer(new int[]{r, c});
                else if (grid[r][c] == 1) fresh++;
            }
        }
        if (fresh == 0) return 0;
        int minutes = 0;
        int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] cell = queue.poll();
                for (int[] d : dirs) {
                    int nr = cell[0] + d[0], nc = cell[1] + d[1];
                    if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1) {
                        grid[nr][nc] = 2;
                        fresh--;
                        queue.offer(new int[]{nr, nc});
                    }
                }
            }
            if (!queue.isEmpty()) minutes++;
        }
        return fresh == 0 ? minutes : -1;
    }
}