Rotten Oranges
Problem Statement
You are given an m x n grid where each cell can have one of three values:
0representing an empty cell,1representing a fresh orange, or2representing a rotten orange.
Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.
Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.
Example 1
Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4
Example 2
Input: grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.
Video Explanation
Java Code
import java.util.LinkedList;
import java.util.Queue;
class Node {
int row, col, time;
public Node(int row, int col, int time) {
this.row = row;
this.col = col;
this.time = time;
}
}
class Solution {
int[][] distances = new int[][]{{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
private boolean isValidCell(int row, int col, int rows, int cols) {
if(row >= 0 && row < rows && col >= 0 && col < cols)
return true;
else
return false;
}
public int orangesRotting(int[][] grid) {
int rows = grid.length;
int cols = grid[0].length;
int freshOranges = 0;
Queue<Node> queue = new LinkedList<>();
for(int i = 0; i < rows; i++) {
for(int j = 0; j < cols; j++) {
if(grid[i][j] == 2) {
queue.add(new Node(i, j, 0));
} else if(grid[i][j] == 1) {
freshOranges += 1;
}
}
}
int minTime = 0;
while(!queue.isEmpty()) {
Node node = queue.poll();
for(int[] distance : distances) {
int newRow = node.row + distance[0];
int newCol = node.col + distance[1];
if(isValidCell(newRow, newCol, rows, cols) && grid[newRow][newCol] == 1) {
queue.add(new Node(newRow, newCol, node.time + 1));
grid[newRow][newCol] = 2;
minTime = node.time + 1;
freshOranges -= 1;
}
}
}
return freshOranges == 0 ? minTime : -1;
}
}
C++ Code
#include<bits/stdc++.h>
using namespace std;
class Node {
public:
int row, col, time;
Node(int row, int col, int time) {
this->row = row;
this->col = col;
this->time = time;
}
};
class Solution {
public:
bool isValidCell(int row, int col, int rows, int cols) {
if(row >= 0 && row < rows && col >= 0 && col < cols)
return true;
else
return false;
}
int orangesRotting(vector<vector<int>>& grid) {
int rows = grid.size();
int cols = grid[0].size();
int freshOranges = 0;
vector<vector<int>> distances = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
queue<Node> queue;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == 2) {
queue.push(Node(i, j, 0));
} else if(grid[i][j] == 1) {
freshOranges += 1;
}
}
}
int minTime = 0;
while (!queue.empty()) {
Node node = queue.front();
queue.pop();
for (const auto& distance : distances) {
int newRow = node.row + distance[0];
int newCol = node.col + distance[1];
if (isValidCell(newRow, newCol, rows, cols) && grid[newRow][newCol] == 1) {
queue.push(Node(newRow, newCol, node.time + 1));
grid[newRow][newCol] = 2;
minTime = node.time + 1;
freshOranges -= 1;
}
}
}
return freshOranges == 0 ? minTime : -1;
}
};
Python Code
from typing import List
from collections import deque
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
rows, cols = len(grid), len(grid[0])
distances = [(-1, 0), (0, -1), (0, 1), (1, 0)]
fresh_oranges = 0
def is_valid_cell(row, col):
return 0 <= row < rows and 0 <= col < cols
queue = deque()
for i in range(rows):
for j in range(cols):
if grid[i][j] == 2:
queue.append((i, j, 0))
elif grid[i][j] == 1:
fresh_oranges += 1
min_time = 0
while queue:
row, col, time = queue.popleft()
for direction in distances:
new_row, new_col = row + direction[0], col + direction[1]
if is_valid_cell(new_row, new_col) and grid[new_row][new_col] == 1:
queue.append((new_row, new_col, time + 1))
grid[new_row][new_col] = 2
min_time = time + 1
fresh_oranges -= 1
return min_time if fresh_oranges == 0 else -1
Javascript Code
var orangesRotting = function(grid) {
const distances = [[-1, 0], [0, -1], [0, 1], [1, 0]];
const isValidCell = (row, col, rows, cols) => {
return row >= 0 && row < rows && col >= 0 && col < cols;
};
class Node {
constructor(row, col, time) {
this.row = row;
this.col = col;
this.time = time;
}
}
const rows = grid.length;
const cols = grid[0].length;
let freshOranges = 0;
const queue = [];
for (let i = 0; i < rows; i++) {
for (let j = 0; j < cols; j++) {
if (grid[i][j] === 2) {
queue.push(new Node(i, j, 0));
} else if (grid[i][j] === 1) {
freshOranges += 1;
}
}
}
let minTime = 0;
while (queue.length > 0) {
const node = queue.shift();
for (const distance of distances) {
const newRow = node.row + distance[0];
const newCol = node.col + distance[1];
if (isValidCell(newRow, newCol, rows, cols) && grid[newRow][newCol] === 1) {
queue.push(new Node(newRow, newCol, node.time + 1));
grid[newRow][newCol] = 2;
minTime = node.time + 1;
freshOranges -= 1;
}
}
}
return freshOranges === 0 ? minTime : -1;
};
Go Code
type Node struct {
row, col, time int
}
var distances = [][]int{{-1, 0}, {0, -1}, {0, 1}, {1, 0}}
func isValidCell(row, col, rows, cols int) bool {
return row >= 0 && row < rows && col >= 0 && col < cols
}
func orangesRotting(grid [][]int) int {
rows := len(grid)
cols := len(grid[0])
freshOranges := 0
queue := make([]Node, 0)
for i := 0; i < rows; i++ {
for j := 0; j < cols; j++ {
if grid[i][j] == 2 {
queue = append(queue, Node{i, j, 0})
} else if grid[i][j] == 1 {
freshOranges += 1
}
}
}
minTime := 0
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
for _, distance := range distances {
newRow := node.row + distance[0]
newCol := node.col + distance[1]
if isValidCell(newRow, newCol, rows, cols) && grid[newRow][newCol] == 1 {
queue = append(queue, Node{newRow, newCol, node.time + 1})
grid[newRow][newCol] = 2
minTime = node.time + 1
freshOranges -= 1
}
}
}
if freshOranges == 0 {
return minTime
} else {
return -1
}
}
Complexity Analysis
- Time Complexity: O(N*M), where N*M is the size of the grid.
- Space Complexity: O(N*M), where N*M is the size of the grid. In the worst case, the grid is filled with rotten oranges. As a result, the queue would be initialized with all the cells in the grid.