Spreading Mold
MediumGraphs
Problem
A warehouse shelf is modelled as a grid of slots: 0 is an empty slot, 1 holds a fresh loaf and 2 holds a moldy loaf.
Every minute, mold spreads from each moldy loaf to every fresh loaf directly above, below, left or right of it. Return the number of minutes until no fresh loaf remains. If some fresh loaf can never be reached, return -1. If there are no fresh loaves to begin with, return 0.
Example 1
- Input:
- grid = [[2,1,1],[1,1,0],[0,1,1]]
- Output:
- 4
The loaf at the bottom-right corner is the last to go moldy, four minutes in.
Example 2
- Input:
- grid = [[2,1,1],[0,1,1],[1,0,1]]
- Output:
- -1
The loaf at (2,0) is surrounded by empty slots and the edge, so mold never reaches it.
Example 3
- Input:
- grid = [[0,2]]
- Output:
- 0
Constraints
- 1 ≤ rows, cols ≤ 1000
- rows · cols ≤ 10^5
- grid[r][c] is 0, 1 or 2
Hint
Show the first hint
The answer is the time at which the last fresh loaf is reached. What does 'first reached at minute t' sound like?
Walkthrough
How to approach it
01Clarify before coding
- Does mold spread diagonally? No, only to the four orthogonal neighbours.
- Does it spread through empty slots? No, empty slots block it.
- What if there is no fresh loaf? Return 0, even if there is no mold either.
02Brute force
Simulate minute by minute: scan the grid, find fresh loaves next to mold, convert them all at once, repeat until nothing changes.
Cost: Each minute costs O(r · c) and the process can last O(r · c) minutes (a long snake): O((r · c)²).
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.