Hello. We are given that the array A is sorted.

1. If you spend a bit of time, you can understand that Fk(x) denotes the distance of (k+1)th nearest point from x.

2. Observe that nearest points of x are chronological neighbours of x. For example, if we are looking at the Nth nearest point of X, and we have a list of (N-1) nearest points with us, some on left of x and some on right of x, then the required point will either be to the immediate left of an existing point, or immediate right of an existing point (i.e. no gaps). (Let know if you want a proof)

3. Therefore, by spending a little time, we can observe that (K+1) nearest points of any point x must correspond to a sliding window of size K+1 in the array.

4. Once that is established, we know that x can be chosen by us. What is the distance of x from each point in the sliding window? Note that it decreases till it reaches the nearest integer to x, and then starts increasing again. Therefore D_(k+1) (the required (k+1)th distance) must be the max of D1 and D2 where D1 is distance of x from the first element in the window and D2 is distance of x from last element in the window.

5. Now, we need to minimize this distance. You can observe that there is a tradeoff between these 2 distances D1 and D2. As we move x to the left, D1 decreases and D2 increases. (with D1+D2 =constant at all times). The minimum distance must occur at the middle.

Happy to elaborate on any of the numbered points that is not clear.

if we know that the best point have xl limit on the left and xr limit from the right and by limit I mean the limit of numbers that form the first k + 1 distances.

for example if the array is given (note that the array is given is sorted) 1 3 4 5 6 7 and k = 2 if we choose the point x to be 2 that mean the left limit is 1 and right limit is 4 from 1 to 4 those are the numbers that form the first k+1 distances after sorting as we can see 1 — 2, 3 — 2, 4 — 2 which is 1, 1, 2, and we only care about first k + 1 distances because we want to make k+1 th minimal.

now suppose we know what is xl (left limit ) and what is xr so it's greedy to choose x as (xr + xl ) / 2 now let's try every array[i] as the left limit then we are forced to make array[i + k] the right limit and we take the best x from every array[i] we try to take as the left limit.