The Infection Spread

A hard Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
hard
Seniority
L5
Asked in
Sigmoid

Problem

You're modeling spoilage in a produce crate held as a 2D grid, where each cell is empty (0), holds a fresh item (1), or holds an already-spoiled one (2). Every minute, spoilage spreads from each spoiled cell to the fresh items directly above, below, left of, and right of it, all at once. Return how many minutes pass until nothing fresh is left, -1 if some fresh item is walled off and can never spoil, or 0 when there was nothing fresh to begin with.

It starts with one, and then it spreads.

Example 1

Input:

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

Output:

4

Example 2

Input:

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

Output:

-1

Worked solution and explanation

What this really is

Underneath the produce metaphor this is a level-synchronized flood fill from many sources at once. The skill it probes: can you advance every wavefront in lockstep so that one full wave equals exactly one minute? A single-source walk or a plain grid rescan looks tempting, but the sources all spread at the same instant, so you have to expand all of them together or your minute count drifts. The trap is counting a minute per cell you process, or letting a cell that just rotted infect its neighbors in the same minute. Do either and you overcount the clock, or you miss the walled-off cell and return a number where the answer is -1.

The three things that trip people

Building it

Step 1: Scan once, seed every source

Walk the whole grid a single time. Push every already-rotten cell into the frontier together (that is what makes it multi-source) and tally the fresh cells. If nothing is fresh, the clock never starts, so return 0 right here.

Step 2: Peel one layer per minute

Drain the entire current layer before the clock advances: pop each cell off the frontier, rot its four straight neighbors that are still fresh, drop the fresh tally, and stage those newly rotten cells as the next layer. Bump the minute count once per layer, never once per cell.

Step 3: Decide between a number and -1

Stop when the frontier drains or the fresh tally reaches zero. If any fresh cell is still left, it was walled off and can never rot, so return -1; otherwise the minute count is the answer.

The solution

Multi-source layer-by-layer spread
def oranges_rotting(grid):
    rows = len(grid)
    cols = len(grid[0])
    fresh = 0
    frontier = []
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                frontier.append((r, c))
            elif grid[r][c] == 1:
                fresh += 1
    if fresh == 0:
        return 0
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    minutes = 0
    while frontier and fresh > 0:
        next_frontier = []
        while frontier:
            r, c = frontier.pop()
            for dr, dc in directions:
                nr = r + dr
                nc = c + dc
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                    grid[nr][nc] = 2
                    fresh -= 1
                    next_frontier.append((nr, nc))
        minutes += 1
        frontier = next_frontier
    if fresh > 0:
        return -1
    return minutes

Each layer is a plain list used as a stack: we pop cells off the current layer and append newly rotted cells to the next one, and the fresh tally gates the loop so no extra minute is counted.

Common follow-up questions