Problem Analysis

In a given 2D grid, each cell can contain an integer of 0, 1, or 2. These integers represent an empty space, a fresh orange, and a rotten orange respectively. At each minute, any fresh oranges that are directly left/right or above/below to a rotten orange become rotten as well.

Our goal is to determine the minimum number of minutes until no cell contains a fresh orange. If there exists at least one fresh orange that can't be rotted, then we return -1.

Let's walk through the Example 2:

1
2
3// Input grid:
42 1 1
50 1 1
61 0 1 
7
8// After 1st minute:
92 2 1
100 1 1
111 0 1
12
13// After 2nd minute:
142 2 2
150 2 1
161 0 1
17
18// At this point, the fresh orange at the bottom left can't be rotted since it's not directly adjacent to a rotten one. So, we return -1.

Solution

We initialize ans as 0 to store the required minimum number of minutes. We use a helper function isNeighborRotten to check if any of the 4-directionally neighbors of an orange at a cell (i, j) is rotten. If yes, it returns true else false.

We calculate the nextGrid for each minute based on each value in grid. If a cell is fresh and any of its neighbors is rotten, we turn it into rotten. If a cell is rotten, we keep it as it is. If it's empty, we don't change it. After calculating the new nextGrid, we compare it with grid. If they're same, we break the loop else we update grid with nextGrid and increment ans by 1.

Finally, we check if there's still any fresh oranges left in grid. If yes, we return -1. If no, we return ans.

Python Solution

1
2python
3class Solution:
4    def orangesRotting(self, grid: List[List[int]]) -> int:
5        m, n = len(grid), len(grid[0])
6        dirs = [0, 1, 0, -1, 0]
7        
8        def isNeighborRotten(i, j, grid):
9            for k in range(4):
10                r = i + dirs[k]
11                c = j + dirs[k + 1]
12                if r < 0 or r == m or c < 0 or c == n:
13                    continue
14                if grid[r][c] == 2:
15                    return True
16            return False
17
18        ans = 0
19        
20        while True:
21            nextGrid = [[0]*n for _ in range(m)]
22            for i in range(m):
23                for j in range(n):
24                    if grid[i][j] == 1:  # Fresh
25                        if isNeighborRotten(i, j, grid):  # Any of 4-directionally oranges is rotten
26                            nextGrid[i][j] = 2
27                        else:
28                            nextGrid[i][j] = 1
29                    elif grid[i][j] == 2:  # Rotten
30                        nextGrid[i][j] = 2  # Keep rotten
31                        
32            if nextGrid == grid:
33                break
34            grid = nextGrid
35            ans += 1
36                    
37        return -1 if any(1 in row for row in grid) else ans

Java Solution

1
2java
3public class Solution {
4    public int orangesRotting(int[][] grid) {
5        int m = grid.length;
6        int n = grid[0].length;
7        int[] dirs = {0, 1, 0, -1, 0};
8        int ans = 0;
9
10        while (true) {
11            int[][] nextGrid = new int[m][n];
12            for (int i = 0; i < m; ++i) {
13                for (int j = 0; j < n; ++j) {
14                    if (grid[i][j] == 1) {  // Fresh
15                        if (isNeighborRotten(i, j, grid, dirs)) {  // Any of 4-directionally oranges is rotten
16                            nextGrid[i][j] = 2;
17                        } else {
18                            nextGrid[i][j] = 1;
19                        }
20                    } else if (grid[i][j] == 2) {  // Rotten
21                        nextGrid[i][j] = 2;  // Keep rotten
22                    }
23                }
24            }
25            if (Arrays.deepEquals(nextGrid, grid)) {
26                break;
27            }
28            grid = nextGrid;
29            ans += 1;
30        }
31        
32        for (int[] row : grid) {
33            for (int orange : row) {
34                if (orange == 1) {  // If there's any fresh orange left
35                    return -1;
36                }
37            }
38        }
39        return ans;
40    }
41
42    private boolean isNeighborRotten(int i, int j, int[][] grid, int[] dirs) {
43        int m = grid.length;
44        int n = grid[0].length;
45        for (int k = 0; k < 4; ++k) {
46            int r = i + dirs[k];
47            int c = j + dirs[k + 1];
48            if (r < 0 || r == m || c < 0 || c == n) {
49                continue;
50            }
51            if (grid[r][c] == 2) {
52                return true;
53            }
54        }
55        return false;
56    }
57}

C++ Solution

