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

Solution: K Closest Points to Origin

Discover how to identify the k closest points to the origin in a 2D plane by applying max-heap data structures and squared Euclidean distance. Learn to optimize your solution's time complexity from O(n log n) to O(n log k) and understand the implementation details for efficient coding interview preparation.

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 ...