Katkat
Back

Compute Plant Infection Time

OpenAISoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to model a grid-based propagation process using Breadth-First Search (BFS), specifically handling multi-source initialization and obstacle avoidance.

Problem Statement

You are given an m x n grid representing a greenhouse. Each cell can be one of three types:

  • 0: Empty soil.
  • 1: A healthy plant.
  • 2: An infected plant.

Every day, an infected plant spreads the infection to any adjacent (up, down, left, or right) healthy plants. Return the minimum number of days required for all healthy plants to become infected. If it is impossible for all plants to become infected, return -1.

Function Signature

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

Examples

Example 1: Input: grid = [[2, 1, 1], [1, 1, 0], [0, 1, 1]] Output: 4 Explanation: The infection spreads level by level. By day 4, all reachable plants are infected.

Example 2: Input: grid = [[2, 1, 1], [0, 0, 0], [1, 0, 1]] Output: -1 Explanation: The isolated plants at the bottom cannot be reached by the infection.

Constraints

  • m and n are between 1 and 200.
  • Time complexity should be O(m * n).
  • Space complexity should be O(m * n).

Hints

Hint 1

Identify this as a multi-source shortest path problem on a grid.

Hint 2

Initialize your BFS queue with all cells initially containing an infected plant (value 2).

Hint 3

Track the number of healthy plants remaining; if the count is greater than zero after the BFS completes, return -1.

Follow-up questions

  • How would the logic change if the infection could jump over empty soil tiles to reach a plant two cells away?
  • What if some plants are 'resistant' and take 2 days to become infected once exposed?
  • How would you optimize the solution if the grid size was extremely large (e.g., 100,000 x 100,000) but the number of infected plants was small?