Problem 🤔

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

Note

• (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 1

Input: points = [[1,3],[-2,2]], K = 1

Output: [[-2,2]]

Explanation

The distance between (1, 3) and the origin is sqrt(10). The distance between (-2, 2) and the origin is sqrt(8). Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin. We only want the closest K = 1 points from the origin, so the answer is just [[-2,2]].

Example 2

Input: points = [[3,3],[5,-1],[-2,4]], K = 2

Output: [[3,3],[-2,4]]

(The answer [[-2,4],[3,3]] would also be accepted.)

Constraints

• 1 <= K <= points.length <= 10000
• -10000 < points[i][0] < 10000
• -10000 < points[i][1] < 10000

Real World Applications 🌎

Finding K closest points is common. I have seen this most often in the context of running clustering algorithms and deciding which data points belong to which cluster or running other algos such as K Nearest Neighbors.

The Finer Details 🔎

Whenever we need to keep track of k closest anything we need to think of a scalable way to do this! Declaring k variables would be messy since k is given to us during runtime. A perfect data structure for something like this would be a priority queue, also known as a heap! We could constrain the heap to hold k elements maximum at any given moment. Let’s try that!

Solution 💡 - Using a Heap

Takeaways 🎉🥳

Needing to keep track of k elements should always hint at using a heap! Keep this trick in mind :)

Complexity Analysis 🧮

Time complexity

O(n*log(k))

To build the heap we iterate through n points. For every point we perform and insert (or pop) on the heap with a complexity of log(k).

Space complexity

O(k)

Heap holds k elements.

Resources 📚 💻

Leetcode