# Minheap: [O(N) + klogN ~ O(N) + N(logN) ~ NlogN, O(N)]

class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:

        dist = [(math.sqrt(x**2 + y**2), x, y) for x, y in points]
        heapq.heapify(dist) # O(N)

        res = []
        for _ in range(k):
            d, x, y = heapq.heappop(dist)
            res.append([x, y]) # log N

        # O(N) + klogN ~ O(N) + N(logN) ~ NlogN
        return res

# MaxHeap [O(Nlogk), O(k)]

class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:

        dist = [(-math.sqrt(x**2 + y**2), x, y) for x, y in points[:k]]
        heapq.heapify(dist) # O(k)

        for (x, y) in points[k:]:
            distance = -math.sqrt(x**2 + y**2)
            if distance > dist[0][0]:
                # what we are trying to do here is trying to have (N-k) farthest points
                # not in the heap; if any incoming point is farther than the farthest, we don't
                # do anything; if the incoming point is closer compared to farthest point in the heap
                # we remove the farthest point and add the incoming points; this ensure that we have
                # removed farthest of the farthest point of the point from the heap
                heappop(dist)
                heappush(dist, (distance, x, y)) # log(k)

        return [(x, y) for (_, x, y) in dist]