973. K Closest Points to Origin#

Code#

 1public int[][] kClosest(int[][] points, int k) {
 2  int[][] result = new int[k][2];
 3
 4  Comparator<int[]> distanceComparator = (int[] a, int[] b) -> {
 5    int aDist = (a[0] * a[0]) + (a[1] * a[1]);
 6    int bDist = (b[0] * b[0]) + (b[1] * b[1]);
 7    return Integer.compare(aDist, bDist);
 8  };
 9
10  PriorityQueue<int[]> pq = new PriorityQueue<>(k, distanceComparator);
11
12  for (int[] point : points) {
13    pq.add(point);
14  }
15
16  for (int i = 0; i < k; i++) {
17    result[i] = pq.remove();
18  }
19
20  return result;
21}

Time Complexity

Space Complexity

\(\mathcal{O}(nlogk)\)

\(\mathcal{O}(n)\)