A grid has infected cells (I), healthy cells (H), and walls (W). Each minute, every
infected cell infects its healthy 4-directional neighbours. Return the number of minutes
until no healthy cell remains, or -1 if some healthy cell can never be infected.
virusSpread(grid)
Input format: rows separated by |.
IHH|HHH|HHH // → 4
IH|HW // → 1
IW|WH // → -1 (the bottom-right H is walled off)
The spread happens simultaneously from every infected cell at once, minute by minute — not from a single starting point. That's the key detail: this is a multi-source shortest-path problem, many cells racing outward in lockstep.
BFS explores in expanding rings of distance, processing everything at distance d before distance d+1. That's exactly how infection behaves: everything currently infected spreads to immediate neighbors this minute, and only next minute do those newly infected cells spread further. Seeding the BFS queue with all infected cells at once, rather than one, makes BFS process the grid in the same synchronized waves as the infection — one hop away is minute 1, two hops is minute 2.
It doesn't matter which infected source a healthy cell ends up closest to. Seeding with every source at once automatically produces the correct minimum-distance-from-any-source for every cell, since BFS discovers each cell via whichever path reaches it soonest.
Scan the grid once: enqueue every infected cell at minute 0, and count healthy cells up front. Run BFS: for each cell popped, check its four neighbors — still-healthy ones get marked infected, the healthy count decremented, their infection minute recorded as one more than the current cell's, and enqueued. Walls never get infected and block the BFS.
Track the maximum minute seen across all newly infected cells — that's the answer, the moment the last healthy cell converted.
If healthy cells remain after BFS exhausts everything reachable (walled off from every source), no more time will infect them — BFS already explored every reachable path. Check the leftover healthy count: greater than zero means return -1.
Each cell is enqueued and processed at most once, examining four neighbors each — O(rows·cols) time and space, regardless of how many infected sources there are.
def virus_spread(grid):
rows = len(grid)
cols = len(grid[0])
cells = [list(row) for row in grid]
queue = []
healthy = 0
for r in range(rows):
for c in range(cols):
if cells[r][c] == "I":
queue.append((r, c, 0))
elif cells[r][c] == "H":
healthy += 1
dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
minutes = 0
i = 0
while i < len(queue):
r, c, t = queue[i]
i += 1
for dr, dc in dirs:
nr = r + dr
nc = c + dc
if 0 <= nr < rows and 0 <= nc < cols and cells[nr][nc] == "H":
cells[nr][nc] = "I"
healthy -= 1
if t + 1 > minutes:
minutes = t + 1
queue.append((nr, nc, t + 1))
return -1 if healthy > 0 else minutes
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.