K Closest Points

35 min · kClosest()

A courier has thousands of map pins but room for only k nearby stops. The useful question isn't their full ranking—it's which pins survive the distance cutoff.

Each entry in points is [x, y]. Return the k points closest to the origin [0, 0], in any order.

You can compare points using squared distance, x² + y², which preserves the same near-to-far order as Euclidean distance without computing a square root.

A few ground rules:

Every point has exactly two coordinates.
All squared distances in one input are distinct, so the chosen set is unambiguous.
Coordinate order matters: [3, 1] and [1, 3] are different points.

Constraints

1 <= k <= points.length <= 100_000
-10_000 <= x, y <= 10_000
Every x² + y² is distinct within the input.
x² + y² <= 200_000_000, so squared distances fit in a signed 32-bit integer.

Hints

Skip the square root

If one nonnegative number has a smaller square than another, it also has the smaller distance. Compare x * x + y * y directly.

Find the waste in sorting

Sorting every point works, but you return only k of them. Can you keep a live set of k candidates instead of ordering all n points?

Put the worst candidate on top

Keep a size-k max-heap, a structure that exposes its farthest stored point. A new point replaces that root only when it's closer.

Follow-up

How would your choice change when k is almost points.length? Could partitioning find the cutoff without fully sorting the points?

Visible cases

Examples

Example 1

ready

Input: points = [ [ 1, 3 ], [ -2, 2 ] ] k = 1
Expected: [ [ -2, 2 ] ]
Why: squared distances are 10 and 8, so [-2, 2] is closer

Example 2

ready

Input: points = [ [ 3, 3 ], [ 5, -1 ], [ -2, 4 ] ] k = 2
Expected: [ [ 3, 3 ], [ -2, 4 ] ]
Why: squared distances 18 and 20 beat 26

Example 3

ready

Input: points = [ [ 0, 1 ], [ 2, 2 ], [ -3, 0 ] ] k = 2
Expected: [ [ 0, 1 ], [ 2, 2 ] ]
Why: the two smallest squared distances are 1 and 8

Interview signal

Asked at

AmazonMetaGoogle

Sort by distance

Attach each point to its squared distance, sort from nearest to farthest, and take the first k. The guarantee that distances are distinct removes any tie policy.

def k_closest(points: list[list[int]], k: int) -> list[list[int]]:
    ranked = sorted(points, key=lambda point: point[0] ** 2 + point[1] ** 2)
    return ranked[:k]

Square roots never enter the comparison. For nonnegative distances, ordering by x² + y² gives the same result.

Time O(n log n), space O(n) for the sorted list.

Size-k max-heap — keep only the winners

You need the nearest k, so keep exactly that many candidates. The root should be the worst current candidate: the farthest point among the kept set. Python exposes a min-heap, so a negative squared distance gives you max-heap behavior.

import heapq
 
 
def k_closest(points: list[list[int]], k: int) -> list[list[int]]:
    closest: list[tuple[int, int, int]] = []
    for x, y in points:
        distance = x * x + y * y
        heapq.heappush(closest, (-distance, x, y))
        if len(closest) > k:
            heapq.heappop(closest)
    return [[x, y] for _, x, y in closest]

After each point, the heap contains the nearest k points from the prefix you've read. When a closer point arrives, pushing it makes the heap too large and popping removes the farthest candidate. The final heap is the answer set; its internal order doesn't matter.

Time O(n log k), space O(k) for the candidate heap.

Loading editor

Console

ready to run

Ready to run.

3 cases are queued.

Visible testcase

Case 1

Arguments · JSON arraypoints: int[][] · k: int

Expected

[
  [
    -2,
    2
  ]
]

Run: visible + custom · Submit: full suite