Rotting Oranges

GraphsBFS

30 min

Problem Statement

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.

Example

Example 1:

Output: 2

Solution

This problem is a perfect use case for a Breadth-First Search (BFS). Since the rotting process happens in layers (or minutes), BFS is ideal because it explores the graph level by level. Each level of the BFS will correspond to one minute passing.

We can start by finding all initially rotten oranges and adding them to a queue. We also count the number of fresh oranges. Then, we perform a multi-source BFS, where each "level" of the search represents one minute.

Algorithm Steps (BFS)

Scan the grid to find all initial rotten oranges and add their coordinates to a queue. Also, count the number of fresh oranges.
Initialize `minutes` to 0.
While the queue is not empty and there are still fresh oranges:
Process all oranges currently in the queue (one full level/minute).
For each rotten orange dequeued, check its 4-directional neighbors.
If a neighbor is a fresh orange, make it rotten, decrement the `freshOranges` count, and add it to the queue.
After processing a full level, if any oranges were rotted, increment `minutes`.
After the loop, if `freshOranges` is 0, return `minutes`. Otherwise, return -1.

Rotting Oranges (BFS)

Minutes Elapsed: 0

Progress1 / 1

Ready to start.

Rotting Oranges (BFS)


from collections import deque

class Solution:
    def orangesRotting(self, grid: list[list[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        fresh_oranges = 0
        queue = deque()

        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 1:
                    fresh_oranges += 1
                elif grid[r][c] == 2:
                    queue.append((r, c))

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

        while queue and fresh_oranges > 0:
            level_size = len(queue)
            for _ in range(level_size):
                r, c = queue.popleft()
                for dr, dc in directions:
                    row, col = r + dr, c + dc
                    if (row in range(rows) and
                        col in range(cols) and
                        grid[row][col] == 1):
                        grid[row][col] = 2
                        fresh_oranges -= 1
                        queue.append((row, col))
            minutes += 1
            
        return minutes if fresh_oranges == 0 else -1