🍊994. Rotten Oranges

Medium | Grind 75 | January 16 Monday, 2023

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.

Constraints:

• m == grid.length

• n == grid[i].length

• 1 <= m, n <= 10

• grid[i][j] is 0, 1, or 2.

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.

SOLUTION

1. Initialize an empty queue to hold the positions and rot times of the oranges and a variable called total_minutes to store the overall time taken for all the oranges to rot.

2. Iterate over the grid to locate all the initial rotten oranges, and append their grid indices and a rot time of 0 minutes to the queue since they are already rotten.

3. Loop through the queue containing the positions and rot times of the rotten oranges. Pop an element from the queue, and examine all its four neighbors. If any of the neighbors are fresh oranges, append the neighbor's position and the current rot time + 1 minute as the time to the queue, and change the neighbor's value from 1 to 2 to indicate it has been affected.

4. In step 4, every time a fresh orange neighbor is found, update the total_minutes to the rot time of the parent + 1. Since we are using BFS, the total_minutes will be the time of the last orange in the queue which will be the maximum time taken.

5. Repeat step 4 until the queue is empty.

6. Iterate over the grid again to check for any remaining fresh oranges. If any are found, it means that they could not be reached, and therefore the function should return -1. Otherwise, return the total_minutes.

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        """
            1. BFS on the grid.
            2. iterate over the grid one more time to see any 
            unreached orange exist.
        """
        
        # hold the position of the rotten organes
        queue = deque()

        # iterate to find every initial rotten oranges
        for row in range(len(grid)): 
            for col in range(len(grid[0])): 
                if grid[row][col] == 2: 
                    # append index and minute which will initially be 0
                    queue.append((row, col, 0))
                    
        
        total_minutes = 0
        neighbors = (0,1),(0,-1),(1,0),(-1,0)

        # BFS to propagate oranges rotting
        while queue: 
            row, col, minute = queue.popleft()
            for neigh in neighbors: 
                r, c = row+neigh[0], col+neigh[1]

                # neighbors are inbounds and fresh orange
                if 0 <= r < len(grid) and 0 <= c < len(grid[0]) and grid[r][c] == 1: 
                    queue.append((r,c,minute+1))
                    # neighbor gets rotten
                    grid[r][c] = 2

                    # given a queue the last element in queue will be the last reached orange
                    total_minutes = minute+1 
        
        for row in range(len(grid)): 
            for col in range(len(grid[0])): 
                if grid[row][col] == 1: 
                    return -1

        return total_minutes
        

TIME AND SPACE COMPLEXITY

TIME: O(n *m) where n is the number of rows and m is the number of columns. We iterate n *m) the first time to find the initial rotten position. Then while processing the queue, in the worst case will be another O(n *m). Finally, we iterate the grid one more time resulting in another O(n *m). In total the time complexity will be O(3 * n *m).

SPACE: O(n *m). In the worst case, our queue will require space close to O(nm)

* Written with help from ChatGPT *