Matrix Infection

Determine the minimum time for a digital virus to spread across a network represented as a grid. This problem tests graph traversal and optimization skills crucial for real-world network analysis.

graphbfsmatrixbreadth-first searchgrid traversal

Problem Statement

You are given a rectangular grid representing a computer network. Each cell in the grid can have one of three states: 0 (uninfected), 1 (healthy), or 2 (infected). Every minute, each infected computer (marked as 2) spreads the virus to its directly adjacent (up, down, left, right) healthy neighbors (marked as 1). Your task is to calculate the minimum number of minutes required for all healthy computers in the network to become infected. If it's impossible for the virus to reach all healthy computers, return -1.

Example 1

Input: grid = [[1, 1, 1, 0], [1, 0, 2, 1], [1, 1, 1, 0]]

Output: 2

Initially, one computer is infected. After one minute, its neighbors become infected. After two minutes, all reachable healthy computers are infected.

Example 2

Input: grid = [[1, 1, 1], [1, 0, 1], [1, 1, 0]]

Output: -1

There are no initially infected computers and some healthy computers remain isolated, so it's impossible for the virus to spread to all healthy computers.

Constraints

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

Brute Force Approach

The brute force approach simulates the virus spread minute by minute. Imagine manually checking each cell in the grid every minute to see if it's infected based on its neighbors from the previous minute. This involves iterating through the entire grid repeatedly until no more healthy computers are infected, or a maximum time limit is reached. This is inefficient because you are re-checking previously infected cells.

TimeO(m*n*t)

SpaceO(m*n)

Ready to practice?

Work through this problem with AI coaching and get real-time feedback

Practice This Problem