#973

Medium

LeetCode Problem Workspace

K Closest Points to Origin

Find the k closest points to the origin in a 2D plane using array operations and Euclidean distance calculations efficiently.

array math divide and conquer geometry sorting

Problem Statement

You are given an array of points where each point is represented as points[i] = [xi, yi] on a 2D plane. Your task is to return the k points closest to the origin (0, 0) based on Euclidean distance.

The Euclidean distance between a point (x, y) and the origin is calculated as sqrt(x x + y y). You may return the points in any order, and the answer is guaranteed to be unique with respect to point selection, though order can vary.

Examples

Example 1

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

Output: [[-2,2]]

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 <= 104
-104 <= xi, yi <= 104

Solution Approach

Max-Heap Approach

Use a max-heap of size k to store the closest points seen so far. Iterate through all points, and if a point is closer than the current farthest in the heap, replace it. This ensures we always maintain the k closest points efficiently.

Quickselect Partitioning

Apply the Quickselect algorithm to partially sort the points based on their squared Euclidean distance. Partition the array until the first k points are the closest, avoiding a full sort and reducing average time complexity.

Sorting Entire Array

Compute the squared distance for all points and sort the entire array based on these distances. Select the first k points after sorting. This is simpler to implement but may be slower for large inputs.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Max-heap maintains O(n log k) time and O(k) space. Quickselect achieves average O(n) time and O(1) extra space. Full sort requires O(n log n) time and O(n) space. Trade-offs involve implementation simplicity versus performance on large datasets.

What Interviewers Usually Probe

Does the candidate correctly compute Euclidean distances without using square roots unnecessarily?
Do they choose an optimal approach between heap, Quickselect, and full sort for k closest points?
Can they handle edge cases such as multiple points at the same distance or k equal to array length?

Common Pitfalls or Variants

Common pitfalls

Using sqrt unnecessarily, increasing computation time instead of comparing squared distances.
Not maintaining max-heap of size k, causing extra space usage or wrong points selection.
Failing to handle cases where multiple points have identical distances to the origin.

Follow-up variants

Find k farthest points from origin using a min-heap or modified Quickselect.
Find k closest points to an arbitrary point (x0, y0) instead of the origin.
Find k closest points in 3D space using Euclidean distance in three dimensions.

FAQ

What is the best approach for K Closest Points to Origin?

Using a max-heap for dynamic tracking of k closest points or Quickselect for partial sorting usually provides optimal performance.

Should I compute sqrt for Euclidean distance?

No, comparing squared distances is sufficient and avoids extra computation, maintaining correct order for selection.

Can the answer be in any order?

Yes, the points can be returned in any order as long as the closest k points are selected.

What is the time complexity for this problem?

Max-heap approach runs in O(n log k), Quickselect averages O(n), and full sort requires O(n log n).

How do I handle multiple points at the same distance?

Any subset of points at the same distance can be chosen as long as k points are returned; order does not matter.

terminal

Solution

Solution 1: Custom Sorting

We sort all points by their distance from the origin in ascending order, and then take the first $k$ points.

1

2

3

4

class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        points.sort(key=lambda p: hypot(p[0], p[1]))
        return points[:k]

Solution 2: Priority Queue (Max Heap)

We can use a priority queue (max heap) to maintain the $k$ closest points to the origin.

1

2

3

4

class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        points.sort(key=lambda p: hypot(p[0], p[1]))
        return points[:k]

Solution 3: Binary Search

We notice that as the distance increases, the number of points increases as well. There exists a critical value such that the number of points before this value is less than or equal to $k$, and the number of points after this value is greater than $k$.

1

2

3

4

class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        points.sort(key=lambda p: hypot(p[0], p[1]))
        return points[:k]

Continue Practicing

#347 top k frequent elements #215 kth largest element in an array #1738 find kth largest xor coordinate value