Dare2Solve
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
.
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.
Initialize a Queue and Count Fresh Oranges:
Breadth-First Search (BFS):
Check Remaining Fresh Oranges:
-1
as it's impossible to rot all oranges. Otherwise, return the time taken.O(m * n)
, where m
is the number of rows and n
is the number of columns in the grid. This is because each cell is processed at most once.O(m * n)
because in the worst case, all cells could be added to the queue.class Solution {
public:
int orangesRotting(vector<vector<int>>& grid) {
int time = 0;
queue<pair<int, int>> 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<pair<int, int>> 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;
}
};
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
class Solution {
public int orangesRotting(int[][] grid) {
int time = 0;
Queue<int[]> 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;
}
}
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
};