Watch 2 video solutions for Minimum Time For K Virus Variants to Spread, a hard level problem involving Array, Math, Binary Search. This walkthrough by Programming Live with Larry has 482 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
There are n unique virus variants in an infinite 2D grid. You are given a 2D array points, where points[i] = [xi, yi] represents a virus originating at (xi, yi) on day 0. Note that it is possible for multiple virus variants to originate at the same point.
Every day, each cell infected with a virus variant will spread the virus to all neighboring points in the four cardinal directions (i.e. up, down, left, and right). If a cell has multiple variants, all the variants will spread without interfering with each other.
Given an integer k, return the minimum integer number of days for any point to contain at least k of the unique virus variants.
Example 1:
Input: points = [[1,1],[6,1]], k = 2 Output: 3 Explanation: On day 3, points (3,1) and (4,1) will contain both virus variants. Note that these are not the only points that will contain both virus variants.
Example 2:
Input: points = [[3,3],[1,2],[9,2]], k = 2 Output: 2 Explanation: On day 2, points (1,3), (2,3), (2,2), and (3,2) will contain the first two viruses. Note that these are not the only points that will contain both virus variants.
Example 3:
Input: points = [[3,3],[1,2],[9,2]], k = 3 Output: 4 Explanation: On day 4, the point (5,2) will contain all 3 viruses. Note that this is not the only point that will contain all 3 virus variants.
Constraints:
n == points.length2 <= n <= 50points[i].length == 21 <= xi, yi <= 1002 <= k <= nProblem Overview: You are given coordinates of different virus variants on a grid. Each variant spreads one unit per second using Manhattan distance. The task is to compute the minimum time t such that there exists at least one grid cell infected by k different variants.
Approach 1: Brute Force Candidate Points (High Polynomial Time)
The Manhattan spread from each variant forms a diamond region. If you enumerate candidate intersection points formed by the boundaries of these diamonds, you can test whether at least k variants cover that point. For every candidate point, compute |x - xi| + |y - yi| for all variants and count how many are within time t. This approach directly checks geometric overlap but the number of candidate points grows quickly, leading to roughly O(n^3) time and O(1) extra space. It mainly serves as intuition for how the overlap region behaves.
Approach 2: Binary Search + Coordinate Transformation + Sweep Line (Optimal)
The key observation is that a Manhattan distance region |x - xi| + |y - yi| ≤ t becomes an axis‑aligned square after transforming coordinates: u = x + y and v = x - y. Each virus then covers a square defined by [ui - t, ui + t] and [vi - t, vi + t]. The problem becomes finding whether a point exists that lies inside at least k of these squares.
Binary search the answer on time t. For each candidate t, convert every diamond to its square representation and run a sweep line over the u axis. Add events for square entry and exit. While sweeping, maintain overlapping intervals on the v axis using a segment tree or coordinate-compressed difference structure. If any position on v reaches coverage ≥ k, a point exists where k variants meet.
This reduces the geometric search dramatically. The check runs in O(n log n) time with O(n) space, and binary search adds a log T factor where T is the coordinate range. The final complexity becomes O(n log n log T). The technique relies on ideas from geometry, binary search, and sweep-line style interval processing.
Recommended for interviews: The expected solution is the binary search combined with geometric transformation and sweep line. Brute force shows understanding of Manhattan regions, but the optimized approach demonstrates the ability to convert geometry constraints into interval overlap problems and apply efficient search techniques.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Candidate Intersection | O(n^3) | O(1) | Useful for understanding geometric overlap of Manhattan diamonds; impractical for large inputs |
| Binary Search + Sweep Line on Transformed Coordinates | O(n log n log T) | O(n) | General optimal solution when coordinates are large and you need to detect k overlapping regions efficiently |