Katkat
Back

Compute time for virus to infect grid

UberSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question tests the ability to model state propagation in a 2D grid using a Breadth-First Search (BFS) approach to determine the minimum time required for a condition to cover all cells.

Problem Statement

You are given an m x n grid where each cell is either 0 (empty), 1 (healthy), or 2 (infected). Every minute, any healthy cell that is adjacent (horizontally or vertically) to an infected cell becomes infected.

Return the minimum number of minutes that must elapse until no healthy cells remain. If it is impossible for all cells to become infected, return -1.

Function Signature

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

Constraints

  • m, n are between 1 and 200.
  • grid[i][j] is 0, 1, or 2.

Examples

Example 1: Input: grid = [[2, 1, 1], [1, 1, 0], [0, 1, 1]] Output: 4 Explanation: The infection spreads level by level. After 4 minutes, all 1s are infected.

Example 2: Input: grid = [[2, 1, 1], [0, 0, 1], [1, 0, 1]] Output: -1 Explanation: The 1 at (2, 0) is isolated by 0s and can never be reached.

Edge Cases

  • Grids with no healthy cells.
  • Grids with no infected cells.
  • Grids that are disconnected due to empty cells (0s).

Hints

Hint 1

Consider this as a multi-source shortest path problem where all initially infected cells start at time zero.

Hint 2

Use a queue to keep track of the coordinates of infected cells and their current infection time, performing a level-order traversal.

Hint 3

After the BFS completes, iterate through the grid one last time to ensure no healthy cells remain unvisited.

Follow-up questions

  • How would you modify your approach if some cells contained 'walls' that blocked the infection instead of empty cells?
  • Can you optimize the space complexity if you are allowed to modify the input grid in-place?
  • How would the solution change if the infection spread speed was not uniform (e.g., some cells take longer to infect than others)?