DSA problem
K Closest Points to Origin
Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane, and an integer k, return the k closest points to the origin (0, 0). The distance between two points on the X-Y plane is the Euclidean distance, sqrt((x1 - x2)^2 + (y1 - y2)^2). You may return the answer in any order.
A direct solution sorts every point by its distance from the origin and returns the first k. That takes O(n log n) time, which is straightforward but suboptimal when k is much smaller than n.
The canonical heap solution uses a max-heap of size k keyed by squared distance. Iterate every point and push it; whenever the heap grows beyond k, pop the root — the farthest point in the heap. After all points are processed, the heap contains exactly the k closest. This runs in O(n log k), which dominates the sorting solution for small k. We use squared distance to avoid an expensive square-root that doesn't change ordering.
An even faster average-case solution is Quickselect, which partitions the array around a pivot in the spirit of Quicksort but recurses only on the side containing the answer. Its expected time is O(n), though worst-case is O(n²). For interview settings the heap solution is the most defensible and is what we show below; Quickselect is noted as the further optimization.
Examples
points = [[1,3],[-2,2]], k = 1[[-2,2]]points = [[3,3],[5,-1],[-2,4]], k = 2[[3,3],[-2,4]]points = [[1,1],[2,2],[3,3]], k = 2[[1,1],[2,2]]Constraints
- 1 <= k <= points.length <= 10^4
- -10^4 <= xi, yi <= 10^4
- It is guaranteed that the answer is unique except for the order in which it is returned.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.