Rotting Oranges

+10

You get a grid as a list of rows of equal length. Each cell is 0 (empty), 1 (a fresh orange) or 2 (a rotten orange). Every minute, each fresh orange that shares a side with a rotten orange, up, down, left or right, turns rotten. Return the number of minutes until no fresh orange is left, or -1 if some fresh orange can never rot. A grid with no fresh oranges at the start needs 0 minutes.

Function

orangesRotting(grid: integer-2d-array) → integer

gridinteger-2d-array: the grid, one list of 0, 1 and 2 per row
Returnsinteger: the minutes until no orange is fresh, or -1 if that never happens

Constraints

1 ≤ grid.length ≤ 150
1 ≤ grid[i].length ≤ 150
Every row has the same length.
Each grid[i][j] is 0, 1 or 2.

Examples

Input: grid = [[2, 1, 1, 0], [0, 1, 0, 1], [1, 1, 1, 1]]
Output: 6
Explanation: Writing cells as (row, column), the rot leaves (0,0) and follows the only path: (0,1) at minute 1, (0,2) and (1,1) at minute 2, (2,1) at minute 3, (2,0) and (2,2) at minute 4, (2,3) at minute 5. The orange at (1,3) only touches (2,3), so it is the last to go, at minute 6.

+21 hidden tests on Submit

Follow-up

Suppose each fresh orange needs its own number of minutes to rot once a neighbour is rotten. How would you find the finishing time then?

Solution

The rot starts from every rotten orange at once and moves one cell a minute, so the answer is a distance: how many steps the farthest fresh orange is from its nearest rotten orange. Breadth first search measures exactly that, if you put every rotten orange in the queue before you start and work through the queue one level, one minute, at a time.

Simulate minute by minute

Correct, but does not finish on the largest tests

Intuition

Do what the story says. Each minute, scan the whole grid and list every fresh orange that touches a rotten one. Then rot all of them, add one to the clock, and scan again. Stop when a scan finds nothing to rot. If a fresh orange is still in the grid at that point, the rot can never reach it: return -1.

List first, rot after. If you rot an orange in the middle of a scan, a cell later in the same scan sees it as rotten and rots too, so the rot races several cells in one minute and the clock comes out too low.

This is correct, but each minute costs a full scan of rows × cols cells, and the number of minutes can come close to the number of cells. On a 150 × 150 grid whose fresh oranges form one winding path with the rot at its head, the rot needs 11,324 minutes: 11,324 scans of 22,500 cells, about 2.5 × 10^8 cell checks, nearly all of them on cells that cannot change.

Algorithm

Set minutes to 0.
Scan the grid and list every fresh orange that has a rotten neighbour.
If the list is empty, stop. Otherwise turn every listed orange rotten, add 1 to minutes, and scan again.
Return -1 if a fresh orange is left, else minutes.

def orangesRotting(grid):
    rows, cols = len(grid), len(grid[0])
    minutes = 0
    while True:
        # Find every fresh orange that touches a rotten one right now.
        to_rot = []
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] != 1:
                    continue
                for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 2:
                        to_rot.append((r, c))
                        break
        if not to_rot:
            break
        # Rot them only after the scan, so the rot moves one step a minute.
        for r, c in to_rot:
            grid[r][c] = 2
        minutes += 1
    for row in grid:
        if 1 in row:
            return -1
    return minutes

Multi-source BFS by levels

Intuition

The scan wastes its time on cells far from the action. The only oranges that can rot at minute t+1 are fresh neighbours of the oranges that rotted at minute t. So keep exactly those in a queue: the frontier of the rot.

Start the queue with every orange that is rotten at minute 0, all of them together. That is the multi-source part. A fresh orange rots at the minute equal to its distance from the nearest rotten orange, and a breadth first search seeded with all the sources reaches each cell first from whichever source is closest. One search does the work of one search per source plus taking the minimum.

