Minimum time for k virus variants to spread

Array Math Binary Search Geometry Enumeration

50.9% acceptance

Mar 31, 2026

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.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_daysk_variants(points: Vec<Vec<i32>>, k: i32) -> i32 {
    // Manhattan distance: |x1-x2| + |y1-y2|
    // Transform to Chebyshev: u = x+y, v = x-y => max(|u1-u2|, |v1-v2|) = manhattan
    // Binary search on days d. For a given d, check if any point is within d of at least k virus origins.
    // A virus at (u,v) covers [u-d, u+d] x [v-d, v+d] in Chebyshev space.
    // We need an integer point covered by at least k rectangles, with u and v having the same parity.
    
    let transformed: Vec<(i32, i32)> = points.iter().map(|p| (p[0] + p[1], p[0] - p[1])).collect();
    
    let mut lo = 0i32;
    let mut hi = 200;
    
    while lo < hi {
      let mid = lo + (hi - lo) / 2;
      if Self::can_reach(&transformed, mid, k) {
        hi = mid;
      } else {
        lo = mid + 1;
      }
    }
    lo
  }
  
  fn can_reach(pts: &[(i32, i32)], d: i32, k: i32) -> bool {
    let mut v_positions: Vec<i32> = Vec::with_capacity(pts.len() * 2);
    for &(_, v) in pts {
      v_positions.push(v - d);
      v_positions.push(v + d + 1);
    }
    v_positions.sort_unstable();
    v_positions.dedup();

    // Between consecutive event positions, the active rectangle set is constant.
    for window in v_positions.windows(2) {
      let v_start = window[0];
      let v_end = window[1] - 1;
      if v_start > v_end {
        continue;
      }

      let mut u_events: Vec<(i32, i32)> = Vec::with_capacity(pts.len() * 2);
      let mut active = 0usize;
      for &(u, v) in pts {
        if v - d <= v_start && v_start <= v + d {
          active += 1;
          u_events.push((u - d, 1));
          u_events.push((u + d + 1, -1));
        }
      }

      if active < k as usize {
        continue;
      }

      u_events.sort_unstable();

      let mut count = 0i32;
      let mut i = 0usize;
      while i < u_events.len() {
        let u_start = u_events[i].0;
        while i < u_events.len() && u_events[i].0 == u_start {
          count += u_events[i].1;
          i += 1;
        }
        if count < k || i == u_events.len() {
          continue;
        }

        let u_end = u_events[i].0 - 1;
        if Self::matching_parity_exists(u_start, u_end, v_start, v_end) {
          return true;
        }
      }
    }

    false
  }

  fn matching_parity_exists(u_start: i32, u_end: i32, v_start: i32, v_end: i32) -> bool {
    if u_start > u_end || v_start > v_end {
      return false;
    }

    // Any interval of length at least two contains both parities.
    (u_end - u_start + 1) >= 2
      || (v_end - v_start + 1) >= 2
      || u_start.rem_euclid(2) == v_start.rem_euclid(2)
  }
}