In this guide, you will get 994. Rotting Oranges LeetCode Solution with the best time and space complexity. The solution to Rotting Oranges problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
You are given an m x n grid where each cell can have one of three values:
0 representing an empty cell,
1 representing a fresh orange, or
2 representing 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.
Example 3:
Input: grid = [[0,2]]
Output: 0
Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.
Constraints:
m == grid.length
n == grid[i].length
1 <= m, n <= 10
grid[i][j] is 0, 1, or 2.
Complexity Analysis
Time Complexity: O(kmn)
Space Complexity: O(mn)
994. Rotting Oranges LeetCode Solution in C++
class Solution {
public:
int orangesRotting(vector<vector<int>>& grid) {
constexpr int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
const int m = grid.size();
const int n = grid[0].size();
auto isNeighborRotten = [&](int i, int j, const vector<vector<int>>& grid) {
for (const auto& [dx, dy] : dirs) {
const int r = i + dx;
const int c = j + dy;
if (r < 0 || r == m || c < 0 || c == n)
continue;
if (grid[r][c] == 2)
return true;
}
return false;
};
int ans = 0;
while (true) {
vector<vector<int>> nextGrid(m, vector<int>(n));
// Calculate `nextGrid` based on `grid`.
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (grid[i][j] == 1) { // fresh
// Any of the 4-directionally oranges is rotten
if (isNeighborRotten(i, j, grid))
nextGrid[i][j] = 2;
else
nextGrid[i][j] = 1;
} else if (grid[i][j] == 2) { // rotten
nextGrid[i][j] = 2; // Keep rotten.
}
if (nextGrid == grid)
break;
grid = nextGrid;
++ans;
}
return any_of(grid.begin(), grid.end(),
[&](vector<int>& row) {
return ranges::any_of(row, [&](int orange) { return orange == 1; });
})
? -1
: ans;
}
}; /* code provided by PROGIEZ */
994. Rotting Oranges LeetCode Solution in Java
class Solution {
public:
int orangesRotting(vector<vector<int>>& grid) {
constexpr int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
const int m = grid.size();
const int n = grid[0].size();
int countFresh = 0;
queue<pair<int, int>> q;
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (grid[i][j] == 1)
++countFresh;
else if (grid[i][j] == 2)
q.emplace(i, j);
if (countFresh == 0)
return 0;
int step = 0;
for (; !q.empty(); ++step)
for (int sz = q.size(); sz > 0; --sz) {
const auto [i, j] = q.front();
q.pop();
for (const auto& [dx, dy] : dirs) {
const int x = i + dx;
const int y = j + dy;
if (x < 0 || x == m || y < 0 || y == n)
continue;
if (grid[x][y] != 1)
continue;
grid[x][y] = 2; // Mark grid[x][y] as rotten.
q.emplace(x, y); // Push the newly rotten orange to the queue.
--countFresh; // Decrease the count of fresh oranges by 1.
}
}
return countFresh == 0 ? step - 1 : -1;
}
}; // code provided by PROGIEZ
