leetcode

commit 58adb3a8e7e008cb69e0a55e05b8831ec93b42dc
parent 2e7a99518b0d10618b9c88bf6d6c0379e97874d4
Author: Andrew Laack <andrew@laack.co>
Date:   Mon,  7 Jul 2025 09:13:33 -0500

Completed k closest points to origin

Diffstat:
A
k-closest-points-to-origin/k-closest-points-to-originV1.py
 | 
65
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

1 file changed, 65 insertions(+), 0 deletions(-)
diff --git a/k-closest-points-to-origin/k-closest-points-to-originV1.py b/k-closest-points-to-origin/k-closest-points-to-originV1.py
@@ -0,0 +1,65 @@
+from heapq import heappop, heapify
+
+# Intuition:
+
+# we can calculate the distance easily
+# we can place these distances into list in O(n)
+# we can make this into a min-heap in O(n)
+# we can remove the lowest elements from the heap
+# which will be closest ones as distance is always positive
+# return first k
+
+# Approach:
+
+# 1) Place the euclidean distance for each element into an array called distances
+# a) These distances should be an object that contains both the coordinates
+# of the point as well as the distances.
+# we should then implement the comparison operator
+# based on the distance. We know the result is
+# unqiue so we don't need to worry about tie breaking
+# behaviors
+# 2) Create a heap out of the distances array
+# 3) Remove k elements, placing them into a return list
+# 4) Return the associated coordinates
+
+# Time Complexity
+
+# O(n) - Create list
+# O(n) - Create heap
+# O(klogn + k) - Pull out elements and place in new list
+
+# OVERALL:
+# O(klogn + n)
+
+# Space Complexity
+
+# O(k + n) \equiv O(n)
+
+# Code:
+
+
+class Distance:
+    def __init__(self, coords):
+        self.coords = coords
+        self.val = self._sq_euclidean_distance(coords)
+
+    def __lt__(self, other):
+        if self.val < other.val:
+            return True
+        return False
+
+    def _sq_euclidean_distance(self, coords):
+        return (coords[0] ** 2) + (coords[1] ** 2)
+
+
+class Solution:
+    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
+        distances = [Distance(coords) for coords in points]
+        heapify(distances)
+
+        results = []
+
+        for i in range(0, k):
+            results.append((heappop(distances).coords))
+
+        return results