Leetcode Problem 1956. Minimum Time For K Virus Variants to Spread

1956. Minimum Time For K Virus Variants to Spread

Leetcode Solutions

Binary Search + Rotate Axis +D Sweep Line

  1. Define a function check(day) that will determine if there is a point with at least k overlapping virus spread areas after day days.
  2. Rotate the axis by 45 degrees to turn the diamond-shaped spread into squares.
  3. Use a 2D sweep line technique to count the overlapping of virus spread areas at each critical point.
  4. Apply binary search on the number of days to find the minimum number of days required.
  5. Return the result from the binary search as the minimum number of days.
UML Thumbnail

Exhaustive Search on Grid

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...