Loading page…
Practice problem · medium
A rider opens a ride-hailing app. The app finds the k drivers closest to the rider and offers the ride to them first.
The city is a flat grid, and the rider stands at the point (0, 0). Up to 100,000 drivers are online, so the app should not sort them all only to find a handful.
Write nearest_drivers(xs, ys, k).
i is at the point (xs[i], ys[i]). Drivers are numbered from 0.(0, 0). You can compare distances by the squared distance, x * x + y * y, so no square root is needed.k nearest drivers, nearest first. When two drivers are equally near, the smaller number comes first.Input: xs = [3, 1, -2, 5], ys = [3, 0, -2, -1], k = 2
Output: [1, 2]| Driver | Squared distance | Heap of the 2 nearest after | Dropped |
|---|---|---|---|
| 0 | 18 | 0 | |
| 1 | 1 | 0, 1 | |
| 2 | 8 | 1, 2 | 0 (18 is the farthest) |
| 3 | 26 | 1, 2 | 3 (26 is the farthest) |
Drivers 1 and 2 are the two nearest, with squared distances 1 and 8. Driver 1 comes first.
Input: xs = [2, -2], ys = [0, 0], k = 1
Output: [0]Both drivers are 2 away, so the squared distance is 4 for each. The smaller number, driver 0, comes first.
Input: xs = [0], ys = [0], k = 1
Output: [0]One driver stands exactly at the rider. The distance is 0, and the answer is that driver.
1 ≤ length of xs = length of ys ≤ 10^5-10^4 ≤ xs[i], ys[i] ≤ 10^41 ≤ k ≤ length of xsComputing every driver's distance once is fine: 100,000 steps. The expensive part is ranking. Sorting all of them costs about 1.7 million steps, which is fine here, but it grows faster than the work you need.
A heap of size k ranks only what matters: each driver costs about log k steps, and the memory stays at k drivers. The squared distance can reach 200,000,000, which still fits a 32-bit integer, but packing it with the driver number does not, so use 64 bits.
nearest_drivers · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.