#994

Medium

auto_awesomeArray plus Breadth-First Search

LeetCode Problem Workspace

Rotting Oranges

Given a grid with fresh and rotten oranges, return the minimum time for all oranges to rot or -1 if impossible.

Problem Statement

You are given a grid of size m x n, where each cell can contain a fresh orange (1), a rotten orange (2), or an empty space (0). Every minute, any fresh orange that is adjacent to a rotten orange becomes rotten. You need to determine the minimum number of minutes required for all the fresh oranges to rot, or return -1 if it's impossible for some fresh oranges to rot.

The grid is provided with constraints where the dimensions are small (1 ≤ m, n ≤ 10), making it feasible to use breadth-first search (BFS). This problem combines matrix traversal with BFS to spread the rot through the grid and find the solution efficiently.

Examples

Example 1

Input: grid = [[2,1,1],[1,1,0],[0,1,1]]

Output: 4

Example details omitted.

Example 2

Input: grid = [[2,1,1],[0,1,1],[1,0,1]]

Output: -1

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

Since there are already no fresh oranges at minute 0, the answer is just 0.

Constraints

m == grid.length
n == grid[i].length
1 <= m, n <= 10
grid[i][j] is 0, 1, or 2.

Solution Approach

Breadth-First Search (BFS)

This problem is solved by applying breadth-first search (BFS) starting from all rotten oranges (cells with 2). BFS ensures that we spread the rot level by level, ensuring the shortest time for rot propagation. For each rotten orange, the BFS will visit neighboring cells, turning fresh oranges (1) to rotten (2) and incrementing the time until no fresh oranges remain or some oranges are unreachable.

Multi-Source BFS

To optimize the BFS, we treat all initially rotten oranges as the starting points, effectively using multi-source BFS. This allows the rotting process to propagate simultaneously from multiple points, reducing the time complexity by exploring all directions at once.

Edge Case Handling

The algorithm should account for edge cases such as grids with no fresh oranges, grids where some fresh oranges are isolated from rotten ones, or grids with empty spaces (0). It should also handle the case where no fresh oranges exist at the start (return 0 minutes) or when all fresh oranges are unreachable (return -1).

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on the grid size and BFS traversal. In the worst case, every cell is visited once, making the time complexity O(m * n), where m is the number of rows and n is the number of columns. The space complexity is also O(m * n) due to the space required to store the grid and BFS queue.

What Interviewers Usually Probe

Can the candidate apply BFS for grid traversal?
Does the candidate handle edge cases like isolated fresh oranges?
Does the candidate consider the multi-source BFS approach for efficiency?

Common Pitfalls or Variants

Common pitfalls

Not using BFS correctly and attempting DFS, leading to incorrect time calculations.
Failing to account for edge cases such as no fresh oranges or isolated cells.
Overcomplicating the algorithm with unnecessary data structures or excessive loops.

Follow-up variants

Grid with no empty cells (0) but only fresh (1) and rotten (2) oranges.
Larger grids requiring more optimized BFS or additional pruning techniques.
Time complexity analysis with a focus on different grid configurations or larger problem constraints.

FAQ

How does breadth-first search solve the Rotting Oranges problem?

BFS spreads the rot level by level, ensuring the minimum time for all fresh oranges to rot. It starts from all rotten oranges and propagates to adjacent fresh ones.

What happens if some oranges can't rot in Rotting Oranges?

If a fresh orange is unreachable by any rotten orange, the answer will be -1, as it's impossible for all fresh oranges to rot.

How does multi-source BFS improve the solution?

Multi-source BFS allows simultaneous propagation of rot from multiple rotten oranges, reducing the overall time required to spread the rot.

What is the time complexity of this solution?

The time complexity is O(m * n), where m and n are the dimensions of the grid, as every cell is visited once during BFS.

What are common edge cases to consider in this problem?

Common edge cases include grids with no fresh oranges, grids with no rotten oranges, and grids where some fresh oranges are isolated and cannot rot.

terminal

Solution

Solution 1: BFS

First, we traverse the entire grid once, count the number of fresh oranges, denoted as $\textit{cnt}$, and add the coordinates of all rotten oranges to the queue $q$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        cnt = 0
        q = deque()
        for i, row in enumerate(grid):
            for j, x in enumerate(row):
                if x == 2:
                    q.append((i, j))
                elif x == 1:
                    cnt += 1
        ans = 0
        dirs = (-1, 0, 1, 0, -1)
        while q and cnt:
            ans += 1
            for _ in range(len(q)):
                i, j = q.popleft()
                for a, b in pairwise(dirs):
                    x, y = i + a, j + b
                    if 0 <= x < m and 0 <= y < n and grid[x][y] == 1:
                        grid[x][y] = 2
                        q.append((x, y))
                        cnt -= 1
                        if cnt == 0:
                            return ans
        return -1 if cnt else 0

Continue Practicing

#1020 number of enclaves #959 regions cut by slashes #1034 coloring a border