🎨Now live: Try our Free AI Image Generation Feature

Description
The problem is to determine the minimum amount of time required for all oranges in a grid to rot. The grid contains three types of cells:
0
representing an empty cell,1
representing a fresh orange, and2
representing a rotten orange.
Each minute, any fresh orange that is adjacent (4-directionally) to a rotten orange becomes rotten. The goal is to return the minimum number of minutes required for all fresh oranges to rot. If it's impossible for all the fresh oranges to rot, return -1
.
Intuition
The problem can be solved using a Breadth-First Search (BFS) approach. BFS is suitable here because we need to explore all nodes (fresh oranges) layer by layer from the initially rotten oranges. This ensures that we track the time taken for the rotting process level by level.
Approach
- Initialize a Queue and Count Fresh Oranges: - Traverse the grid to count the number of fresh oranges. - At the same time, add the position of all initially rotten oranges to a queue.
- Breadth-First Search (BFS): - Use the queue to process each rotten orange. - For each rotten orange, rot all adjacent fresh oranges and add them to the queue. - Track the time taken for each layer of BFS.
- Check Remaining Fresh Oranges:
- After the BFS completes, check if there are any fresh oranges left. If so, return
-1
as it's impossible to rot all oranges. Otherwise, return the time taken.
Complexity
Time Complexity:
- The time complexity is
O(m * n)
, wherem
is the number of rows andn
is the number of columns in the grid. This is because each cell is processed at most once.
Space Complexity:
- The space complexity is also
O(m * n)
because in the worst case, all cells could be added to the queue.
Code
C++
class Solution {
public:
int orangesRotting(vector>& grid) {
int time = 0;
queue> q;
int m = grid.size();
int n = grid[0].size();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 2) {
q.push({i, j});
}
}
}
vector> directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
while (!q.empty()) {
int size = q.size();
time++;
for (int k = 0; k < size; k++) {
auto [x, y] = q.front();
q.pop();
for (auto [i, j] : directions) {
int newX = x + i;
int newY = y + j;
if (newX < 0 || newX >= m || newY < 0 || newY >= n || grid[newX][newY] == 0 || grid[newX][newY] == 2) {
continue;
}
if (grid[newX][newY] == 1) {
grid[newX][newY] = 2;
q.push({newX, newY});
}
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
return -1;
}
}
}
return time == 0 ? 0 : time - 1;
}
};
Python
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
queue = deque()
fresh_oranges = 0
for i in range(m):
for j in range(n):
if grid[i][j] == 2:
queue.append((i, j))
elif grid[i][j] == 1:
fresh_oranges += 1
if fresh_oranges == 0:
return 0
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
time = 0
while queue:
time += 1
for _ in range(len(queue)):
x, y = queue.popleft()
for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 1:
grid[nx][ny] = 2
queue.append((nx, ny))
fresh_oranges -= 1
if fresh_oranges == 0:
return time
return -1
Java
class Solution {
public int orangesRotting(int[][] grid) {
int time = 0;
Queue queue = new LinkedList<>();
int m = grid.length;
int n = grid[0].length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 2) {
queue.add(new int[]{i, j});
}
}
}
int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
while (!queue.isEmpty()) {
int size = queue.size();
boolean foundFresh = false;
for (int k = 0; k < size; k++) {
int[] cell = queue.poll();
int x = cell[0], y = cell[1];
for (int[] dir : directions) {
int newX = x + dir[0];
int newY = y + dir[1];
if (newX < 0 || newX >= m || newY < 0 || newY >= n || grid[newX][newY] == 0 || grid[newX][newY] == 2) {
continue;
}
if (grid[newX][newY] == 1) {
grid[newX][newY] = 2;
queue.add(new int[]{newX, newY});
foundFresh = true;
}
}
}
if (foundFresh) {
time++;
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
return -1;
}
}
}
return time;
}
}
JavaScript
var orangesRotting = function(grid) {
let time = 0
const queue = []
const m = grid.length
const n = grid[0].length
for(let i = 0; i < m; i++){
for(let j = 0; j < n; j++){
if(grid[i][j] === 2){
queue.push([i,j])
}
}
}
while(queue.length > 0){
const size = queue.length
time += 1
for(let k = 0; k < size; k++){
const [x, y] = queue.shift()
for(let [i,j] of [[0,1],[0,-1],[1,0],[-1,0]]){
if(x+i < 0 || x+i >= m || y+j < 0 || y+j >= n || grid[x+i][y+j] === 0 || grid[x+i][y+j] === 2)continue
if(grid[x+i][y+j] === 1){
grid[x+i][y+j] = 2
queue.push([x+i,y+j])
}
}
}
}
console.log(grid)
for(let i = 0; i < m; i++){
for(let j = 0; j < n; j++){
if(grid[i][j] === 1)return -1
}
}
return time === 0 ? 0 : time-1
};