Problem Breakdown
We are given an array of points where each point is [x, y], and we need to return exactly k points closest to the origin (0, 0).
Key Inputs & Outputs:
- Input: A list of lists (2D coordinates), integer
k. - Output: List containing exactly
kcoordinate pairs. Order does not matter.
Implicit Constraints & Optimizations:
- Distance Metric: Euclidean distance involves a square root (
√(x² + y²)). Since we only need to compare distances, using squared Euclidean distance(x*x + y*y)is sufficient and avoids floating-point precision issues/costs ofsqrt. - Order Independence: The result order does not matter, allowing us to discard points once they are no longer in the top
kclosest set. - Constraints: Coordinates range from
-10^4to10^4, array length up to10^4. Squared distances fit within standard integer types (Python handles large integers automatically).
Intuition
A brute-force approach would be to calculate the distance for every point, sort all points by this metric, and slice off the first k. This takes time. While acceptable given constraints (), it is not optimal if we only care about finding a subset of size K where K << N.
Key Insight: We are looking for the “Top K” smallest elements in an unsorted collection. This pattern strongly suggests using a Heap (Priority Queue).
- Using a Min-Heap to store all points would require popping until we have
k, which is inefficient (). - To optimize, we can maintain a heap of size exactly
K. As we iterate through the input:- Add current point’s distance info to our collection (heap).
- If the collection exceeds size
k, remove the element with the largest distance from this subset.
- Python Specifics: Python’s standard library provides a Min-Heap (
heapq). To simulate removing the “farthest” point when we exceed capacity, we store negative distances in our heap (Max-Heap behavior using negation). The smallest value popped will be the most negative number, corresponding to the largest positive distance.
Approach
- Initialize an empty list
heapwhich acts as a priority queue. - Iterate through each point
(x, y)in the input array:- Calculate squared Euclidean distance:
dist = x*x + y*y. - Push tuple
(-dist, x, y)onto the heap. We negatedistso that Python’s min-heap pops the largest actual distances first when we need to trim our set of closest points.
- Calculate squared Euclidean distance:
- Check if the length of the heap exceeds
k:- If yes: Perform a pop operation (
heappop). This removes the point with the largest distance (worst candidate) from our current top-k selection, keeping only the closer ones.
- If yes: Perform a pop operation (
- After iterating through all points, convert the remaining tuples in the heap back into lists of coordinates and return them.
Complexity Analysis
- Time Complexity: where
Nis the number of points andKis the target count. We iterate once () and perform a push/pop operation on a heap of size at mostk. Each heap operation takes logarithmic time relative to its current size ($\le k$).- Note: If we used sorting, it would be . Since , the Heap approach is theoretically faster when
Kis small. Given Python’s Timsort efficiency (), both pass easily, but this demonstrates algorithmic optimization skills required for senior roles.
- Note: If we used sorting, it would be . Since , the Heap approach is theoretically faster when
- Space Complexity: to store the heap elements (excluding input storage).
Solution
import heapq
def kClosest(points: list[list[int]], k: int) -> list[list[int]]:
# Use a min-heap but store negative distances to simulate max-heap behavior.
# We want to evict the point with the largest distance when size > k.
heap = []
for x, y in points:
dist_sq = x * x + y * y
# Push (-dist, x, y) so that heappop removes the farthest point (smallest negative value)
heapq.heappush(heap, (-dist_sq, x, y))
# Maintain heap size at k. If larger, remove the worst candidate (farthest).
if len(heap) > k:
heapq.heappop(heap)
# Extract coordinates from tuples and convert to list format as per return type requirements
result = [list(point[1:]) for point in heap]
return result
Edge Cases Handled
- Empty Input: The loop simply won’t execute; returns empty list. Though constraints guarantee
points.length >= k. k == len(points): The heap grows to full size and never pops, returning all points (correct).- Negative Coordinates: Squared distance calculation (
x*x) handles negative signs correctly without special logic. - Duplicate Distances: If multiple points have the exact same squared distance,
heapqmaintains stability based on insertion order or tuple comparison of subsequent elements; any valid subset is accepted by problem statement (“answer in any order”).