<p>You are given an <code>m x n</code> <code>grid</code> where each cell can have one of three values:</p>

<ul>
	<li><code>0</code> representing an empty cell,</li>
	<li><code>1</code> representing a fresh orange, or</li>
	<li><code>2</code> representing a rotten orange.</li>
</ul>

<p>Every minute, any fresh orange that is <strong>4-directionally adjacent</strong> to a rotten orange becomes rotten.</p>

<p>Return <em>the minimum number of minutes that must elapse until no cell has a fresh orange</em>. If <em>this is impossible, return</em> <code>-1</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2019/02/16/oranges.png" style="width: 650px; height: 137px;" />
<pre>
<strong>Input:</strong> grid = [[2,1,1],[1,1,0],[0,1,1]]
<strong>Output:</strong> 4
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> grid = [[2,1,1],[0,1,1],[1,0,1]]
<strong>Output:</strong> -1
<strong>Explanation:</strong> The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.
</pre>

<p><strong class="example">Example 3:</strong></p>

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

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == grid.length</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 10</code></li>
	<li><code>grid[i][j]</code> is <code>0</code>, <code>1</code>, or <code>2</code>.</li>
</ul>

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        from collections import deque

        '''
    def orangesRotting(self, grid: List[List[int]]) -> int:
        from collections import deque
        queue = deque()
        #step1 build the first set of rotten oranges
        fresh_oranges = 0
        rows,cols = len(grid),len(grid[0])
        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_oranges += 1
        
        # mark the round/level , ie the ticker of timestamp
        queue.append((-1,-1))

        #start the rotting process via BFS
        minutes_elasped = -1 
        directions = [(-1,0),(0,1),(1,0),(0,-1)]
        while queue:
            row,col = queue.popleft()
            if row == -1:

                # we finish one round of processing
                minutes_elasped += 1
                if queue: # to avoid the endless loop
                    queue.append((-1,-1))
            else:
                #this is rotten orange
                # then it would contaminate its neighbors
                for d in directions:
                    neighbor_row, neighbor_col = row+ d[0], col +d[1]
                    if rows > neighbor_row >= 0 and cols > neighbor_col >= 0:
                        if grid[neighbor_row][neighbor_col] == 1:
                            grid[neighbor_row][neighbor_col] =2
                            fresh_oranges -=1 
                            queue.append((neighbor_row, neighbor_col))
        return minutes_elasped if fresh_oranges == 0 else -1 

        '''
        #best solution 

        '''
    def orangesRotting(self, grid: List[List[int]]) -> int:
        from collections import deque
        # number of rows, number of cols
        rows,cols = len(grid), len(grid[0])

        if rows == 0: # check if grid is empty 
            return -1 

        #keep track of fresh oranges
        fresh_count = 0

        # queue with rotten oranges for BFS
        rotten = deque()

        # visit each cell in the grid
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 2:
                    # add the rotten orange coordinates to the queue 
                    rotten.append((r,c))
                elif grid[r][c] ==1:
                    #update fresh oranges count. 
                    fresh_count +=1 

        # keep track of minutes passed 
        minutes_passed = 0

        # if there are rotten organges in the queue and there are still fresh oranges in the grid keep looking 
        while rotten and fresh_count>0:

            #update the number of minutes passed 
            # it is safe to update the minutes by 1, sice we visit oranges level by level in the BFS traversal 
            minutes_passed +=1 

            #process rotten oranges on the current level
            for _ in range(len(rotten)):
                x, y = rotten.popleft()

                # visit all the adjacent cells
                for dx, dy in [(1,0),(-1,0),(0,1),(0,-1)]:
                    # calcualte the coordinates of the adjacent cell
                    xx,yy = x+dx, y+dy

                    # ignore then cell if its out of the grid boundry
                    if xx < 0 or xx == rows or yy < 0 or yy == cols:
                        continue 
                    
                    # ignore the cell if it is empty '0' or visited before '2'
                    if grid[xx][yy] == 0 or grid[xx][yy] == 2:
                        continue 
                    
                    # update the fresh fruit count 
                    fresh_count -= 1

                    # mark the current fresh count as rotten
                    grid[xx][yy] = 2

                    # add the current rotten to the queue 
                    rotten.append((xx,yy))

        #return the number of minutes taken to make all the fresh oranges to be rotten 
        # return -1 if there are fresh oranges left in the grid(as there were no ajdacent rotten oranges to make them rotten )
        return minutes_passed if fresh_count == 0 else -1 
        '''

        fresh, rotten = set(), deque()

        # iterate through the grid to get all the fresh and rotten oranges
        for row in range(len(grid)):
            for col in range(len(grid[0])):

                # if we see a fresh orange, put its position in fresh
                if grid[row][col] == 1:
                    fresh.add((row,col))
                
                # if we see a rotten orange, put its position in rotten
                elif grid[row][col] == 2:
                    rotten.append((row,col))

        minutes = 0
        while fresh and rotten:
            minutes +=1 
            #iterate through the rotten, popping off then (row,col) that's currently in rotten
            # we don't touch the newly added (row,col) that are added during the loop until the next loop
            for rot in range(len(rotten)):
                row,col = rotten.popleft()

                for direction in ((row-1, col), (row+1,col),(row,col+1),(row,col-1)):
                    if direction in fresh:
                    # if the (row,col ) is in fresh, remove it then add it to rotten
                        fresh.remove(direction)
                    # we will perform 4-directional checks on each (row,col)
                        rotten.append(direction)

        # if fresh is not empty , then there is an orange we were not able to reach 4 -directionally
        return -1 if fresh else minutes 


        
16400