K Closest Points 25 XP Medium

LeetCode Ctrl+Enter Run Ctrl+S Save

Given an array of points [x, y] on a plane, find the k closest points to the origin (0, 0).

points = [[1,3], [-2,2]], k = 1
# Distance of (1,3): sqrt(1² + 3²) = sqrt(10) ≈ 3.16
# Distance of (-2,2): sqrt(4 + 4) = sqrt(8) ≈ 2.83
# Closest: [[-2, 2]]

No need to compute actual square root — compare squared distances instead (preserves ordering):

Distance² = x² + y² (skip the sqrt for efficiency)
Use a max-heap of size k (negate distances for max-heap with Python's min-heap)
Process all points — keep only the k closest in the heap
Time: O(n log k), Space: O(k)

This is the same "top K" heap pattern as Kth Largest — just with a custom comparison value.

📋 Instructions

Implement `k_closest(points, k)` using a heap. Return the k closest points (order doesn't matter).

Use max-heap of size k. For each point, calculate dist = x*x + y*y. Push (-dist, point). If heap size > k, pop the farthest (largest negated distance). At end, extract points from heap.

🧪 Test Cases

Input

k_closest([[1,3],[-2,2]], 1)

Expected

[[-2, 2]]

Test case 1

Input

sorted(k_closest([[3,3],[5,-1],[-2,4]], 2))

Expected

[[-2, 4], [3, 3]]

Test case 2

← Previous Next Exercise →

main.py

Hi! I'm Rex 👋

Output

Ready. Press ▶ Run or Ctrl+Enter.

›