Katkat
Back

Compute infection spread time

OpenAISoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to model a spreading process on a 2D grid using a multi-source Breadth-First Search (BFS) to determine the time required for a state to propagate across the entire space.

Infection Spread Simulation

You are given an m x n grid where each cell is either empty (represented by 0) or contains an infected entity (represented by 1). Each hour, any empty cell that is adjacent (horizontally or vertically) to at least one infected cell becomes infected.

Write a function minTimeToInfect(grid) that returns the number of hours required for every cell in the grid to become infected. If it is impossible for all cells to become infected (e.g., they are blocked or isolated in a way that prevents propagation), return -1.

Function Signature

def minTimeToInfect(grid: List[List[int]]) -> int:

Constraints

  • m == grid.length, n == grid[0].length
  • 1 <= m, n <= 100
  • grid[i][j] is either 0 or 1.

Examples

Example 1: Input: grid = [[1, 0], [0, 0]] Output: 2 Explanation: Hour 1: [[1, 1], [1, 0]]. Hour 2: [[1, 1], [1, 1]].

Example 2: Input: grid = [[1, 0, 0], [0, 0, 0], [0, 0, 1]] Output: 2 Explanation: Both infected cells spread simultaneously.

Edge Cases

  • Grids already fully infected.
  • Grids with no infected cells initially.
  • Unreachable empty cells.

Hints

Hint 1

Treat the initial infected cells as multiple starting points for a traversal algorithm.

Hint 2

A Breadth-First Search (BFS) approach is ideal here because the infection spreads layer by layer, representing a constant time step per expansion.

Hint 3

Keep track of the number of empty cells and decrement this count as you infect them to determine when the simulation is complete or if unreachable cells remain.

Follow-up questions

  • How would your approach change if infected cells only spread to empty cells but could not spread through obstacles (e.g., represented by '-1')?
  • If infection had a 'strength' value that decayed over distance, how would you modify the simulation?
  • What is the time and space complexity of your solution in terms of grid dimensions M and N?