K Closest Points to Origin

Heaps & Top-K, problem 4 of 7

K Closest Points to Origin

Medium

LC #973

max-heaptop-kgeometry

Not attempted yet

Given a list of points [x, y] on a plane and an integer k, return the k points closest to the origin (0, 0) by Euclidean distance. Return them in any order. The answer is guaranteed to be unique.

Example 1

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

Distances²: 1+9 = 10 and 4+4 = 8, so [-2,2] is closer.

Example 2

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

Constraints

  • 1 <= k <= len(points) <= 2 * 10^4
  • -10^5 <= x, y <= 10^5

Python

Loading draft…

Test results

8 tests available

No results yet

Run tests your code against the examples; Submit runs the hidden tests too.

2 examples, 6 hidden

Run examples, then submit all tests.