Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns

Solution: K Closest Points to Origin

Understand how to identify the k points closest to the origin by implementing a max-heap data structure. Learn to optimize the solution by comparing squared distances, reducing time complexity to O(n log k). This lesson guides you through the step-by-step process for organizing points and extracting the nearest ones efficiently.

We'll cover the following...

Statement

You are given an array of points where each element points[i] =[xi,yi]= [x_i, y_i] represents a point on the X-Y plane, along with an integer k. Your task is to find and return the k points that are closest to the origin [0,0][0, 0].

The distance between two points on the X-Y plane is measured using Euclidean distance, which is calculated as:

Note: You can return the result in any order. The answer is guaranteed to be unique, except for the order in which points appear.

Constraints:

  • 1≤1 \leq k ≤\leq ...