K Closest Points to Origin
Problem
Given an array points where points[i] = [x_i, y_i] 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. The answer is guaranteed to be unique (except for the order that it is in).
- 1 ≤ k ≤ points.length ≤ 10⁴
- −10⁴ ≤ points[i][0], points[i][1] ≤ 10⁴
Example
points = [[1,3],[-2,2],[2,-2]], k = 2[[-2,2],[2,-2]]The algorithm calculates the squared Euclidean distance for each point to avoid costly square root operations. For example, point [1,3] has distance 1^2 + 3^2 = 10, [-2,2] has 4 + 4 = 8, and [2,-2] has 4 + 4 = 8. These distances are stored in a min-heap along with the points. The heap is then used to efficiently extract the k points with the smallest distances. The first two points popped from the heap are [-2,2] and [2,-2], which are the closest to the origin.
Approach
Straightforward Solution
A brute-force approach sorts all points by their distance to the origin, which takes O(n log n) time. This is inefficient when k is much smaller than n.
Core Observation
The problem reduces to selecting the k points with the smallest Euclidean distances to the origin. Since distance comparisons suffice, squared distances can be used to avoid expensive square root calculations.
Path to Optimal
Recognizing that only the k smallest distances are needed, a min-heap can be used to store all points keyed by their distance. Heapifying the entire list takes O(n) time, and extracting k elements takes O(k log n) time, which is more efficient when k is small relative to n.
Optimal Approach
PreviewCompute squared distances for all points and store them in a list along with their coordinates. Use heapq…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n + k log n)
Heapifying all n points takes O(n) time, and each of the k heappop operations takes O(log n), resulting in O(n + k log n) total time.
Space
O(n)
The min-heap stores all n points with their distances, requiring O(n) auxiliary space proportional to the input size.
Pattern Spotlight
Heap / Priority Queue (Partial Sorting)
When needing the top k elements by a key, use a heap to avoid full sorting; heapify all elements for O(n) setup, then extract k times for O(k log n), which is optimal when k << n.
Solution
| 1 | import heapq
|
| 2 |
|
| 3 | class Solution:
|
| 4 | def kClosest(self, points: list[list[int]], k: int) -> list[list[int]]:
|
| 5 | min_heap = []
|
| 6 | for x, y in points:
|
| 7 | dist = (x ** 2) + (y ** 2)
|
| 8 | min_heap.append([dist, x, y])
|
| 9 |
|
| 10 | heapq.heapify(min_heap)
|
| 11 |
|
| 12 | res = []
|
| 13 | while k > 0:
|
| 14 | dist, x, y = heapq.heappop(min_heap)
|
| 15 | res.append([x, y])
|
| 16 | k -= 1
|
| 17 |
|
| 18 | return res |
Step-by-Step Solution
Calculate Squared Distances and Build Min-Heap
| 5 | min_heap = []
|
| 6 | for x, y in points:
|
| 7 | dist = (x ** 2) + (y ** 2)
|
| 8 | min_heap.append([dist, x, y])
|
| 10 | heapq.heapify(min_heap)
|
Objective
To transform the input points into a min-heap keyed by squared distance to the origin for efficient retrieval.
Key Insight
Calculating squared distances avoids the computational cost of square roots while preserving relative order. Building a list of [distance, x, y] tuples allows the heap to prioritize points by distance. Using heapq.heapify converts the list into a valid min-heap in linear time, enabling efficient extraction of the closest points.
Interview Quick-Check
Core Logic
Calculate squared distances for all points and heapify the list to prepare for efficient minimum extraction.
Common Pitfalls & Bugs
Avoid computing the actual Euclidean distance with square roots, as squared distances suffice and are cheaper to compute.
Complexity
Heapifying the entire list takes O(n) time, which is more efficient than inserting elements one by one.
Extract K Closest Points from the Min-Heap
To retrieve the k points with the smallest distances by popping from the min-heap.
Return the List of K Closest Points
To output the collected k closest points as the final result.
2 more steps with full analysis available on Pro.
Line Analysis
This solution has 2 Critical lines interviewers watch for.
heapq.heapify(min_heap)Transform the list into a min-heap in-place.
Heapifying in O(n) time is critical for efficiency, as it avoids the higher cost of inserting elements one by one into the heap.
dist, x, y = heapq.heappop(min_heap)Pop the point with the smallest distance from the heap.
This line is the core algorithmic move that leverages the heap's property to efficiently find the next closest point without sorting the entire list.
Full line-by-line criticality + rationale for all 11 lines available on Pro.
Test Your Understanding
Why does using a min-heap improve efficiency over sorting all points when k is small?
See the answer with Pro.
Related Problems
Heap / Priority Queue pattern
Don't just read it. Drill it.
Reconstruct K Closest Points to Origin from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the K Closest Points to Origin drill