mediumHeap / Priority Queue

K Closest Points to Origin

Find the k points closest to the origin. Sort the selected points by squared distance, then x, then y to break ties.

LeetCode ↗

Work through the cases

3 examples

Input notation

k on line 1, followed by one x y point per line. k is between 1 and the number of points.

Expected result

One selected x y pair per line.

Case 1

Input

Expected output

1 1
0 2

Case 2

Input

1
-1 0
2 0

Expected output

-1 0

Case 3

Input

1
0 0
3 4

Expected output

0 0

These notes use simplified input/output notation. The linked platform defines the method signature and judge format.

FROM IDEA TO IMPLEMENTATION

Understand the approach.

Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.

Find the k points closest to the origin. Sorting by Euclidean distance and taking the first k is O(nlog n), which is fine for n ≤ 10^4.

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

The time complexity is O(n log n), and the space complexity is O(log n). Here, n is the length of the array points.

class Solution {
    public int[][] kClosest(int[][] points, int k) {
        Arrays.sort(
            points, (p1, p2) -> Math.hypot(p1[0], p1[1]) - Math.hypot(p2[0], p2[1]) > 0 ? 1 : -1);
        return Arrays.copyOfRange(points, 0, k);
    }
}

Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.

Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.