Then work in levels. At the start of a minute the queue holds k oranges, the ones that rotted last minute. Take exactly k from the front; for each, rot its fresh neighbours and add them to the back. When the k are done, one minute has passed and the queue holds the next frontier. In the first example the levels are {(0,0)}, {(0,1)}, {(0,2), (1,1)}, {(2,1)}, {(2,0), (2,2)}, {(2,3)}, {(1,3)}: six steps after the start, so six minutes.

Count the fresh oranges once at the start and lower the count each time one rots. Stop as soon as it reaches 0, or the last level would add a minute in which nothing rots, and return -1 if the queue empties while the count is above 0. Each cell enters the queue at most once and checks four neighbours, so the work is O(rows × cols).

Algorithm

Put every rotten orange in a queue and count the fresh ones.
Set minutes to 0. While the queue is not empty and fresh oranges remain, add 1 to minutes and note the queue's size k.
Take k oranges from the front. For each fresh neighbour inside the grid, mark it rotten, lower the fresh count, and add it to the back.
When the loop ends, return minutes if the fresh count is 0, else -1.

from collections import deque


def orangesRotting(grid):
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0
    # Every orange that is rotten at minute 0 starts in the queue.
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c))
            elif grid[r][c] == 1:
                fresh += 1
    minutes = 0
    while queue and fresh > 0:
        minutes += 1
        # The queue holds exactly the oranges that went rotten last minute.
        # Rot their fresh neighbours; those become the next minute's queue.
        for _ in range(len(queue)):
            r, c = queue.popleft()
            for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                    grid[nr][nc] = 2
                    fresh -= 1
                    queue.append((nr, nc))
    return minutes if fresh == 0 else -1

Pitfalls and edge cases

Most wrong answers here are one minute off, or come from starting the search in the wrong place.

Counting a minute for the last level. If the loop runs until the queue is empty, its final pass rots nothing and still adds 1. Stop as soon as no fresh orange is left.
Searching from each rotten orange in turn. The first search claims every orange it reaches with its own clock, so two sources that should meet in the middle give a time that is too high: [[2, 1, 1, 1, 1, 1, 1, 2]] takes 3 minutes, not 6.
Rotting oranges during the scan in the minute by minute version. A cell later in the same scan then sees them as rotten, and the rot crosses several cells in one minute.
Returning -1 because there is no rotten orange. With no fresh orange either, nothing has to happen: [[0]] returns 0. Only fresh oranges that never rot make the answer -1.
Marking an orange rotten when you take it out of the queue instead of when you put it in. An orange next to two rotten ones then goes in twice and the fresh count drops below zero.
Depth first search. It follows one path as deep as it goes, so the first time it reaches an orange says nothing about the minute that orange rots.

Frequently asked questions4

What is the time complexity of Rotting Oranges?

O(rows × cols) with breadth first search. The first scan looks at every cell once, and each orange enters the queue at most once and checks four neighbours. The queue takes O(rows × cols) space in the worst case, a grid full of rotten oranges.

Why use BFS and not DFS for Rotting Oranges?

Breadth first search visits cells in order of their distance from the start, and distance is time here: level k of the search is exactly the set of oranges that rot at minute k. Depth first search can reach a cell along a long detour before it finds the short route, so it would have to revisit cells every time it finds a shorter one.

What is multi-source BFS?

A breadth first search that starts with several cells in the queue at distance 0 instead of one. In a single pass it gives every cell its distance to the nearest source, the same result as one search per source with the minimum taken, for the cost of one search. Any "distance to the nearest X" question on a grid uses it.

Can you solve Rotting Oranges without changing the grid?

Yes. Keep a separate visited array and check it instead of writing 2 into the grid. That costs O(rows × cols) extra memory, which the queue can need anyway. In languages that pass the grid by reference, writing into it also changes the caller's grid, which an interviewer may ask you about.

Python

def orangesRotting(grid):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

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

Expected