LeetCode 994 - Rotting Oranges - 2022.12.30 solution

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        """ How to solve it: First iterate through every cell to find all the rotting oranges, and add them
        to a deque.  Also count the fresh oranges.
        Then do repeated iterations through the length of the deque (at the time of the start of the
        iteration) to pop each rotting orange, add its fresh-orange neighbors to the end of the deque,
        decrement the count of fresh oranges, and increment the minute-counter.
        When the deque is empty, if the count of fresh oranges is still greater than 0, return -1, else return
        the number of minutes passed.
        """
        fresh_oranges = 0
        ROWS = len(grid)
        COLS = len(grid[0])
        rotting_oranges = deque()
        minutes = -1
        for r in range(ROWS):
            for c in range(COLS):
                val = grid[r][c]
                if val == 1:
                    fresh_oranges += 1
                elif val == 2:
                    rotting_oranges.append((r, c))

        visited = set()
        while rotting_oranges:
            minutes += 1
            for i in range(len(rotting_oranges)):
                rotten_orange = rotting_oranges.popleft()
                grid[rotten_orange[0]][rotten_orange[1]] = 2
                adjustments = [
                    [0, 1,],
                    [0, -1],
                    [1, 0],
                    [-1, 0],
                ]
                neighbors = [(rotten_orange[0] + a[0], rotten_orange[1] + a[1]) for a in adjustments]
                for neighbor in neighbors:
                    if neighbor[0] < 0 or neighbor[0] >= ROWS or \
                       neighbor[1] < 0 or neighbor[1] >= COLS:
                       continue
                    elif grid[neighbor[0]][neighbor[1]] != 1:
                        continue
                    elif neighbor in visited:
                        continue
                    visited.add(neighbor)
                    fresh_oranges -= 1
                    rotting_oranges.append(neighbor)
        if fresh_oranges > 0:
            return -1
        return max(0, minutes)