Skip to content

1956. Minimum Time For K Virus Variants to Spread 👍

  • Time: $O(100^2 n\log k) = O(n\log k)$
  • Space: $O(k)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
 public:
  int minDayskVariants(vector<vector<int>>& points, int k) {
    constexpr int kMax = 100;
    int ans = INT_MAX;

    for (int a = 1; a <= kMax; ++a)
      for (int b = 1; b <= kMax; ++b) {
        // Stores the k minimum distances of points that can reach (a, b).
        priority_queue<int> maxHeap;
        for (const vector<int>& point : points) {
          const int x = point[0];
          const int y = point[1];
          maxHeap.push(abs(x - a) + abs(y - b));
          if (maxHeap.size() > k)
            maxHeap.pop();
        }
        ans = min(ans, maxHeap.top());
      }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
  public int minDayskVariants(int[][] points, int k) {
    final int MAX = 100;
    int ans = Integer.MAX_VALUE;

    for (int a = 1; a <= MAX; ++a)
      for (int b = 1; b <= MAX; ++b) {
        // Stores the k minimum distances of points that can reach (a, b).
        Queue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        for (int[] point : points) {
          final int x = point[0];
          final int y = point[1];
          maxHeap.offer(Math.abs(x - a) + Math.abs(y - b));
          if (maxHeap.size() > k)
            maxHeap.poll();
        }
        ans = Math.min(ans, maxHeap.peek());
      }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
  def minDayskVariants(self, points: list[list[int]], k: int) -> int:
    MAX = 100
    ans = math.inf

    for a in range(1, MAX + 1):
      for b in range(1, MAX + 1):
        # Stores the k minimum distances of points that can reach (a, b).
        maxHeap = []
        for x, y in points:
          heapq.heappush(maxHeap, -abs(x - a) + -abs(y - b))
          if len(maxHeap) > k:
            heapq.heappop(maxHeap)
        ans = min(ans, -maxHeap[0])

    return ans