PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

Quick Overview

This question evaluates a candidate's ability to apply multi-source breadth-first search to simulate simultaneous state propagation across a 2D grid. It tests graph traversal, reachability reasoning, and time-complexity awareness — core competencies commonly assessed in coding interviews for software engineering roles. The follow-up variant on 8-directional spread further probes adaptability and spatial reasoning within the same algorithmic framework.

  • hard
  • Airbnb
  • Coding & Algorithms
  • Software Engineer

Infection Spread Time on a Grid

Company: Airbnb

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

# Infection Spread Time on a Grid You are given an `m x n` grid where every cell holds one of three integer values: - `0` — an empty cell that can never be infected. - `1` — a healthy (susceptible) cell. - `2` — an infected cell. Every minute, any healthy cell (`1`) that is **4-directionally adjacent** (up, down, left, right) to an infected cell (`2`) becomes infected. Infection spreads simultaneously: all cells that can be infected in a given minute become infected at the same time, then the next minute begins. Return the **minimum number of minutes** that must elapse until no healthy cell remains. If it is impossible for every healthy cell to become infected (some healthy cell is unreachable from any initially infected cell), return `-1`. If there are no healthy cells to begin with, the answer is `0`. ### Example ``` Input: 2 1 1 1 1 0 0 1 1 Output: 4 ``` The single initially infected cell at the top-left spreads outward; the bottom-right healthy cell is the last to be infected, at minute 4. ### Follow-up After solving the 4-directional version, extend your solution so that infection **also spreads diagonally** — i.e. each cell has up to **8 neighbors** (the four orthogonal neighbors plus the four diagonal neighbors). Describe (and, if asked, implement) what changes in your approach and recompute the minimum minutes for the same input under 8-directional spread. ### Constraints & Assumptions - `1 <= m, n <= 300`. - `grid[i][j]` is one of `0`, `1`, or `2`. - There may be zero, one, or many initially infected cells. - The grid may contain empty cells (`0`) that block infection (infection does not pass through them, and they are never counted as healthy). - Time and memory should be efficient enough for the maximum grid size; an $O(m \cdot n)$ solution is expected. ### Required Output - Return a single integer: the minimum number of minutes until no healthy cell remains, or `-1` if some healthy cell can never be infected.

Quick Answer: This question evaluates a candidate's ability to apply multi-source breadth-first search to simulate simultaneous state propagation across a 2D grid. It tests graph traversal, reachability reasoning, and time-complexity awareness — core competencies commonly assessed in coding interviews for software engineering roles. The follow-up variant on 8-directional spread further probes adaptability and spatial reasoning within the same algorithmic framework.

Infection Spread Time on a Grid (4-Directional)

You are given an `m x n` grid where every cell holds one of three integer values: - `0` — an empty cell that can never be infected. - `1` — a healthy (susceptible) cell. - `2` — an infected cell. Every minute, any healthy cell (`1`) that is **4-directionally adjacent** (up, down, left, right) to an infected cell (`2`) becomes infected. Infection spreads simultaneously: all cells that can be infected in a given minute become infected at the same time, then the next minute begins. Return the **minimum number of minutes** that must elapse until no healthy cell remains. If it is impossible for every healthy cell to become infected (some healthy cell is unreachable from any initially infected cell), return `-1`. If there are no healthy cells to begin with, return `0`. This is a multi-source BFS: enqueue every initially infected cell at level 0, then expand outward one minute (one BFS layer) at a time. The answer is the number of layers needed to consume every healthy cell; if any healthy cell remains after the queue drains, return `-1`.

Constraints

  • 1 <= m, n <= 300
  • grid[i][j] is one of 0, 1, or 2
  • There may be zero, one, or many initially infected cells
  • Empty cells (0) block infection and are never counted as healthy
  • An O(m * n) solution is expected

Examples

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

Expected Output: 4

Explanation: Single infected cell at top-left; the bottom-right healthy cell is last, infected at minute 4.

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

Expected Output: -1

Explanation: The healthy cell at (2,0) is walled off by 0s and never gets infected, so return -1.

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

Expected Output: 0

Explanation: No healthy cells to infect, so 0 minutes.

