Find the K Closest Points to the Origin
Company: Asana
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
# Find the K Closest Points to the Origin
Given `points`, a list of distinct integer coordinate pairs `[x, y]`, and an integer `k`, return the `k` points closest to the origin `(0, 0)`.
Distance is compared using `x*x + y*y`; do not take square roots. To make the result deterministic, rank points by `(squared_distance, x, y)` and return the selected points in that order.
Implement:
```python
def solve(points: list[list[int]], k: int) -> list[list[int]]:
...
```
## Constraints
- `1 <= k <= len(points) <= 200_000`
- `-10^9 <= x, y <= 10^9`
- The number of points can be much larger than `k`.
## Examples
```text
points = [[1, 3], [-2, 2], [2, -2]], k = 2
result = [[-2, 2], [2, -2]]
```
Both selected points have squared distance `8`, so their coordinates determine their order.
Quick Answer: Select the k points closest to the origin from a much larger set of distinct integer coordinates. Use squared distance and deterministic coordinate tie-breakers, then return the chosen points in ranked order.
Implement solve(points, k). points contains distinct integer pairs [x, y]. Return the k points closest to the origin, ranked and returned deterministically by (x*x + y*y, x, y). Do not take square roots. The number of points may be much larger than k.
Constraints
- 1 <= k <= len(points) <= 200,000
- Points are distinct integer coordinate pairs.
- -10^9 <= x, y <= 10^9
- Rank by (squared distance, x, y) and return points in that order.
Examples
Input: ([[1, 3], [-2, 2], [2, -2]], 2)
Expected Output: [[-2, 2], [2, -2]]
Explanation: Equal squared distance is broken by x then y.
Input: ([[0, 0]], 1)
Expected Output: [[0, 0]]
Explanation: The origin is the only point.
Hints
- Keep only the best k ranks in a max-heap whose root is the worst selected point.
- Use wide integer arithmetic for squared distances; JavaScript can compare them as BigInt.
- Sort the retained k points by the required rank before returning them.