LeetCode 1956 - Minimum Time For K Virus Variants to Spread

LeetCode Problem 1956

Difficulty: 🔴 Hard
Topics: Array, Math, Binary Search, Geometry, Enumeration

Solution

Problem Understanding

The problem describes multiple virus variants spreading across an infinite 2D grid. Each virus starts from its own origin point on day 0. Every day, a virus spreads one step in the four cardinal directions, which means after d days, a virus can reach every point whose Manhattan distance from its origin is at most d.

The Manhattan distance between two points (x1, y1) and (x2, y2) is:

$$|x1 - x2| + |y1 - y2|$$

A point on the grid contains a virus variant on day d if the virus can reach that point within d steps.

We are given:

• points[i] = [xi, yi], the starting location of the i-th virus
• An integer k

We must determine the minimum number of days such that there exists at least one grid cell that contains at least k different virus variants simultaneously.

An important detail is that multiple virus variants may originate from the same coordinates. Even though the coordinates may repeat, the virus variants themselves are considered distinct.

The constraints are relatively small:

• n <= 50
• Coordinates are at most 100

This tells us that an exponential or heavy geometric approach might still be acceptable if carefully optimized. Since the answer represents a minimum feasible day count, binary search becomes a strong candidate.

Several edge cases are important:

• Multiple viruses may already overlap at day 0
• k may equal n, meaning we need a point reachable by all variants
• Viruses may be extremely far apart
• There may be many candidate intersection regions
• The optimal meeting point does not necessarily coincide with an original virus location

The infinite grid sounds intimidating, but the geometry of Manhattan distance gives the problem strong structure that we can exploit.

Approaches

Brute Force Approach

A direct brute-force solution would simulate day-by-day virus spreading and track which viruses reach each cell.

For a fixed number of days d, each virus covers a diamond-shaped region:

$$|x - xi| + |y - yi| \le d$$

One brute-force strategy would enumerate all grid cells inside a sufficiently large bounding box and count how many virus regions contain each point.

This works because if any point is covered by at least k viruses, then d is feasible.

However, this approach becomes inefficient because:

• The grid is infinite
• Coverage regions grow quadratically with distance
• The bounding box for large distances becomes huge
• Repeating this for binary search would be extremely expensive

Even with coordinate limits near 100, the answer can exceed that range significantly.

Key Insight

The critical observation is that Manhattan distance constraints can be transformed into linear inequalities.

A point (x, y) satisfies:

$$|x - xi| + |y - yi| \le d$$

if and only if the following are all true:

$$x + y \le xi + yi + d$$

$$x + y \ge xi + yi - d$$

$$x - y \le xi - yi + d$$

$$x - y \ge xi - yi - d$$

Each virus therefore defines a rectangle in transformed coordinates:

• u = x + y
• v = x - y

For a fixed d, we need to determine whether there exists a point covered by at least k such rectangles.

Since n <= 50, we can enumerate subsets indirectly by sweeping candidate boundaries.

We binary search the answer:

• If a day count d is feasible, larger values are also feasible
• This monotonicity makes binary search valid

For each candidate d, we test feasibility geometrically.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(R² × n × log R)	O(R²)	Enumerates grid cells in a large bounding box
Optimal	O(log M × n³)	O(n²)	Binary search with geometric intersection checking

Here, M is the maximum possible answer range.

Algorithm Walkthrough

Step 1, Binary Search the Answer

The answer is monotonic.

If it is possible for k viruses to overlap after d days, then it is also possible after d + 1 days because every virus region only expands.

This allows binary search over the minimum feasible day.

We initialize:

• left = 0
• right = 200

A larger upper bound such as 400 or 1000 also works safely.

Step 2, Convert Each Virus Region

For a fixed day d, each virus covers:

$$|x - xi| + |y - yi| \le d$$

Transform coordinates:

$$u = x + y$$

$$v = x - y$$

Then the virus coverage becomes:

$$xi + yi - d \le u \le xi + yi + d$$

$$xi - yi - d \le v \le xi - yi + d$$

This is an axis-aligned rectangle in (u, v) space.

Step 3, Enumerate Candidate Intersections

We need to know whether at least k rectangles overlap.

