k-closest-points-to-originV1.py (1679B)
1 from heapq import heappop, heapify 2 3 # Intuition: 4 5 # we can calculate the distance easily 6 # we can place these distances into list in O(n) 7 # we can make this into a min-heap in O(n) 8 # we can remove the lowest elements from the heap 9 # which will be closest ones as distance is always positive 10 # return first k 11 12 # Approach: 13 14 # 1) Place the euclidean distance for each element into an array called distances 15 # a) These distances should be an object that contains both the coordinates 16 # of the point as well as the distances. 17 # we should then implement the comparison operator 18 # based on the distance. We know the result is 19 # unqiue so we don't need to worry about tie breaking 20 # behaviors 21 # 2) Create a heap out of the distances array 22 # 3) Remove k elements, placing them into a return list 23 # 4) Return the associated coordinates 24 25 # Time Complexity 26 27 # O(n) - Create list 28 # O(n) - Create heap 29 # O(klogn + k) - Pull out elements and place in new list 30 31 # OVERALL: 32 # O(klogn + n) 33 34 # Space Complexity 35 36 # O(k + n) \equiv O(n) 37 38 # Code: 39 40 41 class Distance: 42 def __init__(self, coords): 43 self.coords = coords 44 self.val = self._sq_euclidean_distance(coords) 45 46 def __lt__(self, other): 47 if self.val < other.val: 48 return True 49 return False 50 51 def _sq_euclidean_distance(self, coords): 52 return (coords[0] ** 2) + (coords[1] ** 2) 53 54 55 class Solution: 56 def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]: 57 distances = [Distance(coords) for coords in points] 58 heapify(distances) 59 60 results = [] 61 62 for i in range(0, k): 63 results.append((heappop(distances).coords)) 64 65 return results