K Closest points - Priority Queue / Heap / Top K

Problems
21

This should be O(N):

def k_closest_points(points: List[List[int]], k: int) → List[List[int]]:
heapq.heapify(points)
closest_points = []

for i in range(k):
    closest_points.append(heapq.heappop(points))

return closest_points
22

Or possibly n+k (where n is the length of points since heapify is O(N))

23

leetcode

24

C# version test 2 seems bugged. It expects (-2, 2) as the first closest, but the one is the (1, 3). Distances are sqrt(4) and sqrt(3) respectively

25

Two errors in Alternative solution:

  1. dist() function need add sqrt
  2. Need to do reversed return(res) array, as the order of max_heap is beginning from maximum distance, otherwise Test#3 would fail.
26

  1. dist() does not need sqrt as square root preserves ordering

  2. no need to reverse, the max of (-distance) is the smallest distance from the origin

27

^this

28

(1, 3)'s distance to (0, 0) is sqrt(10)

29

in a white boarding interview, you can casually mention we need to import these. in a online coding interview, you should be able to look it up

30

the dist(point) function should be -point[0] ** 2 - point[1] ** 2

31

Tulip is right. With heapify we can get the complexity down to O(n + k*log n)

32

Alternate solution seems better in terms of O complexity, time is the same (I saw different thoughts on this in comments, so to me it’s we still have to check every point and there is a chance they are bad sorted initially so that we’d have to insert each one in the heap which give n*log(N) though) but space gets reduced from O(N) to O(K), nice.

33

In the alternate version, should

 return -point[0] ** 2 + point[1] ** 2

be

 return -( point[0] ** 2 + point[1] ** 2 )
34

Getting the following error for C#:
Solution.cs(9,22): error CS0246: The type or namespace name `PriorityQueue’ could not be found. Are you missing an assembly reference?

using System;
using System.Collections.Generic;
using System.Linq;

class Solution
{
    public static List<List<int>> KClosestPoints(List<List<int>> points, int k)
    {
        var pq = new PriorityQueue<List<int>,double>();
        
        var point2 = new List<int>() {0,0};
        
        foreach(var point1 in points)
        { 
         var dist = FindDistance(point1, point2);
         pq.Enqueue(point1,dist);   
        }
        
        var ans = new List<List<int>>();
        
        for(int i = 0; i < k; i++)
        {
            ans.Add(pq.Dequeue());
        }
        return ans;
    }
    
    
    public static double FindDistance(List<int> point1, List<int> point2)
    {
        var x = point1[0] - point2[0];
        var y = point1[1] - point2[1];
        
        var xsquare = Math.Pow(x, 2);
        var ysquare = Math.Pow(y, 2);
        
        return Math.Sqrt(xsquare + ysquare);
    }

    public static List<string> SplitWords(string s)
    {
      return string.IsNullOrEmpty(s) ? new List<string>() : s.Trim().Split(' ').ToList();
    }

    public static void Main()
    {
        int pointsLength = int.Parse(Console.ReadLine());
        List<List<int>> points = new List<List<int>>();
        for (int i = 0; i < pointsLength; i++)
        {
            points.Add(SplitWords(Console.ReadLine()).Select(int.Parse).ToList());
        }
        int k = int.Parse(Console.ReadLine());
        List<List<int>> res = KClosestPoints(points, k);
        foreach (List<int> row in res)
        {
            Console.WriteLine(String.Join(' ', row));
        }
    }
}
35

I think the time complexity can be O(n) + klog(n), where k might be big as n
The idea is that we already have the full list that we can simply use heapify

from typing import List
from heapq import heapify, heappop

def k_closest_points(points: List[List[int]], k: int) -> List[List[int]]:
    if k >= len(points):
        return sorted(points, key=lambda x: x[0]**2 + x[1] ** 2)
    h = [(p[0]**2 + p[1]**2, p) for p in points]
    heapify(h)
    rst = []
    assert h
    for _ in range(k):
        _, p = heappop(h)
        rst.append(p)
    return rst