Rotten oranges problem goes like: In a given grid, each cell can have one of three values:
- the value 0 representing an empty cell;
- the value 1 representing a fresh orange;
- the value 2 representing a rotten orange.
Every minute, any fresh orange that is adjacent (4-directionally) 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
instead.
Input: [[2,1,1],[1,1,0],[0,1,1]] Output: 4 Input: [[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.
Thoughts
Rotting oranges problem offers a unique perspective on identifying a graph search problem. At first glance, it seems like the solution to the problem lies in changing the status of the given grid on multiple time steps while counting the steps and making sure that we come to a conclusion to our iterations, akin to solving a sudoku puzzle, where the state of the entire grid matters.
On further inspection though, we can see that we do not need to worry about the state of the entire grid, just the fresh oranges adjacent newly rotting oranges at each time step. We can consider the oranges as nodes of a graph, and the fresh oranges around them as connected to these nodes. We do not know the entire state of the graph beforehand, but we know that the adjacent nodes will expose themselves as time passes. This pushes us towards the idea of a Breadth-First Search, where we topologically move level by level through a graph.
This problem also has some interesting edge cases, with it being necessary to parse the graph to identify such cases:
Invalid grid | return -1 |
Grid with all rotten oranges | return 0 |
Grid with no rotten oranges and no fresh | return 0 |
Grid with no rotten oranges and fresh present | return -1 |
Grid post BFS with fresh oranges left | return -1 |
Grid post BFS with all rotten oranges | return count |
Show me the implementation
class Solution: def orangesRotting(self, grid: List[List[int]]) -> int: # Make sure we have a valid grid if len(grid) < 1 or len(grid[0]) < 1: return -1 sources = [] ones = 0 for i in range(len(grid)): for j in range(len(grid[i])): if grid[i][j] == 2: sources.append((i, j)) elif grid[i][j] == 1: ones += 1 if len(sources) == 0: # In case of no rotten oranges, return value depending # on the state of the grid if ones == 0: return 0 else: return -1 directions = [[-1, 0], [1, 0], [0, -1], [0, 1]] # Grid is initially at t = -1 count = -1 visited = set(sources) # End the BFS when there are no new sources left while len(sources) > 0: count += 1 newsources = [] for source in sources: i, j = source grid[i][j] = 2 for direction in directions: row = i + direction[0] col = j + direction[1] # Make sure it is a valid row and column, # It is not visited, and it is a fresh orange if row >= 0 and row < len(grid) \ and col >= 0 and col < len(grid[0]) \ and (row, col) not in visited and grid[row][col] == 1: newsources.append((row, col)) visited.add((row, col)) sources = newsources # Make sure there are no fresh oranges left in the grid for i in grid: for j in i: if j == 1: return -1 return count
The runtime complexity of BFS is O(V + E), which in our scenario translates to moving to every node, i.e. O(n * m) where n and m are dimensions of the grid. The space complexity of BFS is O(V), which similarly as time complexity translates into O(n*m)
This article is contributed by Khushman Patel