A standard geometric trick is that any overlap region boundary must come from rectangle boundaries.

We collect all candidate u coordinates from:

• lower bounds
• upper bounds

Similarly for v.

Then we test every candidate (u, v) pair.

For each candidate point:

• Count how many rectangles contain it
• If count reaches k, then day d is feasible

Step 4, Feasibility Check

For each virus rectangle:

• Check whether:

$$u_{min} \le u \le u_{max}$$

and

$$v_{min} \le v \le v_{max}$$

If true, the rectangle contains the point.

If at least k rectangles contain the point, return True.

Step 5, Finish Binary Search

If day mid is feasible:

• Store answer
• Search smaller values

Otherwise:

• Search larger values

Eventually binary search converges to the minimum feasible day.

Why it works

The transformed geometry converts diamond-shaped Manhattan regions into axis-aligned rectangles. Any overlap region among rectangles must have boundaries derived from rectangle edges. Therefore, if an overlap of size at least k exists, there exists a candidate boundary point we will enumerate.

Binary search is valid because virus regions only grow over time, making feasibility monotonic.

Python Solution

from typing import List

class Solution:
    def minDayskVariants(self, points: List[List[int]], k: int) -> int:
        n = len(points)

        def can(days: int) -> bool:
            rectangles = []

            u_values = set()
            v_values = set()

            for x, y in points:
                u_min = x + y - days
                u_max = x + y + days

                v_min = x - y - days
                v_max = x - y + days

                rectangles.append((u_min, u_max, v_min, v_max))

                u_values.add(u_min)
                u_values.add(u_max)

                v_values.add(v_min)
                v_values.add(v_max)

            for u in u_values:
                for v in v_values:
                    count = 0

                    for u_min, u_max, v_min, v_max in rectangles:
                        if u_min <= u <= u_max and v_min <= v <= v_max:
                            count += 1

                    if count >= k:
                        return True

            return False

        left = 0
        right = 400

        while left < right:
            mid = (left + right) // 2

            if can(mid):
                right = mid
            else:
                left = mid + 1

        return left

The implementation starts by defining a helper function can(days) that determines whether at least k viruses can overlap after a given number of days.

Inside this helper, every virus region is converted into a rectangle in transformed (u, v) coordinates. We store:

• minimum and maximum u
• minimum and maximum v

We also collect all rectangle boundaries into candidate coordinate sets.

Next, we enumerate every candidate (u, v) pair. For each pair, we count how many rectangles contain the point. If the count reaches k, the configuration is feasible.

The outer binary search repeatedly calls this feasibility function. Since feasibility is monotonic, binary search correctly finds the smallest valid number of days.

Go Solution

func minDayskVariants(points [][]int, k int) int {
	can := func(days int) bool {
		type Rect struct {
			uMin int
			uMax int
			vMin int
			vMax int
		}

		rectangles := []Rect{}

		uSet := map[int]bool{}
		vSet := map[int]bool{}

		for _, p := range points {
			x := p[0]
			y := p[1]

			uMin := x + y - days
			uMax := x + y + days

			vMin := x - y - days
			vMax := x - y + days

			rectangles = append(rectangles, Rect{
				uMin: uMin,
				uMax: uMax,
				vMin: vMin,
				vMax: vMax,
			})

			uSet[uMin] = true
			uSet[uMax] = true

			vSet[vMin] = true
			vSet[vMax] = true
		}

		uValues := []int{}
		for val := range uSet {
			uValues = append(uValues, val)
		}

		vValues := []int{}
		for val := range vSet {
			vValues = append(vValues, val)
		}

		for _, u := range uValues {
			for _, v := range vValues {
				count := 0

				for _, rect := range rectangles {
					if rect.uMin <= u && u <= rect.uMax &&
						rect.vMin <= v && v <= rect.vMax {
						count++
					}
				}

				if count >= k {
					return true
				}
			}
		}

		return false
	}

	left := 0
	right := 400

	for left < right {
		mid := (left + right) / 2

		if can(mid) {
			right = mid
		} else {
			left = mid + 1
		}
	}

	return left
}

The Go implementation mirrors the Python approach closely.

Since Go does not have tuples, we define a Rect struct to store rectangle boundaries. Hash sets are implemented using map[int]bool.

