Rotting Oranges

Problem Summary

• Given a 2D grid of oranges:
  • 1 is fresh orange
  • 2 is rotten orange
  • 0 is empty cell
• If in one minute, every orange adjacent to a rotten orange becomes rotten
• how many minutes it would take for all oranges to become rotten
• if its not possible to make every orange rotten then return -1

What is Being Asked?

• Run BFS, multi-source to rot all orange and increment time

Key Observations

• Need to run a Multi-Source Breadth First

Main Concepts Used

• Queue
• Breadth First
• Multi Source

Time & Space Complexity

• Time: $O(n\ast m)$ → Reason: We touch each cell once
• Space: $O(n\ast m)$ → Reason: We store each cell in a Queue

Code

class Solution:
    empty = 0
    fresh = 1
    rotten = 2
    minute = 0
    directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]

    def orangesRotting(self, grid: List[List[int]]) -> int:
        # every iteration is one minute spent
        # start at rotten orange then perform bfs
        # do not run bfs on already run orange

        # outer loop
        # iterate through each cell in the grid
        # if empty or fresh orange, return
        # if rotten run bfs

        # need a global minute counter that needs to be incremented

        # bfs():
        # if empty cell return
        # bi-directionally run bfs
        # increment minute after all 4 directions
        #     0 1 2
        # 0  [#,1,1]
        # 1  [1,1,0]
        # 2  [0,1,1]
        # row = 0
        # col = 0
        # cell = 2
        # q = (1,0), (0,1)
        # curRow = 0
        # curCol = 0
        ROWS, COLS = len(grid), len(grid[0])
        q = deque()
        fresh = 0
        for row in range(ROWS):
            for col in range(COLS):
                if grid[row][col] == self.fresh:
                    fresh += 1
                if grid[row][col] == self.rotten:
                    q.append([row,col])
        # we have counted all fresh oranges in our system
        # we have added all rotten oranges in our queue
        while q and fresh > 0:
            for _ in range(len(q)): # one layer from all sources
                curRow, curCol = q.popleft()
                for changeInRow, changeInCol in self.directions:
                    newRow = curRow + changeInRow
                    newCol = curCol + changeInCol
                    if min(newRow, newCol) < 0 or newRow == len(grid) or newCol == len(grid[0]):
                        continue # out of bounds
                    if grid[newRow][newCol] == self.empty or grid[newRow][newCol] == self.rotten:
                        continue
                    fresh -= 1
                    grid[newRow][newCol] = self.rotten
                    q.append([newRow, newCol])
            self.minute += 1
        return self.minute if fresh == 0 else -1

Common Mistakes / Things I Got Stuck On

• Tried and implemented a full Depth First Traversal solution first
• Could not remember how to do a BFS
• Missing edge cases where not all oranges can be rotten
• Off by one error etc