1
2cpp
3class Solution {
4public:
5    int orangesRotting(vector<vector<int>>& grid) {
6        int m = grid.size(), n = grid[0].size();
7        vector<int> dirs = {0, 1, 0, -1, 0};
8        int ans = 0;
9
10        while (true) {
11            vector<vector<int>> nextGrid(m, vector<int>(n));
12            for (int i = 0; i < m; ++i) {
13                for (int j = 0; j < n; ++j) {
14                    if (grid[i][j] == 1) {  // Fresh
15                        if (isNeighborRotten(i, j, grid, dirs)) {  // Any of 4-directionally oranges is rotten
16                            nextGrid[i][j] = 2;
17                        } else {
18                            nextGrid[i][j] = 1;
19                        }
20                    } else if (grid[i][j] == 2) {  // Rotten
21                        nextGrid[i][j] = 2;  // Keep rotten
22                    }
23                }
24            }
25            if (nextGrid == grid) {
26                break;
27            }
28            grid = nextGrid;
29            ans += 1;
30        }
31        
32        for (vector<int>& row : grid) {
33            for (int orange : row) {
34                if (orange == 1) {  // If there's any fresh orange left
35                    return -1;
36                }
37            }
38        }
39        return ans;
40    }
41
42private:
43    bool isNeighborRotten(int i, int j, vector<vector<int>>& grid, vector<int>& dirs) {
44        int m = grid.size(), n = grid[0].size();
45        for (int k = 0; k < 4; ++k) {
46            int r = i + dirs[k];
47            int c = j + dirs[k + 1];
48            if (r < 0 || r == m || c < 0 || c == n) {
49                continue;
50            }
51            if (grid[r][c] == 2) {
52                return true;
53            }
54        }
55        return false;
56    }
57};

We don't have solutions for JavaScript and C# at this moment.# JavaScript Solution

Notably, JavaScript, unlike other languages, does not have built-in multi-dimensional array comparison. Here we will use a library known as Lodash to facilitate this.

1
2javascript
3const _ = require('lodash');
4
5var orangesRotting = function(grid) {
6    let m = grid.length;
7    let n = grid[0].length;
8    let dirs = [0, 1, 0, -1, 0];
9    let ans = 0;
10    
11    const isNeighborRotten = function(i, j) {
12        for (let k = 0; k < 4; ++k) {
13            let r = i + dirs[k];
14            let c = j + dirs[k + 1];
15            if (r < 0 || r === m || c < 0 || c === n) {
16                continue;
17            }
18            if (grid[r][c] == 2) {
19                return true;
20            }
21        }
22        return false;
23    }
24    
25    while (true) {
26        let nextGrid = Array(m).fill(0).map(() => Array(n).fill(0));
27        for (let i = 0; i < m; ++i) {
28            for (let j = 0; j < n; ++j) {
29                if (grid[i][j] == 1) {  // Fresh
30                    if (isNeighborRotten(i, j)) {  // Any of 4-directionally oranges is rotten
31                        nextGrid[i][j] = 2;
32                    } else {
33                        nextGrid[i][j] = 1;
34                    }
35                } else if (grid[i][j] == 2) {  // Rotten
36                    nextGrid[i][j] = 2;  // Keep rotten
37                }
38            }
39        }
40        if (_.isEqual(nextGrid, grid)) {
41            break;
42        }
43        grid = nextGrid.slice(0);
44        ans += 1;
45    }
46    
47    for (let i = 0; i < m; ++i) {
48        for (let j = 0; j < n; ++j) {
49            if (grid[i][j] == 1) {  // If there's any fresh orange left
50                return -1;
51            }
52        }
53    }
54    return ans;
55};

The remaining part of the solution remains almost the same as Python and Java. If an orange is fresh and any of its 4-direction neighbors are rotten, we turn the orange into rotten. If the orange is already rotten, we keep it as it is. Lastly, if there's any fresh orange left at the end, that means all oranges can't be rotted, so we just return -1, otherwise we return the minimum number of minutes to rot all oranges.

C# Solution

1
2csharp
3public class Solution
4{
5    public int OrangesRotting(int[][] grid)
6    {
7        int m = grid.Length;
8        int n = grid[0].Length;
9        int[] dirs = { 0, 1, 0, -1, 0 };
10        int ans = 0;
11
12        while (true)
13        {
14            var nextGrid = new int[m][];
15            for (int i = 0; i < m; ++i)
16                nextGrid[i] = new int[n];
17
18            for (int i = 0; i < m; ++i)
19            {
20                for (int j = 0; j < n; ++j)
21                {
22                    if (grid[i][j] == 1)  // Fresh
23                    {
24                        if (IsNeighborRotten(i, j, grid, dirs))  // Any of 4-directionally oranges is rotten
25                            nextGrid[i][j] = 2;
26                        else
27                            nextGrid[i][j] = 1;
28                    }
29                    else if (grid[i][j] == 2)  // Rotten
30                    {
31                        nextGrid[i][j] = 2;  // Keep rotten
32                    }
33                }
34            }
35
36            if (Enumerable.Range(0, m).All(x => Enumerable.SequenceEqual(grid[x], nextGrid[x])))
37                break;
38
39            grid = nextGrid;
40            ans += 1;
41        }
42
43        return grid.Any(row => row.Any(orange => orange == 1)) ? -1 : ans;
44    }
45
46    private bool IsNeighborRotten(int i, int j, int[][] grid, int[] dirs)
47    {
48        int m = grid.Length;
49        int n = grid[0].Length;
50        for (int k = 0; k < 4; ++k)
51        {
52            int r = i + dirs[k];
53            int c = j + dirs[k + 1];
54            if (r < 0 || r == m || c < 0 || c == n)
55                continue;
56            if (grid[r][c] == 2)
57                return true;
58        }
59        return false;
60    }
61}

Just like the JavaScript solution, C# version also relies on a deep equality check while comparing the current grid with nextGrid. Otherwise, the logic remains the same as that of Python and Java implementations.