> [!META]- Inline Metadata
> [tags:: #career #concepts/programming/heap ]
> [project group:: Neetcode 150]
> [difficulty:: medium]
> [status:: done]
> [link:: https://leetcode.com/problems/k-closest-points-to-origin]
> [up:: [[Leetcode MOC]]]
## Problem
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 (i.e., `√(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).
**Example 1:**
**Input:** points = [[1,3],[-2,2]], k = 1
**Output:** [[-2,2]]
**Explanation:**
The distance between (1, 3) and the origin is sqrt(10).
The distance between (-2, 2) and the origin is sqrt(8).
Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.
We only want the closest k = 1 points from the origin, so the answer is just [[-2,2]].
**Example 2:**
**Input:** points = [[3,3],[5,-1],[-2,4]], k = 2
**Output:** [[3,3],[-2,4]]
**Explanation:** The answer [[-2,4],[3,3]] would also be accepted.
**Constraints:**
- `1 <= k <= points.length <= 10^4`
- `-10^4 <= xi, yi <= 10^4`
## Solution
### Mine
#### Python
```python
class Solution:
def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
distances = [((point[0]**2 + point[1]**2)**0.5, point) for point in points]
if k == 1:
return [min(distances)[1]]
heapq.heapify(distances)
return [heappop(distances)[1] for _ in range(k)]
```
First, I used a list comprehension to generate the list of distance, point tuples. Python's `heapq` will sort on the first item in each tuple, and use the following items as a tiebreaker if needed. Because order doesn't matter for the problem, this is fine.
For `k==1`, we just return the `min` since that's faster than setting up the heap and popping off of it.
Otherwise, we heapify the `distances` list, then use a list comprehension to call `heappop` `k` times. We use this instead of `heapq.nsmallest()` because for large lists, `nsmallest()` can get slow.
#### Rust
### LC's
## Things I Learned
## Scratchpad
My idea here is to use a min-heap with each distance, then call `heapq.nsmallest()`. The trick will be associating the distances with each coordinate pair, but the `heapq` does accept tuples, so we could push something like `(distance, coordinate_pair)`. If `k = 1`, we'll calculate the distance and