Sponsored
Sponsored
This approach uses BFS to simulate the rotting process of the oranges. We start with all initially rotten oranges and spread the rot to the 4-adjacent fresh oranges, time step by time step. We use a queue to implement BFS, where each element in the queue represents a rotten orange at a specific time. The key idea is that in one minute, all current rotten oranges will rot their 4-directionally adjacent fresh oranges.
Time Complexity: O(m * n), where m and n are the number of rows and columns in the grid. Each cell is processed at most once.
Space Complexity: O(m * n) for the queue, in the worst case.
1function orangesRotting(grid) {
2 const queue = [];
3 let freshCount = 0;
4 let timeElapsed = 0;
5 const rows = grid.length;
6 const cols = grid[0].length;
7
8 for (let r = 0; r < rows; r++) {
9 for (let c = 0; c < cols; c++) {
10 if (grid[r][c] === 2) {
11 queue.push([r, c, 0]);
12 } else if (grid[r][c] === 1) {
13 freshCount++;
14 }
15 }
16 }
17
18 const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
19 while (queue.length && freshCount > 0) {
20 const [r, c, minutes] = queue.shift();
21 for (const [dr, dc] of directions) {
22 const nr = r + dr, nc = c + dc;
23 if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === 1) {
24 grid[nr][nc] = 2;
25 freshCount--;
26 queue.push([nr, nc, minutes + 1]);
27 timeElapsed = minutes + 1;
28 }
29 }
30 }
31 return freshCount === 0 ? timeElapsed : -1;
32}This JavaScript solution follows the same logic as the Python version. We use an array to simulate the queue, tracking the position and time of rotting. We continue processing until all fresh oranges are rotten or no more rotting can occur.
Instead of using BFS, this approach converts the problem to a depth-first search with memoization. By examining from each fresh orange, one can determine its minimum time to rot by considering all possible paths of infection.
Time Complexity: O(m * n), as each cell is processed recursively.
Space Complexity: O(m * n) because of the memoization table and the call stack in recursion.
1public int OrangesRotting(int[][] grid) {
2 int rows = grid.Length;
3 int cols = grid[0].Length;
4 int[][] memo = new int[rows][];
5 for (int i = 0; i < rows; i++)
memo[i] = new int[cols];
int result = 0, freshCount = 0;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (grid[r][c] == 1) {
freshCount++;
int timeToRot = Dfs(grid, memo, r, c);
if (timeToRot == int.MaxValue) return -1;
result = Math.Max(result, timeToRot);
}
}
}
return freshCount == 0 ? result : -1;
}
private int Dfs(int[][] grid, int[][] memo, int r, int c) {
int rows = grid.Length, cols = grid[0].Length;
if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] == 0) return int.MaxValue;
if (grid[r][c] == 2) return 0;
if (memo[r][c] != 0) return memo[r][c];
grid[r][c] = 0; // Temporarily mark visited
int minTime = int.MaxValue;
int[] dr = {0, 0, -1, 1};
int[] dc = {1, -1, 0, 0};
for (int i = 0; i < 4; i++)
minTime = Math.Min(minTime, Dfs(grid, memo, r + dr[i], c + dc[i]));
grid[r][c] = 1; // Unmark visited
minTime = minTime == int.MaxValue ? int.MaxValue : minTime + 1;
memo[r][c] = minTime;
return minTime;
}The C# solution mimics the DFS approach with memoization similar to Java. It recursively determines the minimum time required for each fresh orange to become rotten, ensuring no redundant calculations with memoization.