[link](https://leetcode.com/problems/rotting-oranges/)

---

You are given an m x n grid where each cell can have one of three values:

- 0 representing an empty cell,
- 1 representing a fresh orange, or
- 2 representing a rotten orange.

Every minute, any fresh orange that is 4-directionally adjacent 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.

#### Example 1:


Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4

#### Example 2:

Input: grid = [[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.

#### Example 2:

Input: grid = [[0,2]]
Output: 0
Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.

#### Constraints:

- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 10
- grid[i][j] is 0, 1, or 2.

---

The orangesRotting function takes a 2D grid represented as a list of lists of integers and returns the minimum time required for all fresh oranges to become rotten. If it is not possible for all oranges to become rotten, the function returns -1.

The q deque is used to store the coordinates of rotten oranges. The fresh variable is initialized to 0, which will store the count of fresh oranges. The time variable is initialized to 0, which will store the minimum time required.

The nested loop is used to iterate over each cell in the grid. If the current cell contains 2, it means it is a rotten orange. Its coordinates are added to the q deque. If the current cell contains 1, it means it is a fresh orange. The fresh count is incremented.

The bfs function performs a breadth-first search starting from the rotten oranges in the q deque. Inside the bfs function, the direction list represents the possible neighboring cells: right, left, down, and up. The while loop continues until the q deque is empty or all fresh oranges have become rotten. In each iteration, the rotten oranges in the current layer are processed. For each rotten orange, its neighboring cells are checked.

If a neighboring cell is out of bounds or not a fresh orange (already rotten or empty), it is skipped. If a neighboring cell is a fresh orange, it is marked as rotten by setting its value to 2. Its coordinates are added to the q deque, and the fresh count is decremented.

After processing all the oranges in the current layer, the time is incremented. Once the bfs function completes, the fresh count and time are updated. The function returns the time if all fresh oranges have become rotten (fresh count is 0), otherwise it returns -1.

#### Solution 1

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        q = collections.deque()
        fresh = 0
        time = 0

        for r in range(len(grid)):
            for c in range(len(grid[0])):
                if grid[r][c] == 2:
                    q.append((r, c))
                if grid[r][c] == 1:
                    fresh += 1
        
        def bfs(q, fresh, time):
            direction = [[0, 1], [0, -1], [1, 0], [-1, 0]]
            while q and fresh > 0:
                for _ in range(len(q)):
                    r, c = q.popleft()
                    for dr, dc in direction:
                        row, col = r + dr, c + dc
                        if (min(row, col) < 0 or
                            row == len(grid) or
                            col == len(grid[0]) or
                            grid[row][col] != 1):
                            continue
                        grid[row][col] = 2
                        q.append((row, col))
                        fresh -= 1
                time += 1
            return fresh, time

        fresh, time = bfs(q, fresh, time)

        return time if fresh == 0 else -1
        

O(T): O(n * m)
O(S): O(n * m)