Solution
Approach 1: Sort
Intuition
Sort the points by distance, then take the closest K points.
Algorithm
There are two variants.
In Java, we find the Kth 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 Kth 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.
Complexity Analysis

Time Complexity: , where is the length of
points
. 
Space Complexity: .
Approach 2: Divide and Conquer
Intuition
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 x
".
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.
Algorithm
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 K
positions (i, i+1, ..., i+K1)
.
First, we quickselect by a random pivot element from the subarray. To do this in place, we have two pointers i
and 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)
.
Complexity Analysis

Time Complexity: in average case complexity, where is the length of
points
. 
Space Complexity: .
Analysis written by: @awice.