Slices are used for candidate coordinate enumeration. Integer overflow is not a concern because coordinates and distances remain small.

Worked Examples

Example 1

points = [[1,1],[6,1]]
k = 2

Day = 2

Virus 1:

$$|x-1| + |y-1| \le 2$$

Virus 2:

$$|x-6| + |y-1| \le 2$$

The regions do not overlap.

Day = 3

Virus 1 reaches:

$$x \in [ -2, 4 ]$$

Virus 2 reaches:

$$x \in [ 3, 9 ]$$

Overlap exists at:

• (3,1)
• (4,1)

So answer is 3.

Example 2

points = [[3,3],[1,2],[9,2]]
k = 2

Day = 2

First virus rectangle:

Value	Range
u	[4, 8]
v	[-2, 2]

Second virus rectangle:

Value	Range
u	[1, 5]
v	[-3, 1]

The rectangles overlap.

A valid point is (2,2).

So answer is 2.

Example 3

points = [[3,3],[1,2],[9,2]]
k = 3

We need all three viruses to overlap.

At day 3, no common intersection exists.

At day 4, point (5,2) works:

Virus	Distance
(3,3)	3
(1,2)	4
(9,2)	4

All are within reach.

So answer is 4.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log M × n³)	Binary search times rectangle overlap checking
Space	O(n²)	Stores rectangles and candidate boundaries

For each binary search iteration:

• We create n rectangles
• We enumerate at most 2n candidate u values
• We enumerate at most 2n candidate v values
• For every candidate pair, we scan all n rectangles

This gives:

$$O((2n)(2n)n) = O(n^3)$$

Binary search adds a multiplicative log M factor.

Since n <= 50, this is easily fast enough.

Test Cases

sol = Solution()

assert sol.minDayskVariants([[1,1],[6,1]], 2) == 3
# Basic two-virus overlap

assert sol.minDayskVariants([[3,3],[1,2],[9,2]], 2) == 2
# Need overlap among any two viruses

assert sol.minDayskVariants([[3,3],[1,2],[9,2]], 3) == 4
# Need overlap among all viruses

assert sol.minDayskVariants([[1,1],[1,1]], 2) == 0
# Multiple variants already at same point

assert sol.minDayskVariants([[1,1],[100,100]], 2) == 99
# Very distant viruses

assert sol.minDayskVariants([[1,1],[2,2],[3,3]], 2) == 1
# Small overlap quickly achievable

assert sol.minDayskVariants([[1,1],[2,2],[3,3]], 3) == 2
# All viruses need common meeting point

assert sol.minDayskVariants([[1,1],[1,100],[100,1],[100,100]], 4) == 99
# Large symmetric configuration

assert sol.minDayskVariants([[5,5],[5,5],[5,5]], 3) == 0
# All variants already overlap

Test	Why
[[1,1],[6,1]], k=2	Basic example
[[3,3],[1,2],[9,2]], k=2	Partial overlap
[[3,3],[1,2],[9,2]], k=3	Full overlap
Duplicate coordinates	Tests day 0 answer
Very distant points	Tests large answer
Small clustered points	Tests quick overlap
k = n	Tests all-virus requirement
Symmetric corners	Tests geometry correctness
All same coordinate	Tests immediate overlap

Edge Cases

Multiple Viruses Starting at the Same Point

Different virus variants may originate from identical coordinates. A buggy implementation might accidentally deduplicate them and lose variants.

This implementation never removes duplicates. Each virus produces its own rectangle, so if multiple variants start together, the overlap count immediately reflects that. As a result, the answer can correctly be 0.

Requiring All Viruses to Overlap

When k = n, every virus must simultaneously cover some common point. This is the strictest possible requirement.

The rectangle intersection logic naturally handles this because we simply count how many rectangles contain a candidate point. The algorithm does not distinguish between partial and complete overlap.

Optimal Point Not Equal to Any Virus Origin

A naive implementation might only check original virus coordinates. That fails because the optimal overlap point may lie somewhere entirely different.

The transformed-coordinate rectangle approach correctly searches all possible intersection regions indirectly through boundary enumeration, ensuring no valid overlap point is missed.