# Rotten oranges problem

Tags: , ,

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:

### Show me the implementation

```class Solution:
def orangesRotting(self, grid: List[List[int]]) -&gt; int:
# Make sure we have a valid grid
if len(grid) &lt; 1 or len(grid[0]) &lt; 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) &gt; 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 &gt;= 0 and row &lt; len(grid) \
and col &gt;= 0 and col &lt; len(grid[0]) \
and (row, col) not in visited and grid[row][col] == 1:
newsources.append((row, col))