Reference: LeetCode EPI 10.4
Difficulty: Medium

Problem

We have a list of points on the plane. Find the K closest points to the origin (0, 0).

(Here, the distance between two points on a plane is the Euclidean distance.)

You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in.)

Example:

Analysis

Sorting

First let’s define the distance calculation method.

Time: $O(N\log{N})$
Space: $O(K)$

Max Heap

Since we want K smallest elements, we use a K-size max heap. We repeatedly add elements to the heap. When the size is greater than K, we remove the largest element.

We can also write the comparator like this.

Time: $O(N\log{K})$
Space: $O(K)$

Quick Select

The idea of Quick Select is to find the K-th element, make elements on the left less than the K-th element, and make elements on the right greater than the K-th element.

We randomly pick an element. If it turns out to be the actual K-th element, we can stop at the first step. So it depends on luck.

After swapping, if this element turns out to be an element to the left of the K-th element, we recursively solve the subproblem for the right subarray; if it is to the right, we solve it for the left subarray.

Note: To make code cleaner, after we pick the random index, we place the element at the beginning before doing swapping.

Time: $O(N)$ in average; $O(N^2)$ in the worst case.
Space: $O(K)$

Comment
Junhao Wang
Hi, I was a master student at USC studying Computer Science.