Approach 1: Sort
Sort the points by distance, then take the closest K points.
There are two variants.
In Java, we find the K-th distance by creating an array of distances and then sorting them. After, we select all the points with distance less than or equal to this K-th distance.
In Python, we sort by a custom key function - namely, the distance to the origin. Afterwards, we return the first K elements of the list.
Time Complexity: , where is the length of
Space Complexity: .
Approach 2: Divide and Conquer
We want an algorithm faster than . Clearly, the only way to do this is to use the fact that the K elements returned can be in any order -- otherwise we would be sorting which is at least .
Say we choose some random element
x = A[i] and split the array into two buckets: one bucket of all the elements less than
x, and another bucket of all the elements greater than or equal to
x. This is known as "quickselecting by a pivot
The idea is that if we quickselect by some pivot, on average in linear time we'll reduce the problem to a problem of half the size.
Let's do the
work(i, j, K) of partially sorting the subarray
(points[i], points[i+1], ..., points[j]) so that the smallest
K elements of this subarray occur in the first
(i, i+1, ..., i+K-1).
First, we quickselect by a random pivot element from the subarray. To do this in place, we have two pointers
j, and move these pointers to the elements that are in the wrong bucket -- then, we swap these elements.
After, we have two buckets
[oi, i] and
[i+1, oj], where
(oi, oj) are the original
(i, j) values when calling
work(i, j, K). Say the first bucket has
10 items and the second bucket has
15 items. If we were trying to partially sort say,
K = 5 items, then we only need to partially sort the first bucket:
work(oi, i, 5). Otherwise, if we were trying to partially sort say,
K = 17 items, then the first
10 items are already partially sorted, and we only need to partially sort the next 7 items:
work(i+1, oj, 7).
Time Complexity: in average case complexity, where is the length of
Space Complexity: .
Analysis written by: @awice.