# Rotting Oranges

Clarify the problem:

- The problem requires us to determine the minimum number of minutes required to rot all the fresh oranges in a grid.
- We need to implement a function that takes in the grid as input and returns the minimum number of minutes, or -1 if it is not possible to rot all the oranges.

Analyze the problem:

- Input: 2D grid of integers representing the state of oranges.
- Output: Minimum number of minutes required or -1 if not possible.
- Constraints:
- The grid can have 0, 1, or 2 representing empty cells, fresh oranges, and rotten oranges respectively.
- Oranges can rot up, down, left, or right.
- Rotting happens simultaneously.
- If all the fresh oranges cannot be rotten, return -1.
- The grid size is between 1 and 10^3.

Design an algorithm:

- We can solve this problem using a breadth-first search (BFS) approach.
- The idea is to start with the initial state and simulate the rotting process step by step.
- We can use a queue to keep track of the current rotten oranges and their respective minutes.
- We initialize the queue with the coordinates of the rotten oranges in the grid.
- We also initialize a variable to keep track of the total number of fresh oranges.
- We enter a loop while the queue is not empty.
- Inside the loop, we pop an orange from the queue and check its neighboring oranges.
- If a neighboring orange is fresh, we rot it by updating its value to 2 and decrement the count of fresh oranges.
- We enqueue the newly rotten orange and continue the process until the queue is empty.
- Finally, we check if there are any remaining fresh oranges.
- If there are, it means they cannot be rotten, so we return -1. Otherwise, we return the number of minutes.

Explain your approach:

- We will implement a breadth-first search (BFS) algorithm to simulate the rotting process.
- First, we initialize a queue to store the coordinates of the rotten oranges and their respective minutes.
- We iterate over the grid and enqueue the coordinates of the rotten oranges in the queue.
- We also initialize a variable
`fresh_oranges`

to keep track of the count of fresh oranges. - Next, we enter a loop while the queue is not empty.
- Inside the loop, we dequeue an orange from the queue and check its neighboring oranges.
- If a neighboring orange is fresh, we rot it by updating its value to 2 and decrement the
`fresh_oranges`

count. - We enqueue the newly rotten orange and continue the process until the queue is empty.
- After the loop, we check if there are any remaining fresh oranges.
- If there are, it means they cannot be rotten, so we return -1. Otherwise, we return the maximum number of minutes stored in the queue.

Write clean and readable code:

python`class Solution: def orangesRotting(self, grid): rows = len(grid) cols = len(grid[0]) queue = [] fresh_oranges = 0 for i in range(rows): for j in range(cols): if grid[i][j] == 2: queue.append((i, j, 0)) elif grid[i][j] == 1: fresh_oranges += 1 minutes = 0 while queue: i, j, minutes = queue.pop(0) for di, dj in [(0, 1), (0, -1), (1, 0), (-1, 0)]: ni, nj = i + di, j + dj if 0 <= ni < rows and 0 <= nj < cols and grid[ni][nj] == 1: grid[ni][nj] = 2 fresh_oranges -= 1 queue.append((ni, nj, minutes + 1)) return -1 if fresh_oranges != 0 else minutes solution = Solution() grid = [[2, 1, 1], [1, 1, 0], [0, 1, 1]] minutes = solution.orangesRotting(grid) print(minutes) # Output: 4`

Test your code:

- We test the code with a grid containing both fresh and rotten oranges.
- We chose this test case to ensure that the code can handle a mixed configuration of oranges.
- We expect the output to be 4, which represents the minimum number of minutes required to rot all the fresh oranges.

Optimize if necessary:

- The provided solution already uses the BFS approach, which is the most efficient way to solve this problem.
- There are no further optimizations needed for this solution.

Handle error cases:

- The code assumes that the input grid is a valid 2D list containing only 0, 1, or 2 as values.
- If the input is empty or the grid size is outside the constraints, the behavior of the code may be undefined.

Discuss complexity analysis:

- Let N be the number of cells in the grid.
- The time complexity of the solution is O(N) since each cell is visited at most once during the BFS process.
- The space complexity is O(N) as the queue can store up to N/2 coordinates in the worst case.
- The solution is efficient and performs well even for large grid sizes.