Compute Plant Infection Stabilization
Company: OpenAI
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given an `m x n` grid of plants.
Cell types:
- `X`: infected plant
- `.`: healthy plant
- `I`: immune plant (used only in some variants)
Two cells are neighbors if they share an edge or a corner, so each cell has up to 8 neighbors. Time advances in discrete days, and updates are synchronous.
Base infection rule:
- On each day, every plant that is infected at the **start** of the day attempts to infect all infectable neighbors.
- Newly infected plants become active on the **next** day.
- A process is considered stable when no future state changes can occur.
- If the grid is already stable, return `0`.
Implement or design algorithms for the following related variants:
1. **Base spread**
The grid contains only `X` and `.`. Return the number of days required until no more plants can be infected.
2. **Immune plants**
Now the grid may also contain `I`, and immune plants can never be infected. Return the number of days required until the system becomes stable.
3. **Recovery after a fixed delay**
You are also given an integer `R`. Each infected plant remains infected for exactly `R` full days after it becomes infected, then recovers. In this variant, a recovered plant becomes inactive: it no longer infects other plants and cannot be infected again. Return the number of days until no further infection or recovery events can occur.
4. **Death triggered by local crowding**
This variant extends the previous one. In addition to recovery, you are given integers `K` and `D`. If an infected plant has at least `K` infected neighbors at the start of any day, and it has not already been scheduled to die, it is scheduled to die exactly `D` days later. A dead plant is removed permanently and can neither infect nor be infected. If a plant would both recover and die on the same day, death takes precedence. Return the number of days until no further infection, recovery, or death events can occur.
5. **Row or column burning intervention**
At the start of each day, before infection spreads, you may choose at most one entire row or one entire column and burn it. All plants in that row or column die immediately and are removed from the process. Design an algorithm that minimizes the total number of dead plants by the time the system becomes stable.
Your task is to handle these five subproblems under the rules above.
Quick Answer: This question evaluates a candidate's ability to model and simulate discrete-time state transitions on grids, reason about propagation dynamics and event scheduling (infection, recovery, death), and formulate constrained optimization for interventions.
Part 1: Base Spread Stabilization Days
You are given a rectangular grid of plants containing only 'X' and '.'. 'X' is infected and '.' is healthy. Each day, every plant that is infected at the start of the day infects all 8 neighboring healthy plants. Newly infected plants become active on the next day. Return the number of days until no new plants can be infected. If the grid is already stable, return 0.
Constraints
- 0 <= m * n <= 200000
- All rows have the same length
- Each cell is either 'X' or '.'
Examples
Input: []
Expected Output:
Explanation: An empty grid is already stable.
Input: ["X"]
Expected Output:
Explanation: There are no healthy plants to infect.
Input: ["X..", "..."]
Expected Output:
Explanation: The farthest healthy cell is two 8-direction steps away from the source.
Input: ["X.X", "...", "X.X"]
Expected Output:
Explanation: All remaining cells are adjacent to at least one infected corner and become infected after one day.
Hints
- Think of all initially infected cells as starting points in one multi-source BFS.
- The answer is the maximum day on which any healthy cell first becomes infected.
Part 2: Spread Stabilization with Immune Plants
You are given a rectangular grid containing 'X', '.', and 'I'. 'X' is infected, '.' is healthy, and 'I' is immune. Infection spreads synchronously each day from every infected plant to all 8 neighboring healthy plants only. Immune plants can never be infected and do not spread infection. Return the number of days until no future infections can occur. If the grid is already stable, return 0.
Constraints
- 0 <= m * n <= 200000
- All rows have the same length
- Each cell is 'X', '.', or 'I'
Examples
Input: []
Expected Output:
Explanation: An empty grid is already stable.
Input: ["XII", "III", "..."]
Expected Output:
Explanation: The infected plant is completely blocked by immune plants, so nothing changes.
Input: ["X.I", ".I.", "..."]
Expected Output:
Explanation: The immune plants force the infection to take a longer route to the bottom-right corner.
Input: ["...", "..."]
Expected Output:
Explanation: There is no infection source.
Hints
- This is still a shortest-path problem, but immune cells are blocked nodes.
- Run a multi-source BFS from all infected cells and only expand into '.'.
Part 3: Stabilization Time with Fixed Recovery Delay
You are given a grid containing only 'X' and '.', and an integer R. Initially infected cells are active on day 0. Each day, every infected cell infects all 8 neighboring healthy cells, and newly infected cells become active on the next day. Every infected plant stays infected for exactly R active days, then recovers at the end of its R-th active day. Recovered plants are inactive forever and cannot be infected again. Return the number of days until no further infection or recovery events can occur.
Constraints
- 0 <= m * n <= 200000
- 1 <= R <= 1000000000
- All rows have the same length
- Each cell is either 'X' or '.'
Examples
Input: ([], 3)
Expected Output:
Explanation: There are no plants, so there are no future events.
Input: (["..", ".."], 2)
Expected Output:
Explanation: There is no infected source, so the grid is already stable.
Input: (["X"], 1)
Expected Output:
Explanation: The single infected plant recovers after one active day.
Input: (["XX", "XX"], 3)
Expected Output:
Explanation: No new infections occur, but all initially infected plants recover after 3 days.
Input: (["X."], 2)
Expected Output:
Explanation: The neighbor becomes active on day 1 and recovers after its 2 active days, so the process ends after 3 days.
Hints
- Recovery changes when the process ends, but not which cells can eventually be infected when R >= 1.
- Find the latest day any cell becomes active, then account for R more active days before it recovers.
Part 4: Stabilization with Recovery and Crowding Death
You are given a grid of 'X' and '.', plus integers R, K, and D. Initially infected cells are active on day 0. Each day happens in this order: (1) at the start of the day, every currently infected plant with at least K infected neighbors is scheduled to die at the end of day current_day + D if it was not already scheduled; (2) all start-of-day infected plants infect all 8 neighboring healthy plants; (3) deaths scheduled for today happen; (4) recoveries scheduled for today happen, unless the same plant also dies today, in which case death wins; (5) newly infected plants become active next day. Every infected plant stays infected for exactly R active days before recovering. A scheduled death still occurs on its scheduled day even if the plant recovered earlier. Dead plants are removed permanently; recovered plants are inactive forever. Return the number of days until no further infection, recovery, or death events can occur.
Constraints
- 0 <= m * n <= 2500
- 1 <= R <= 50
- 0 <= K <= 8
- 0 <= D <= 50
- All rows have the same length
- Each cell is either 'X' or '.'
Examples
Input: ([], 2, 1, 1)
Expected Output:
Explanation: No plants means no future events.
Input: (["X"], 2, 1, 1)
Expected Output:
Explanation: The plant never reaches the crowding threshold and simply recovers after 2 days.
Input: (["XX", "XX"], 3, 3, 1)
Expected Output:
Explanation: Every infected plant is scheduled to die on day 1, so death happens before recovery.
Input: (["XX", "XX"], 1, 3, 2)
Expected Output:
Explanation: All plants recover on day 0 but still die later on day 2 because their deaths were already scheduled.
Input: (["X..", "..."], 1, 4, 1)
Expected Output:
Explanation: No plant ever has 4 infected neighbors, so this reduces to infection plus recovery timing.
Hints
- Simulate day by day, but keep separate buckets for events that happen at the end of a specific day.
- Use the infected set at the start of the day as a snapshot for both crowding checks and infection spread.
Part 5: Minimize Lost Plants with Row or Column Burning
You are given a grid containing only 'X' and '.'. Infection follows the base rule: after any daily intervention, every infected plant infects all 8 neighboring healthy plants, and infection is permanent. At the start of each day, before infection spreads, you may burn at most one entire row or one entire column. Every plant in that row or column is removed immediately. A plant is counted as lost if it is ever infected or ever burned; a plant burned after already being infected is still counted only once. Return the minimum possible number of lost plants by the time the system becomes stable. This problem asks for an exact algorithm under small constraints.
Constraints
- 0 <= m * n <= 12
- All rows have the same length
- Each cell is either 'X' or '.'
Examples
Input: []
Expected Output:
Explanation: No plants means no losses.
Input: ["X..."]
Expected Output:
Explanation: Burn the first column on day 0 to remove the only infected plant immediately.
Input: ["...", ".X.", "..."]
Expected Output:
Explanation: Burn the middle row or the middle column on day 0 to remove the center source and save the other 6 plants.
Input: ["X..", "X.."]
Expected Output:
Explanation: Burn the first column on day 0 to remove both infection sources at once.
Input: ["XX", "XX"]
Expected Output:
Explanation: All plants are already infected, so all 4 are inevitably lost.
Hints
- A state can be represented by two bitmasks: currently healthy cells and currently infected cells. Removed cells are the rest.
- Since both infection and burning are monotone, memoized DFS over states is feasible under the small constraint.