K Closest Points to Origin

Explanation & Solution

Description

Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).

The distance between two points on the X-Y plane is the Euclidean distance: √(x² + y²).

You may return the answer sorted by distance (closest first). If two points have the same distance, sort by x-coordinate, then by y-coordinate.

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

Output: [[-2,2]]

Explanation: The distance from (1, 3) to the origin is √10. The distance from (-2, 2) to the origin is √8. Since √8 < √10, (-2, 2) is the closest point.

Constraints

1 <= k <= points.length <= 10⁴
-10⁴ <= xi, yi <= 10⁴

Approach

Top K Elements pattern

1. Understand the Distance Formula

The Euclidean distance from a point (x, y) to the origin is √(x² + y²)
Since we only need to compare distances, we can skip the square root and compare x² + y² directly
This avoids floating-point precision issues

2. Sort by Distance

Sort the entire points array by each point's squared distance to the origin
Use a[0] * a[0] + a[1] * a[1] as the sort key
For tie-breaking, sort by x-coordinate first, then y-coordinate to ensure deterministic output

3. Take the First K Points

After sorting, the first k elements are the k closest points
Use points.slice(0, k) to extract them

4. Return the Result

The returned array contains exactly k points, sorted from closest to farthest

Key Insight

Sorting the array by squared distance gives us the k closest points in O(n log n) time
We compare squared distances instead of actual distances to avoid unnecessary square root computations
An alternative optimal approach uses a max-heap of size k for O(n log k) time, which is better when k << n

Time

O(n log n) where n is the number of points

Space

O(1) extra space (sorting is in-place, ignoring sort's internal stack)

Solution Code

Kth Largest Element in a Stream

Top K Frequent Words