Rotting Oranges

BFS

Problem

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.

Thought Process

• This question is similar to Walls and Gates

• We will store all the rotten oranges ('2') in a queue while alos keeping track of how many fresh oranges we have.

• We are applying BFS to search for the rotten oranges neighbors so we can rot them too. We are processing rotten oranges by level.

Solution

from collections import deque 
class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        
        
        q = deque()
        count_fresh = 0 # keep track of fresh oranges
        
        
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 2:
                    q.append([i,j])
                elif grid[i][j] == 1:
                    count_fresh+=1
                    
        if count_fresh == 0:
            return 0
        
        c = 0
        direc = [[1,0], [-1,0],[0,-1], [0,1]]
        while q and count_fresh > 0:
            c+=1
            level_size = len(q)
            
            for _ in range(level_size):    
                coor = q.popleft()
                x = coor[0]
                y = coor[1]
                for i in direc:
                    newX = x+i[0] #new x-coor
                    newY = y+i[1] #new y-coor
                    
                    if newX < 0 or newX >= len(grid) or newY < 0 or newY == len(grid[0]):
                        continue
                        
                    if grid[newX][newY] == 0 or grid[newX][newY] == 2:
                        continue
                        
                    count_fresh-=1
                    
                    grid[newX][newY] = 2
                    q.append([newX,newY])
                    
            
        return c if count_fresh == 0 else -1
        

Time Complexity

• Time: O(m*n)

• Space: O(m*n)