K Closest Points to Origin

01 · Question

Given an array of points where points[i] = [xi, yi] and an integer k, return the k closest points to the origin (0, 0).

02 · Analysis

Squared distance preserves distance order without a square root. The displayed implementation pushes all n points into a min-heap, then pops k: O(n log(n+1) + k log(n+1)) time and O(n) auxiliary space, plus output. Require 0 <= k <= n. Heapifying the initial entries would make construction O(n); a size-k max-heap is the O(k)-space alternative. Use a wide type before squaring large coordinates.

03 · Solution

Reference solution

1import heapq
2
3def kClosest(points: List[List[int]], k: int) -> List[List[int]]:
4    heap = []
5    for x, y in points:
6        d = x*x + y*y
7        heapq.heappush(heap, (d, x, y))
8    res = []
9    for _ in range(k):
10        _, x, y = heapq.heappop(heap)
11        res.append([x, y])
12    return res

Top K Frequent Elements

Delete Operations