Leetcode 994. Rotting Oranges
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.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.