Problem Statement

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 3:

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

BFS: Iterative

from collections import deque

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        ROWS, COLS = len(grid), len(grid[0])
        ans, fresh_count = 0, 0
        queue = deque()

        # 1) Find all rotten oranges and enque them
        for r in range(ROWS):
            for c in range(COLS):
                if grid[r][c] == 2:
                    queue.append((r, c, 0))
                elif grid[r][c] == 1:
                    fresh_count += 1
                else:
                    pass

        # 2) BFS through the grid
        while queue and fresh_count > 0:
            for _ in range(len(queue)):
                ro, co, mins = queue.popleft()
                mins += 1
                
                # up, right, down, left
                for dr, dc in [(-1,0),(0,1),(1,0),(0,-1)]:
                    r = ro + dr
                    c = co + dc

                    if 0 <= r < ROWS and 0 <= c < COLS and grid[r][c] == 1:
                        grid[r][c] = 2
                        fresh_count -= 1
                        ans = max(ans, mins)
                        queue.append((r, c, mins))
    
        if fresh_count > 0:
            return -1
        else:
            return ans

Leetcode 994 - Rotting Oranges