Given a matrix mat[][] of dimension n * m where each cell in the matrix can have values 0, 1 or 2 which has the following meaning:
0 : Empty cell
1 : Cell have fresh oranges
2 : Cell have rotten oranges
We have to determine what is the earliest time after which all the oranges are rotten. A rotten orange at index (i, j) can rot other fresh orange at indexes (i-1, j), (i+1, j), (i, j-1), (i, j+1) (up, down, left and right) in a unit time.
Note: Your task is to return the minimum time to rot all the fresh oranges. If not possible returns -1.
Examples:
Input: mat[][] = [[0, 1, 2], [0, 1, 2], [2, 1, 1]] Output: 1 Explanation: Oranges at positions (0,2), (1,2), (2,0) will rot oranges at (0,1), (1,1), (2,2) and (2,1) in unit time.
Input: mat[][] = [[2, 2, 0, 1]] Output: -1 Explanation: Oranges at (0,0) and (0,1) can't rot orange at (0,3).
Input: mat[][] = [[2, 2, 2], [0, 2, 0]] Output: 0 Explanation: There is no fresh orange.
Constraints:
1 ≤ mat.size() ≤ 500
1 ≤ mat[0].size() ≤ 500
mat[i][j] = {0, 1, 2}
Approach 01:
-
C++
-
Python
#include <vector>
#include <queue>
using namespace std;
class Solution {
public:
int orangesRotting(vector<vector<int>>& grid) {
int rows = grid.size(), cols = grid[0].size();
queue<pair<int, int>> rottenQueue;
int freshCount = 0;
// Identify initial rotten oranges and count fresh oranges
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == 2) {
rottenQueue.push({i, j});
} else if (grid[i][j] == 1) {
freshCount++;
}
}
}
int minutesElapsed = 0;
vector<vector<int>> visited(rows, vector<int>(cols, 0));
vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
while (!rottenQueue.empty()) {
int queueSize = rottenQueue.size();
minutesElapsed++;
while (queueSize--) {
pair<int, int> cell = rottenQueue.front();
int row = cell.first, col = cell.second;
rottenQueue.pop();
for (size_t i = 0; i < directions.size(); i++) {
int newRow = row + directions[i].first;
int newCol = col + directions[i].second;
if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols &&
visited[newRow][newCol] == 0 && grid[newRow][newCol] == 1) {
freshCount--;
rottenQueue.push({newRow, newCol});
visited[newRow][newCol] = 1;
}
}
}
}
return freshCount == 0 ? max(0, minutesElapsed - 1) : -1;
}
};
from collections import deque
from typing import List
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
rows, cols = len(grid), len(grid[0])
rottenQueue = deque()
freshOranges = 0
for i in range(rows):
for j in range(cols):
if grid[i][j] == 2:
rottenQueue.append((i, j))
elif grid[i][j] == 1:
freshOranges += 1
minutesElapsed = 0
visited = [[0] * cols for _ in range(rows)]
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
while rottenQueue:
levelSize = len(rottenQueue)
minutesElapsed += 1
for _ in range(levelSize):
row, col = rottenQueue.popleft()
for dRow, dCol in directions:
newRow, newCol = row + dRow, col + dCol
if 0 <= newRow < rows and 0 <= newCol < cols and visited[newRow][newCol] == 0 and grid[newRow][newCol] == 1:
freshOranges -= 1
rottenQueue.append((newRow, newCol))
visited[newRow][newCol] = 1
return max(0, minutesElapsed - 1) if freshOranges == 0 else -1
Time Complexity:
- Grid Traversal:
Each cell in the grid is visited once during initialization, contributing \( O(R \times C) \), where \( R \) is the number of rows and \( C \) is the number of columns.
- BFS Processing:
Each fresh orange is processed once when it turns rotten, leading to a worst-case complexity of \( O(R \times C) \).
- Total Time Complexity:
The overall time complexity is \( O(R \times C) \).
Space Complexity:
- Queue Storage:
In the worst case, all oranges could be stored in the queue, requiring \( O(R \times C) \) space.
- Visited Grid:
A separate \( R \times C \) grid is used to track visited cells, contributing \( O(R \times C) \) space.
- Total Space Complexity:
The overall space complexity is \( O(R \times C) \).