881. The k Nearest, Ordered by Distance
Given n values IN ARBITRARY ORDER, a count k and a target x, print the
k values closest to x, ordered by increasing distance |a[i] - x|. Where
two values are the same distance away, the SMALLER value comes first.
Read those two conditions carefully, because they are what separates this from problem 640: the input is not sorted, and the answer is ordered by DISTANCE rather than by value.
n = 6, k = 3, x = 5, values 1 4 9 5 12 6 -> 5 4 6
n = 4, k = 2, x = 0, values -3 3 -3 3 -> -3 -3
n = 7, k = 3, x = 0, values -3 -2 -1 0 1 2 3 -> 0 -1 1
In the first row the distances are 4, 1, 4, 0, 7, 1. The three smallest are
0 (the value 5), then two values at distance 1, which are 4 and 6, and 4 comes
first because it is the smaller value.
The third row shows why the tie rule matters: -1 and 1 are both one away
from 0, and without a rule two correct programs would print them in different
orders.
## What most people try first
Sorting the whole list by distance. Correct, O(n log n), and it orders
n values to report k.
The other attempt is computing a SQUARED distance to avoid the absolute value.
That is a habit picked up from geometry problems and it is wrong here: it
changes the tie rule, because (-1)^2 and 1^2 are both 1 but so are the
distances, and worse, squaring a difference of 2 * 10^9 produces
4 * 10^18, which is near the 64-bit limit of about 9.2 * 10^18 for no
reason at all. In one dimension the absolute difference IS the distance.
## A heap over a DERIVED key
The heap must order values by something that is not the value: the distance. So each heap entry carries the KEY it is ordered by and the value it stands for, as a pair:
key(v) = ( |v - x| , v )
Comparing pairs compares the distance first and the value second, which is exactly the tie rule, written once, in one place.
Since the k NEAREST are wanted, the survivor to throw away is the FURTHEST
of them, so the heap must report the largest key. That is a max-heap on
(|v - x|, v).
h = empty max-heap ordered by ( |v - x| , v )
for each value v:
if size(h) < k: push v
else if key(v) < key(top(h)):
pop, then push v
sort the survivors by key, increasing, and print their values
## Why the pair, and not two heaps or a second pass
A common half-solution keeps a heap of distances only, then has to search the
input again to find which value produced a distance. That second search is
O(n) per answer and it cannot break ties, because two different values can
share a distance. Storing the value alongside its key makes both problems
vanish, and it is the single most transferable idea in this block: a heap
can be ordered by anything you can compute, as long as you carry the answer
along with the key.
## What is NOT an overflow here
The difference |a[i] - x| is at most 2 * 10^9, and it is worth being
exact about this because it is the most commonly mis-stated magnitude in this
whole area. The largest signed 32-bit integer is 2147483647, and
2000000000 is smaller than that, so the distance FITS. The intermediate is worth checking separately, because a difference can be negative
where a distance cannot: computed as (-10^9) - (10^9) it is -2 * 10^9, and the most
negative signed 32-bit value is -2147483648, so that fits too. There is no overflow in this problem, and the only way to create one is
to square the difference for no reason.
## The boundary that breaks a careless implementation
The tie rule has to reach the OUTPUT ordering as well as the eviction test. A program that evicts correctly but then sorts the survivors by distance alone prints tied values in whatever order the heap happened to leave them, which is not reproducible.
## What #640 does, and why neither of its moves is available here
Problem 640 asks the same closeness question with the same tie rule, and it is
a completely different algorithm because its list arrives SORTED. On a sorted
list the k closest values form a CONTIGUOUS block, so the whole problem
collapses to choosing where a window of width k starts, and two pointers
shrinking from both ends solve it in O(n - k) with no extra structure at
all.
Take the sorted guarantee away and that argument dies immediately. On
9 1 5 12 4 with x = 5 the three closest are 5, 4 and 1, which sit
at positions 2, 4 and 1, so the answer is not a run of the input and there is
no window to place.
The second difference is the OUTPUT. Problem 640 prints its block in
non-decreasing order of value, which the window hands over for free. Here the
order is by distance, so the answer alternates around x: on
-3 -2 -1 0 1 2 3 with x = 0 and k = 3 it is 0 -1 1, which is not
sorted by value at all and cannot be produced by sliding a window.
## Related problems
Problem 869 keeps the k points nearest the origin, where the key is a
squared distance in two dimensions and squaring is the RIGHT move because
there is no single-axis difference to take. Problem 880 is the same bounded
heap with the raw value as its own key, and comparing the two is the point:
the machinery is identical and only the key changes.
## Cost
Time O(n log k), plus O(k log k) to order the answer. Space O(k).
Constraints - `1 ≤ k ≤ n ≤ 200000` - `-1000000000 ≤ a[i] ≤ 1000000000` - `-1000000000 ≤ x ≤ 1000000000`
Input
The first line contains three integers n, k and x.
The second line contains n integers.
Output
Print the k closest values on one line, separated by single spaces, ordered by increasing distance from x with ties broken by the smaller value first. Print no other words.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.