Asked at

K Closest Points To Origin

Medium
VerifiedHeapSorting~22 min

Given an array of points on a plane and an integer k, return the k points closest to the origin (0, 0) by Euclidean distance.

Compare by squared distance to avoid floating point. The answer may be returned in any order, and ties between equally distant points may be broken arbitrarily.

The input arrives as a single object { points, k }.

Examples

in{ points: [[1, 3], [-2, 2]], k: 1 }
out[[-2, 2]]

Distance² is 10 vs 8; [-2, 2] is closer to the origin.

in{ points: [[3, 3], [5, -1], [-2, 4]], k: 2 }
out[[3, 3], [-2, 4]]

Distances² are 18, 26, 20; the two smallest are 18 and 20.

Constraints

  • 1 ≤ k ≤ points.length ≤ 10⁴
  • -10⁴ ≤ xᵢ, yᵢ ≤ 10⁴
  • Target: O(n log k) with a max-heap of size k.

Get help

🔑

Sign in to solve

Sign in to write, run, and submit your solution — and to pick up where your iOS flow left off.