How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Uber.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Uber during technical interviews.

Compute time for virus to infect grid

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given an `m x n` grid representing the state of individuals in a lab. - `0` = empty cell (no one) - `1` = healthy individual - `2` = infected individual Every minute, any **healthy** individual (`1`) that is **4-directionally adjacent** (up/down/left/right) to an infected individual (`2`) becomes infected. Return the **minimum number of minutes** needed until **no healthy individuals remain**. If it is **impossible** to infect all healthy individuals, return `-1`. If there are **no healthy individuals initially**, return `0`. ### Input - A 2D integer array `grid` of size `m x n`. ### Output - An integer: the minimum minutes to infect everyone, or `-1` if impossible. ### Constraints - `1 ≤ m, n ≤ 200` - `grid[i][j] ∈ {0,1,2}` ### Notes (as in the interview) - You may be asked to write your own test cases (including edge cases) to validate your solution.

Quick Answer: This question evaluates a candidate's ability to reason about grid-based state propagation, algorithmic problem solving, and performance considerations when managing multi-step updates across a 2D matrix.

You are given an m x n grid representing the state of individuals in a lab. A cell with 0 is empty, 1 contains a healthy individual, and 2 contains an infected individual. Every minute, any healthy individual that is 4-directionally adjacent to an infected individual becomes infected. Return the minimum number of minutes needed until no healthy individuals remain. If it is impossible to infect all healthy individuals, return -1. If there are no healthy individuals initially, return 0.

Constraints

1 <= m, n <= 200
grid[i][j] is one of {0, 1, 2}

Examples

Input: ([[2,1,1],[1,1,0],[0,1,1]],)

Expected Output: 4

Explanation: The infection spreads outward from the top-left cell. The last healthy individual becomes infected after 4 minutes.

Input: ([[2,1,1],[0,1,1],[1,0,1]],)

Expected Output: -1

Explanation: The healthy individual at the bottom-left is separated by empty cells and can never be infected.

Input: ([[0,2],[0,0]],)

Expected Output: 0

Explanation: There are no healthy individuals initially, so no time is needed.

Input: ([[1]],)

Expected Output: -1

Explanation: There is one healthy individual but no infected individual to start the spread.

Input: ([[2,1,1],[1,1,1],[1,1,2]],)

Expected Output: 2

Explanation: The infection spreads simultaneously from both infected corners, so all healthy individuals are infected in 2 minutes.

Input: ([[2,1,1,1,1]],)

Expected Output: 4

Explanation: In a single row, the infection moves one cell to the right each minute.

Hints

All initially infected individuals should start spreading the infection at the same time.
Think of each minute as one level of a breadth-first search starting from all infected cells.

Quick Overview

This question evaluates a candidate's ability to reason about grid-based state propagation, algorithmic problem solving, and performance considerations when managing multi-step updates across a 2D matrix.