Return the K Closest Points with Deterministic Ties
Company: Asana
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
# Return the K Closest Points with Deterministic Ties
Implement `k_closest(points, target, k)`. Each point and the target are integer pairs. Return exactly `k` input points with smallest squared Euclidean distance to the target, ordered by `(distance, x, y, original_index)` so ties have one canonical result.
Constraints: `0 <= k <= len(points) <= 200000`; coordinates are integers between `-10^6` and `10^6`, so every squared distance is at most `8 * 10^12` and is exact in all four languages. Do not use square roots. Aim for `O(n log k)` time and `O(k)` auxiliary space.
```hint Make ties observable
Include duplicate coordinates and different points at equal distance so the required ordering is exercised.
```
Quick Answer: Implement `k_closest(points, target, k)`. Work through the function contract, boundary cases, correctness argument, and time and space complexity expected in a production-quality solution.
Given integer coordinate pairs `points`, an integer pair `target`, and `k`, return exactly `k` input points with the smallest squared Euclidean distance to the target. Order the result by `(distance, x, y, original_index)`, where `distance` is squared distance. Duplicate coordinates are distinct input points. Do not use square roots.
Constraints
- 0 <= k <= len(points) <= 200000.
- Every point and target is an integer pair with each coordinate from -10^6 through 10^6.
- Squared distances are at most 8 * 10^12 and are exact in every supported language.
- The exact output order is (squared distance, x, y, original index).
Examples
Input: ([], [0, 0], 0)
Expected Output: []
Explanation: An empty input with k zero returns an empty list.
Input: ([[3, -4]], [0, 0], 1)
Expected Output: [[3, -4]]
Explanation: A singleton is returned unchanged.
Hints
- Test k = 0, k = 1, and k equal to the number of input points.
- Include duplicate coordinates and different points at the same squared distance to expose every tie field.
- Exercise a point equal to the target, negative coordinates, and both coordinate limits.