Input: ([[1]],)

Expected Output: -1

Explanation: A lone healthy cell with no infected source can never be infected.

Input: ([[2]],)

Expected Output: 0

Explanation: Already fully infected, no healthy cells remain.

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

Expected Output: 0

Explanation: Only empty cells; nothing to infect.

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

Expected Output: 3

Explanation: Two infected ends close in on the middle simultaneously; the meeting cells are reached at minute 3.

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

Expected Output: 4

Explanation: Spread goes down column then around the 0 wall; the cell at (3,0) is last, at minute 4.

Hints

  1. Use multi-source BFS: seed the queue with EVERY initially infected cell at once, not one at a time.
  2. Process the queue one BFS layer per minute. Counting layers (not total nodes) gives you the elapsed minutes.
  3. Track the number of remaining healthy cells. If it's already 0, the answer is 0; if it's still > 0 after the queue drains, return -1.
  4. Empty cells (0) are walls — never spread into them and never count them as healthy.

Infection Spread Time on a Grid (8-Directional Follow-up)

Follow-up to the 4-directional version. Same grid encoding: - `0` — an empty cell that can never be infected. - `1` — a healthy (susceptible) cell. - `2` — an infected cell. Now infection **also spreads diagonally**: each cell has up to **8 neighbors** — the four orthogonal neighbors (up, down, left, right) PLUS the four diagonal neighbors. Every minute, any healthy cell adjacent (in any of the 8 directions) to an infected cell becomes infected, simultaneously. Return the **minimum number of minutes** until no healthy cell remains, or `-1` if some healthy cell can never be infected. Return `0` if there are no healthy cells to begin with. The approach is identical to the 4-directional case — multi-source BFS — and the ONLY change is the neighbor direction set: replace the 4 orthogonal offsets with all 8 offsets. Because diagonal moves are allowed, infection can flow around some 0 walls that would block the 4-directional version, so the same input often finishes in fewer minutes.

Constraints

  • 1 <= m, n <= 300
  • grid[i][j] is one of 0, 1, or 2
  • Infection spreads to all 8 neighbors (4 orthogonal + 4 diagonal)
  • Empty cells (0) block infection and are never counted as healthy
  • An O(m * n) solution is expected

Examples

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

Expected Output: 2

Explanation: With diagonals, (0,0) reaches (1,1) at minute 1, and (1,1) reaches the bottom-right via a diagonal at minute 2 — faster than the 4-directional answer of 4.

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

Expected Output: 2

Explanation: Diagonal moves let infection reach (2,0) and (2,2) (walled off in the 4-dir version), finishing at minute 2.

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

Expected Output: 0

Explanation: No healthy cells.

Input: ([[1]],)

Expected Output: -1

Explanation: Lone healthy cell, no source.

Input: ([[2]],)

Expected Output: 0

Explanation: No healthy cells.

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

Expected Output: 0

Explanation: Only empty cells.

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

Expected Output: -1

Explanation: The healthy cell is separated by a run of 0s with no diagonal bypass on a single row, so it's unreachable.

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

Expected Output: 2

Explanation: From the corner, minute 1 covers the 3 nearest cells (including diagonal (1,1)), minute 2 covers the rest.

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

Expected Output: 1

Explanation: The center infects all 8 surrounding cells in a single minute.

Hints

  1. The algorithm is unchanged from the 4-directional version — only the direction list grows from 4 offsets to all 8.
  2. Diagonal offsets are (-1,-1), (-1,1), (1,-1), (1,1); add these to the orthogonal four.
  3. Because diagonals let infection slip past some 0 walls, the same grid can finish faster than under 4-directional spread.
  4. A healthy cell still returns -1 if NO infected cell can reach it via any 8-directional path through non-empty cells.
Last updated: Jun 24, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,000+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Count Candies from Unlockable Boxes - Airbnb (medium)
  • Find Optimal Property Combination - Airbnb (medium)
  • Determine Exact Layover Booking - Airbnb (medium)
  • Solve Linked-List and Iterator Problems - Airbnb
  • Implement Text Layout and Query Parsing - Airbnb (easy)