Katkat
Back

Minimize deaths in spreading plant infection

OpenAISoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to simulate a state-based grid propagation and optimize intervention timing using either greedy or dynamic programming approaches.

Problem Statement

You are monitoring a grid of plants, represented by an N x M integer matrix where each cell (r, c) contains a plant. A plant can be in one of three states:

  1. 0: Healthy
  2. 1: Infected
  3. -1: Dead

Each day, the infection spreads: any healthy plant adjacent (up, down, left, right) to at least one infected plant becomes infected the next day. Furthermore, an infected plant dies exactly K days after it first becomes infected. Once a plant is dead, it stays dead and cannot spread the infection.

You have a single "Pesticide Shot" that you can use on exactly one day to instantly turn all currently infected plants into healthy plants (they stop being infected and will not be dead). After the shot, the grid continues to propagate infection as normal from any plants that were not infected at the time of the shot (or any new infections that occur).

Write a function minimize_deaths(grid, K) that returns the minimum number of dead plants remaining after the infection has fully stabilized (i.e., no more new infections can occur or all plants are dead).

Constraints

  • N, M = 1
  • The grid contains at least one initially infected plant.

Example

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

  • Day 0: (0, 1) is infected.
  • Day 1: (0, 0), (0, 2), and (1, 1) become infected. (0, 1) dies (since K=1).
  • If you use the shot on Day 0, only (0, 1) is cured. If you use it on Day 1, all infected plants are cured.

Edge Cases

  • The infection may die out naturally before all plants are affected.
  • The grid might contain no initially infected plants (return 0).

Hints

Hint 1

Simulate the process day-by-day to track the infection status and "time-since-infection" for every cell.

Hint 2

Since you only have one shot, consider that the optimal day to use it is likely between Day 0 and the day the last plant becomes infected.

Hint 3

For each possible day `d` to use the pesticide, perform a full simulation to see the resulting number of dead plants and track the minimum.

Follow-up questions

  • How would the solution change if you could use the pesticide shot twice?
  • What is the time complexity of your simulation approach, and can it be optimized using BFS distance mapping?
  • How would you modify the model if healthy plants had a 'resistance' factor, meaning they require contact with two infected neighbors to become infected?