Rotting Oranges - Leetcode Solution

The Rotting Oranges problem on LeetCode asks you to solve a problem where you are given a 2D grid representing the initial status of a bunch of oranges, with values of 0 representing an empty cell, 1 representing a fresh orange, and 2 representing a rotten orange. Each minute, any fresh orange that is adjacent to a rotten orange becomes rotten too. Determine the minimum number of minutes that must elapse until no cell has a fresh orange. If this is not possible, return -1 instead.

To solve this problem, we can use BFS (breadth-first search) to simulate the process of the oranges getting rotten. First, we can count the number of fresh oranges and the positions of all the rotten oranges. Then, we can start BFS from the positions of all the rotten oranges, and for each level of the BFS, all the fresh oranges that are adjacent to any of the rotten oranges will become rotten. We can keep track of the number of fresh oranges that are turned into rotten oranges in each level of the BFS, and add this number to the total number of minutes it takes to fully rot all the fresh oranges.

If all the fresh oranges have been rotten at the end, return the total number of minutes. Otherwise, return -1.

Here is the detailed solution in Python:

from collections import deque

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        # find all the positions of the rotten oranges
        rotten = []
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 2:
                    rotten.append((i, j))
        
        # BFS to simulate the process of the oranges getting rotten
        fresh_count = sum(1 for row in grid for cell in row if cell == 1)
        minutes = 0
        while rotten:
            new_rotten = []
            for i, j in rotten:
                for x, y in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:
                    if 0 <= x < len(grid) and 0 <= y < len(grid[0]) and grid[x][y] == 1:
                        grid[x][y] = 2
                        fresh_count -= 1
                        new_rotten.append((x, y))
            rotten = new_rotten
            if rotten:
                minutes += 1
        
        return minutes if fresh_count == 0 else -1

Time Complexity: O(N), where N is the total number of cells in the grid, since we visit each cell at most once in the BFS.

Space Complexity: O(N), for the queue used in the BFS and the list used to store the positions of the rotten oranges.

1