NewThe Learning module is now liveSee what's new

(This question is a variation of the LeetCode question 994. Rotting Orange. If you haven't completed that question yet, it is recommended to solve it first.)

A research lab is monitoring the spread of a plant disease across a grid of plants. You are given an m x n grid where each plant is either healthy (0) or infected (1).

The disease spreads simultaneously across all plants each day. A healthy plant becomes infected if at least threshold of its 8 neighboring cells (including diagonals) are currently infected. Once a plant becomes infected, it remains infected forever.

Return the number of days until the epidemic stabilizes, meaning a full day passes with no new infections. If the grid is already stable, return 0.

Constraints:

  • 1 ≤ grid.length ≤ 200
  • 1 ≤ grid[i].length ≤ 200
  • grid is rectangular
  • 1 ≤ threshold ≤ 8
  • Each cell is either 0 or 1
  • The answer fits in a 32-bit signed integer

Example 1:

Input: grid = [[1,0,0],   [0,0,0],   [0,0,0]], threshold = 1 Output: 2 Explanation: The inflection precoess are as follows:

  • On day 1, the three cells adjacent to the top-left corner become infected because each has at least one infected neighbor.
  • On day 2, the remaining five cells become infected.
  • After day 2, no further changes occur, so the epidemic stabilizes after 2 days.

Example 2:

Input: grid = [[1,0],[0,0]], threshold = 2 Output: 0 Explanation: No healthy cell has 2 or more infected neighbors, so no new infections occur.

Example 3:

Input: grid = [[1,1,0],[0,0,0],[0,0,0]], threshold = 2 Output: 3


Accepted
11.4k/26.4k
Acceptance Rate43.3%
Test Cases
Input
grid =
threshold =
Output
Expected