Rotting Oranges

rotting-oranges.py

from collections import deque
class Solution:
    def __init__(self):
        self.grid = None
        self.rows = 0
        self.cols = 0
    
    def bfs(self, rottens: list[tuple[int]]) -> int:
        q = deque([(rr, rc, 0) for (rr, rc) in rottens])
        minutes = 0
        while len(q) > 0:
            r, c, d = q.popleft()
            if (
                (r < 0 or r >= self.rows or c < 0 or c >= self.cols)
                or self.grid[r][c] <= 0
            ):
                continue
            q.append((r - 1, c, d + 1)) # top
            q.append((r, c + 1, d + 1)) # right
            q.append((r + 1, c, d + 1)) # bottom
            q.append((r, c - 1, d + 1)) # left
            
            # mark current node as visited - we use a different integer to represent this state
            minutes = max(minutes, d)
            self.grid[r][c] = -1

        return minutes
        
    def print_matrix(self):
        pretty_str = '\n'.join('[ ' + ', '.join(str(e) for e in row) + ' ]' for row in self.grid)
        print(pretty_str)

    def orangesRotting(self, grid: List[List[int]]) -> int:
        self.rows = len(grid)
        self.cols = len(grid[0])
        # Part-I: get coords for rotten oranges
        rottens = []
        for i in range(self.rows):
            for j in range(self.cols):
                if grid[i][j] == 2:
                    rottens.append((i, j))
        # Part-II a: initiate a BFS for each rotten orange
        # Part-II b: mark nodes as rotten while tracking depth while doing so
        self.grid = grid
        minutes = self.bfs(rottens)
        # Part-III: identify if atleast single node in the grid remains unaffected
        lone_ranger = any(any(v == 1 for v in row) for row in grid)
        
        return -1 if lone_ranger else minutes