from collections import deque

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        directions = [(1,0),(0,1),(-1,0),(0,-1)]
        m, n = len(grid), len(grid[0])

        count = 0
        queue = deque()
        for i in range(m):
           for j in range(n):
                if grid[i][j] == 2:
                    queue.append((i, j))
                elif grid[i][j] == 1:
                    count += 1


        minute = 0
        while queue and count > 0:
            for _ in range(len(queue)):
                rotten_i, rotten_j = queue.popleft()
                for di, dj in directions:
                    if 0 <= rotten_i+di < m and \
                        0 <= rotten_j+dj < n and grid[rotten_i+di][rotten_j+dj] == 1:
                        grid[rotten_i+di][rotten_j+dj] = 2
                        queue.append((rotten_i+di, rotten_j+dj))
                        count -= 1

            minute += 1

        return minute if count == 0 else -1

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        if not grid or not grid[0]:
            return 0 # no orange

        h, w = len(grid), len(grid[0])
        fresh_oranges = 0
        curr_rotten_oranges = []
        max_steps = 0

        for i in range(h):
            for j in range(w):
                if grid[i][j] == 1:
                    fresh_oranges += 1
                elif grid[i][j] == 2:
                    curr_rotten_oranges.append((i, j))

        def valid_fresh_orange(i, j):
            return 0 <= i < h and 0 <= j < w and grid[i][j] == 1

        directions = [(1,0),(-1,0),(0,1),(0,-1)]
        while fresh_oranges > 0 and curr_rotten_oranges:
            next_rotten_oranges = []

            for i, j in curr_rotten_oranges:
                for dx, dy in directions:
                    if valid_fresh_orange(i+dx, j+dy):
                        grid[i+dx][j+dy] = 2
                        fresh_oranges -= 1
                        next_rotten_oranges.append((i+dx, j+dy))

            curr_rotten_oranges = next_rotten_oranges
            max_steps += 1


        return -1 if fresh_oranges else max_steps