Loading
Loading
An electric scooter sits at the origin of a city grid. The map lists charging stations by their (x, y) coordinates, and the app wants to suggest the k closest ones.
Distance is ordinary straight-line distance, so comparing x² + y² is enough. Return the indices of the k nearest stations, nearest first. When two stations are equally far, the one with the smaller index comes first.
points = [[3, 4], [1, -1], [-2, 2], [0, 5]], k = 2squared distances25, 2, 8, 25heap = {0:25}max-heap of the 2 nearest so farheap = {0:25, 1:2}station 1 addedheap = {2:8, 1:2}station 2 added; size 3, so the farthest (station 0) is evictedheap = {2:8, 1:2}station 3 is at 25, worse than the root, evicted at once[1, 2]sort the survivors by (distance, index)[1, 2]Sign in to keep a note here. It is free, and nobody else can see it.
Sign inExample 1
| 0 | 3 | 4 |
|---|---|---|
| 1 | 1 | -1 |
| 2 | -2 | 2 |
| 3 | 0 | 5 |
Squared distances are 25, 2, 8 and 25. The two nearest are station 1 (2) and station 2 (8).
Sign in to open hints.
Struggling is where the learning happens. Open this once you have genuinely tried, or once the hints have run out.
O(n log k) time · O(k) space
Input. Run your code to watch it work on this input, one line at a time.
| 0 | 3 | 4 |
|---|---|---|
| 1 | 1 | -1 |
| 2 | -2 | 2 |
| 3 | 0 | 5 |
Running code is turned off on this deployment. You can still read the problem, write code, use hints and the visualizer.
Tab moves focus out of the editor. Press Ctrl+M to let Tab indent instead.
No results yet
Run your code against the sample tests, or submit to run the full suite.
Example 2
| 0 | 2 | 0 |
|---|---|---|
| 1 | 0 | -2 |
| 2 | 1 | 1 |
Station 2 is nearest (2). Stations 0 and 1 tie at 4; the smaller index wins the last place.