Rotting Fruit

Problem Statement

You are given a 2-D matrix grid. Each cell can have one of three possible values:

  • 0 representing an empty cell
  • 1 representing a fresh fruit
  • 2 representing a rotten fruit

Every minute, if a fresh fruit is horizontally or vertically adjacent to a rotten fruit, then the fresh fruit also becomes rotten.

Return the minimum number of minutes that must elapse until there are zero fresh fruits remaining. If this state is impossible within the grid, return -1.

Example 1:

# Input: grid = [[1,1,0],[0,1,1],[0,1,2]]
# Output: 4

Example 2:

# Input: grid = [[1,0,1],[0,2,0],[1,0,1]]
# Output: -1

Constraints:

  • 1 <= grid.length, grid[i].length <= 10

You should aim for a solution with O(m * n) time and O(m * n) space, where m is the number of rows and n is the number of columns in the given grid.

You should aim for a solution with O(m * n) time and O(m * n) space, where m is the number of rows and n is the number of columns in the given grid.

Hint 1

The DFS algorithm is not suitable for this problem because it explores nodes deeply rather than level by level. In this scenario, we need to determine which oranges rot at each second, which naturally fits a level-by-level traversal. Can you think of an algorithm designed for such a traversal?

Hint 2

We can use the Breadth First Search (BFS) algorithm. At each second, we rot the oranges that are adjacent to the rotten ones. So, we store the rotten oranges in a queue and process them in one go. The time at which a fresh orange gets rotten is the level at which it is visited. How would you implement it?

Hint 3

We traverse the grid and store the rotten oranges in a queue. We then run a BFS, processing the current level of rotten oranges and visiting the adjacent cells of each rotten orange. We only insert the adjacent cell into the queue if it contains a fresh orange. This process continues until the queue is empty. The level at which the BFS stops is the answer. However, we also need to check whether all oranges have rotted by traversing the grid. If any fresh orange is found, we return -1; otherwise, we return the level.

Solution

from collections import deque


def oranges_rotting(grid: list[list[int]]) -> int:
    queue = deque()
    fresh = 0
    time = 0


    for r in range(len(grid)):
        for c in range(len(grid[0])):
            if grid[r][c] == 1:
                fresh += 1
            if grid[r][c] == 2:
                queue.append((r, c))


    directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]
    while fresh > 0 and queue:
        length = len(queue)
        for _ in range(length):
            r, c = queue.popleft()


            for dr, dc in directions:
                row, col = r + dr, c + dc
                if (0 <= row < len(grid)
                    and 0 <= col < len(grid[0])
                    and grid[row][col] == 1
                ):
                    grid[row][col] = 2
                    queue.append((row, col))
                    fresh -= 1
        time += 1


    return time if fresh == 0 else -1

Time complexity: O(m * n) Space complexity: O(m * n)

Breadth First Search (No Queue)

def oranges_rotting_no_queue(grid: list[list[int]]) -> int:
    rows, cols = len(grid), len(grid[0])
    fresh = 0
    time = 0


    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                fresh += 1


    directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]


    while fresh > 0:
        flag = False
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 2:
                    for dr, dc in directions:
                        row, col = r + dr, c + dc
                        if (0 <= row < rows and
                            0 <= col < cols and
                            grid[row][col] == 1):
                            grid[row][col] = 3
                            fresh -= 1
                            flag = True


        if not flag:
            return -1


        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 3:
                    grid[r][c] = 2


        time += 1


    return time

Time complexity: O((m * n) ^ 2) Space complexity: O(1)