Problem
Given an m x n grid where each cell contains one of three values,0 represents an empty cell, 1 represents a fresh orange, and 2 represents a rotten orange.
Every minute, a rotten orange causes any fresh orange directly adjacent to it in the up, down, left, or right direction to become rotten.
Return the minimum number of minutes required for all oranges to become rotten. If some fresh oranges can never become rotten, return
-1.
Example(s)
Consider the following examples to understand the expected input and output.Example 1
Input
grid =
[[2,1,1],
[1,1,0],
[0,1,1]]Output
4Example 2
Input
grid =
[[2,1,1],
[0,1,1],
[1,0,1]]Output
-1Solution
This solution uses the Breadth-First Search (BFS) pattern. Since multiple oranges can already be rotten at the same time, we add all rotten oranges to the queue initially and process them level by level.Each level of BFS represents one minute. During each level, every currently rotten orange spreads to its adjacent fresh oranges. We also maintain a count of fresh oranges. Whenever a fresh orange becomes rotten, we decrease this count.
At the end, if the number of fresh oranges is
0, all oranges have successfully become rotten. Otherwise, some oranges were unreachable, so we return -1.
class Solution {
public int orangesRotting(int[][] grid) {
int rows = grid.length;
int columns = grid[0].length;
Queue<int[]> queue = new LinkedList<>();
int fresh = 0;
// Add all initially rotten oranges to the queue.
for (int i = 0; i < rows; i++) {
for (int j = 0; j < columns; j++) {
if (grid[i][j] == 2) {
queue.offer(new int[]{i, j});
} else if (grid[i][j] == 1) {
fresh++;
}
}
}
int minutes = 0;
int[][] directions = {
{-1, 0},
{1, 0},
{0, -1},
{0, 1}
};
// Process the grid level by level.
while (!queue.isEmpty() && fresh > 0) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int[] current = queue.poll();
int row = current[0];
int column = current[1];
// Spread to all four adjacent cells.
for (int[] direction : directions) {
int nextRow = row + direction[0];
int nextColumn = column + direction[1];
if (nextRow >= 0 && nextRow < rows
&& nextColumn >= 0 && nextColumn < columns
&& grid[nextRow][nextColumn] == 1) {
// Make the fresh orange rotten.
grid[nextRow][nextColumn] = 2;
fresh--;
queue.offer(new int[]{nextRow, nextColumn});
}
}
}
// One minute has passed after processing one level.
minutes++;
}
return fresh == 0 ? minutes : -1;
}
}Complexity
Each cell is processed at most once, so the time complexity isO(m × n), where m and n are the number of rows and columns.
The queue can contain up to
O(m × n) cells, so the extra space complexity is O(m × n).