Aphids in the Greenhouse
A greenhouse keeps its seedlings in trays laid out on a grid. Each spot is empty (0), holds a healthy plant (1) or holds a plant with aphids (2). Aphids crawl, they do not fly: each day, every healthy plant directly above, below, left or right of an infested plant becomes infested too. Empty spots stop them.
The grower wants to know the worst case if nobody acts. How many days until every plant is infested? Or are some plants safe forever, cut off by empty spots?
Your task
Write daysUntilAllInfested(trays). Return the number of days until no healthy plant is left. Return 0 if there are no healthy plants at the start, and -1 if some healthy plant can never be reached.
All infested plants spread at the same time. A plant infested on day d starts spreading on day d + 1.
daysUntilAllInfested(trays: int[][]) → int
Examples
trays = [[2, 1, 1], [1, 1, 0], [0, 1, 1]]
4
Day 1: (0,1) and (1,0). Day 2: (0,2) and (1,1). Day 3: (2,1). Day 4: (2,2). Every plant is infested after 4 days.
trays = [[2, 1, 0, 1], [1, 1, 0, 2]]
2
There are two infested plants, and they spread at the same time. The left one reaches (0,1) and (1,0) on day 1 and (1,1) on day 2. The right one reaches (0,3) on day 1. The answer is 2, not the 3 or more you would get by handling one source after the other.
trays = [[2, 0, 1]]
-1
The empty spot cuts off the plant on the right, so it is never infested: -1.
Constraints
- 1 ≤ rows, cols ≤ 20
- trays[r][c] is 0, 1 or 2
Start with brute force
Simulate day by day: copy the grid, infect every healthy plant next to an infested one, and repeat until a day changes nothing. Then check whether any healthy plant is left.
Each day scans the whole grid, and a long winding row of plants can take about one day per plant. On a 20 × 20 grid that is up to about 200 days × 400 spots. Breadth-first search reaches each plant once instead of rescanning the grid every day.
Hints
0 of 4 shown- Hint 1
In the second example, label every plant with the day it gets infested. Which plants get day 1? Does it matter which infested plant they caught it from?
- Hint 2
A plant's day is its step distance to the nearest infested plant. So you want shortest distances from a whole set of starting points at once.
- Hint 3
Breadth-first search from one start finds step distances in rings. What happens if, at the very beginning, you put every infested plant in the queue at distance 0?
- Hint 4
Queue every 2 at day 0 and count the healthy plants. Run breadth-first search: each time you infect a healthy neighbor, record its day as the current day + 1, subtract one from the healthy count and queue it. At the end, return -1 if the healthy count is not 0, otherwise the largest day you recorded (0 if none).
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
Each plant is infested on the day equal to its step distance from the nearest infested plant. That is breadth-first search, but with many starting points. Put them all in the first ring together and the rings grow from every source at once, exactly like the aphids.
Trace the second example, [[2,1,0,1],[1,1,0,2]]. Healthy plants: 4. Day 0 ring: (0,0) and (1,3).
- Day 1. From (0,0): (0,1) and (1,0). From (1,3): (0,3). Healthy left: 1.
- Day 2. From the day-1 ring, (1,1) is reached (from (0,1) or (1,0), whichever comes first). Healthy left: 0. Stop.
Answer: 2. The loop stops as soon as no healthy plant is left, so it never counts an extra empty day at the end. That off-by-one is the most common bug here: if you keep looping until the queue is empty, the last ring still counts a day even though it infects nothing.
Two edge cases fall out of the healthy counter. No healthy plants at the start gives 0 without entering the loop. Healthy plants that no ring can reach leave the counter above 0, so the answer is -1.
function daysUntilAllInfested(trays) {
const rows = trays.length, cols = trays[0].length;
const grid = trays.map(row => row.slice());
let queue = [];
let healthy = 0;
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (grid[r][c] === 2) queue.push([r, c]); // every source starts at day 0
else if (grid[r][c] === 1) healthy++;
}
}
let days = 0;
while (queue.length > 0 && healthy > 0) {
const next = []; // plants infested tomorrow
for (const [r, c] of queue) {
for (const [nr, nc] of [[r + 1, c], [r - 1, c], [r, c + 1], [r, c - 1]]) {
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
if (grid[nr][nc] !== 1) continue;
grid[nr][nc] = 2;
healthy--;
next.push([nr, nc]);
}
}
queue = next;
days++;
}
return healthy === 0 ? days : -1;
}def days_until_all_infested(trays):
rows, cols = len(trays), len(trays[0])
grid = [row[:] for row in trays]
queue = []
healthy = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == 2:
queue.append((r, c)) # every source starts at day 0
elif grid[r][c] == 1:
healthy += 1
days = 0
while queue and healthy > 0:
nxt = [] # plants infested tomorrow
for r, c in queue:
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
healthy -= 1
nxt.append((nr, nc))
queue = nxt
days += 1
return days if healthy == 0 else -1Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.