Minimum Time For K Virus Variants to Spread - Solution & Explanation

Problem 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.