Katkat
Back

Compute Infection Time in a Grid

OpenAISoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to model state propagation in a 2D grid using Breadth-First Search (BFS) to determine the time required for a dynamic condition to cover all reachable nodes.

Problem: Viral Propagation Time

You are given an m x n grid where each cell is either empty (0), contains an uninfected person (1), or contains an infected person (2). Every minute, any uninfected person who is directly adjacent (up, down, left, or right) to an infected person becomes infected.

Your task is to calculate the minimum number of minutes required until no uninfected people remain in the grid. If it is impossible for every uninfected person to be infected, return -1.

Function Signature

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

Constraints

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

Example 1

Input: grid = [[2, 1, 1], [1, 1, 0], [0, 1, 2]] Output: 4 Explanation: The infection spreads level by level. After 4 minutes, the person at (1, 2) remains uninfected, but wait—if the grid has islands, check if all 1s are reachable.

Example 2

Input: grid = [[2, 1, 1], [0, 0, 0], [1, 0, 1]] Output: -1 Explanation: The 1s at (2, 0) and (2, 2) are isolated by empty space 0 and will never be infected.

Edge Cases

  • Grids with no uninfected people.
  • Grids with no infected people.
  • Completely disconnected uninfected cells.

Hints

Hint 1

Model the problem as a multi-source BFS starting from all initially infected cells (value 2).

Hint 2

Maintain a count of uninfected cells (value 1) initially and decrement this count each time a cell is reached during the BFS.

Hint 3

After the BFS completes, if the count of uninfected cells is greater than zero, return -1; otherwise, return the maximum time recorded during the process.

Follow-up questions

  • How would your approach change if the infection spread speed depended on the type of terrain in the cell?
  • What if the infection has a 'cooldown' period where a cell cannot infect its neighbors until 2 minutes after it becomes infected?
  • How would you optimize the solution for memory if the grid dimensions were 10,000 x 10,000?