Minimum Time For K Virus Variants to Spread

Problem

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 _theminimum integer number of days for any point to contain at least _k of the unique virus variants.

Examples

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.length
• 2 <= n <= 50
• points[i].length == 2
• 1 <= xi, yi <= 100
• 2 <= k <= n

Solution

Method 1 – Binary Search + Geometry

Intuition

For any point (x, y), the day it gets infected by a variant is the Manhattan distance to the variant's origin. To have k variants at a point by day d, we need at least k origins within distance d. We can binary search the minimum d such that some point has at least k variants within d.

Approach

1. Binary search on days d from 0 to a large enough value.
2. For each d, enumerate all possible candidate points (all points within d of any origin).
3. For each candidate, count how many variants can reach it in d days (Manhattan distance ≤ d).
4. If any candidate has at least k variants, d is feasible.
5. Return the minimal feasible d.

Code

C++

class Solution {
public:
    int minDays(vector<vector<int>>& points, int k) {
        int n = points.size();
        int l = 0, r = 200;
        while (l < r) {
            int d = (l + r) / 2, found = 0;
            for (int x = 0; x <= 200; ++x) {
                for (int y = 0; y <= 200; ++y) {
                    int cnt = 0;
                    for (auto& p : points) {
                        if (abs(p[0]-x)+abs(p[1]-y) <= d) cnt++;
                    }
                    if (cnt >= k) { found = 1; break; }
                }
                if (found) break;
            }
            if (found) r = d;
            else l = d+1;
        }
        return l;
    }
};

Go

func minDays(points [][]int, k int) int {
    l, r := 0, 200
    for l < r {
        d := (l + r) / 2
        found := false
        for x := 0; x <= 200 && !found; x++ {
            for y := 0; y <= 200 && !found; y++ {
                cnt := 0
                for _, p := range points {
                    if abs(p[0]-x)+abs(p[1]-y) <= d { cnt++ }
                }
                if cnt >= k { found = true }
            }
        }
        if found { r = d } else { l = d+1 }
    }
    return l
}
func abs(a int) int { if a < 0 { return -a } else { return a } }

Java

class Solution {
    public int minDays(int[][] points, int k) {
        int l = 0, r = 200;
        while (l < r) {
            int d = (l + r) / 2;
            boolean found = false;
            for (int x = 0; x <= 200 && !found; x++) {
                for (int y = 0; y <= 200 && !found; y++) {
                    int cnt = 0;
                    for (int[] p : points) {
                        if (Math.abs(p[0]-x)+Math.abs(p[1]-y) <= d) cnt++;
                    }
                    if (cnt >= k) found = true;
                }
            }
            if (found) r = d;
            else l = d+1;
        }
        return l;
    }
}

Kotlin

class Solution {
    fun minDays(points: Array<IntArray>, k: Int): Int {
        var l = 0; var r = 200
        while (l < r) {
            val d = (l + r) / 2
            var found = false
            for (x in 0..200) {
                for (y in 0..200) {
                    var cnt = 0
                    for (p in points) {
                        if (Math.abs(p[0]-x)+Math.abs(p[1]-y) <= d) cnt++
                    }
                    if (cnt >= k) { found = true; break }
                }
                if (found) break
            }
            if (found) r = d else l = d+1
        }
        return l
    }
}

Python

class Solution:
    def minDays(self, points: list[list[int]], k: int) -> int:
        l, r = 0, 200
        while l < r:
            d = (l + r) // 2
            found = False
            for x in range(201):
                for y in range(201):
                    cnt = sum(abs(px-x)+abs(py-y) <= d for px,py in points)
                    if cnt >= k:
                        found = True
                        break
                if found: break
            if found: r = d
            else: l = d+1
        return l

Rust

impl Solution {
    pub fn min_days(points: Vec<Vec<i32>>, k: i32) -> i32 {
        let (mut l, mut r) = (0, 200);
        while l < r {
            let d = (l + r) / 2;
            let mut found = false;
            for x in 0..=200 {
                for y in 0..=200 {
                    let mut cnt = 0;
                    for p in points.iter() {
                        if (p[0]-x).abs()+(p[1]-y).abs() <= d { cnt += 1; }
                    }
                    if cnt >= k { found = true; break; }
                }
                if found { break; }
            }
            if found { r = d; } else { l = d+1; }
        }
        l
    }
}

TypeScript

class Solution {
    minDays(points: number[][], k: number): number {
        let l = 0, r = 200;
        while (l < r) {
            const d = Math.floor((l + r) / 2);
            let found = false;
            for (let x = 0; x <= 200 && !found; x++) {
                for (let y = 0; y <= 200 && !found; y++) {
                    let cnt = 0;
                    for (const [px, py] of points) {
                        if (Math.abs(px-x)+Math.abs(py-y) <= d) cnt++;
                    }
                    if (cnt >= k) found = true;
                }
            }
            if (found) r = d;
            else l = d+1;
        }
        return l;
    }
}

Complexity

• ⏰ Time complexity: O(D * N * M) — D is the binary search range (up to 200), N is number of points, M is candidate points (up to 201*201). Acceptable for n ≤ 50.
• 🧺 Space complexity: O(1) — Only variables, no extra data structures.