Nearest Drones
MediumHeap / Priority Queue
Problem
A control tower sits at the origin (0, 0). Drone i is hovering at points[i] = [x, y]. Return the positions of the k drones closest to the tower by straight-line distance.
List them from nearest to farthest. If two drones are at the same distance, the one with the smaller index in points comes first.
Example 1
- Input:
- points = [[3, 4], [1, 1], [-2, 2], [5, 0]], k = 2
- Output:
- [[1, 1], [-2, 2]]
Squared distances: 25, 2, 8, 25. The two nearest are [1, 1] then [-2, 2].
Example 2
- Input:
- points = [[0, 2], [2, 0], [1, 1]], k = 2
- Output:
- [[1, 1], [0, 2]]
[0, 2] and [2, 0] tie at distance 2; index 0 wins the tie.
Constraints
- 1 ≤ k ≤ points.length ≤ 10^5
- -10^4 ≤ x, y ≤ 10^4
Hint
Show the first hint
You never need the actual square root to compare distances.
Walkthrough
How to approach it
01Clarify before coding
- Euclidean distance? Yes, and comparing squared distances gives the same order without floating point.
- How are ties broken? By original index, smaller first, which makes the answer unique.
- Output order? Nearest first.
02Brute force
Sort all indices by (x² + y², index) and return the first k points.
Cost: O(n log n) time and O(n) space: fine, but the heap version is O(n log k), which is the point of the exercise when k is much smaller than n.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.