# Rotting Oranges

##### December 26, 2023

## Problem #

In a given grid, each cell can have one of three values: 0 (empty), 1 (fresh orange), or 2 (rotten orange). Every minute, any fresh orange that is adjacent to a rotten orange becomes rotten. Find the minimum number of minutes that must elapse until no cell has a fresh orange.

## Solution #

To solve this problem, we can use the Breadth-First Search (BFS) algorithm. The idea is to iteratively spread the rot from the rotten oranges to the adjacent fresh oranges and track the time taken for all fresh oranges to become rotten. If it’s not possible to rot all the fresh oranges (due to isolation), we return -1. Here’s a Python implementation:

```
from collections import deque
def orangesRotting(grid):
rows, cols = len(grid), len(grid[0])
fresh_count = 0
queue = deque()
# Initialize the queue with all rotten oranges and count fresh oranges
for r in range(rows):
for c in range(cols):
if grid[r][c] == 2:
queue.append((r, c))
elif grid[r][c] == 1:
fresh_count += 1
# Directions for adjacent cells (up, down, left, right)
directions = [(0, 1), (0, -1), (-1, 0), (1, 0)]
minutes = 0
# BFS
while queue and fresh_count > 0:
minutes += 1
for _ in range(len(queue)):
x, y = queue.popleft()
for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == 1:
grid[nx][ny] = 2
fresh_count -= 1
queue.append((nx, ny))
return minutes if fresh_count == 0 else -1
# Example Usage
grid = [
[2, 1, 1],
[1, 1, 0],
[0, 1, 1]
]
print("Minimum minutes to rot all oranges:", orangesRotting(grid))
```

In this code:

- We first iterate through the grid to find the initial positions of rotten oranges and count the number of fresh oranges.
- These positions are added to a queue for BFS.
- We then perform BFS. In each round (or minute), we process all the rotten oranges in the queue and try to rot the adjacent fresh oranges.
- Each time a fresh orange rots, we decrease the count of fresh oranges.
- After each round, we increment the
`minutes`

. - The process continues until there are no more fresh oranges or there are no more oranges that can be rotten (i.e., the queue is empty but there are still fresh oranges left).
- If there are no more fresh oranges, we return the
`minutes`

taken; otherwise, we return -1, indicating it’s impossible to rot all oranges.

This algorithm efficiently solves the problem with a time complexity of O(N*M), where N and M are the number of rows and columns in the grid, respectively.