Problem statement

https://leetcode.com/problems/minimum-time-for-k-virus-variants-to-spread/

Solution 1

We can reformulate the problem: given points we need to find the smallest size of square, such that we have point with k intersections.

First, we need to rotate our coordinates and deal with half-integer: multiply everything by 2.

Then we can use binary search: let check(m) be the answer to question if we have k cross points when we take size equal to m. We can use line sweep with coeffecient copression: for every y we need to keep count is number of active rectangles.

Complexity

Time complexity is O(n^2*log n * log T), where T is maximum value of coordinates (2*10^9, because we multiply everything by 2). Space complexity is O(n).

Code

class Solution:
    def minDayskVariants(self, P, k):
        P = [(2*x - 2*y, 2*x + 2*y) for x, y in P]
        
        def check(m):
            ys = sorted(set([y - m for x, y in P] + [y + m for x, y in P]))
            y_i = {v: i for i, v in enumerate(ys)}
            count, ans = [0] * len(y_i), 0
            
            sides_lft = [(x-m, 1, y-m, y+m) for x, y in P]
            sides_rgh = [(x+m, -1, y-m, y+m) for x, y in P]
            sides = sorted(sides_lft + sides_rgh)
            
            for x, op_cl, y1, y2 in sides:
                for i in range(y_i[y1], y_i[y2]): count[i] += op_cl
                ans = max(ans, max(count))
                
            return ans >= k
        
        beg, end = -1, 2*10**9
        while beg + 1 < end:
            mid = (beg + end)//2
            if check(mid):
                end = mid
            else:
                beg = mid
                
        return end//2

Solution 2

There is also better time complexity solution, using segment trees. Ineed, what we need to do is to update values in range.

Complexity

Time complexity is O(n log n log T), however in practice it works slower than previous approach, because constraints are very small. Space complexity is O(n).

Code

class SegmentTree:
    def __init__(self, N, update_fn, query_fn):
        self.UF, self.QF = update_fn, query_fn
        self.T = defaultdict(int)
        self.L = defaultdict(int)
    
    def push(self, v):
        for u in [2*v, 2*v+1]:
            self.T[u] = self.UF(self.T[u], self.L[v])
            self.L[u] = self.UF(self.L[u], self.L[v])
        self.L[v] = 0

    def update(self, v, tl, tr, l, r, h):
        if l > r: return
        if l == tl and r == tr:
            self.T[v] = self.UF(self.T[v], h)
            self.L[v] = self.UF(self.L[v], h)
        else:
            self.push(v)
            tm = (tl + tr)//2
            self.update(v*2, tl, tm, l, min(r, tm), h)
            self.update(v*2+1, tm+1, tr, max(l, tm+1), r, h)
            self.T[v] = self.QF(self.T[v*2], self.T[v*2+1])

    def query(self, v, tl, tr, l, r):
        if l > r: return -float("inf")
        if l <= tl and tr <= r: return self.T[v]
        self.push(v)
        tm = (tl + tr)//2
        return self.QF(self.query(v*2, tl, tm, l, min(r, tm)), self.query(v*2+1, tm+1, tr, max(l, tm+1), r))

class Solution:
    def minDayskVariants(self, P, k):
        P = [(2*x - 2*y, 2*x + 2*y) for x, y in P]
        
        def check(m):
            ys = sorted(set([y - m for x, y in P] + [y + m for x, y in P]))
            y_i = {v: i for i, v in enumerate(ys)}
            STree, ans = SegmentTree(len(y_i), lambda x, y: x+y, max), 0
 
            
            sides_lft = [(x-m, 1, y-m, y+m) for x, y in P]
            sides_rgh = [(x+m, -1, y-m, y+m) for x, y in P]
            sides = sorted(sides_lft + sides_rgh)
            
            for x, op_cl, y1, y2 in sides:
                STree.update(1, 0, len(y_i) - 1, y_i[y1], y_i[y2] - 1, op_cl)
                ans = max(ans, STree.query(1, 0, len(y_i) - 1, 0, len(y_i) - 1))
                
            return ans >= k
        
        beg, end = -1, 2*10**9
        while beg + 1 < end:
            mid = (beg + end)//2
            if check(mid):
                end = mid
            else:
                beg = mid
                
        return end//2