Medium

K Closest Points to Origin

039

Given points [x, y], return the k closest points to the origin sorted lexicographically.

EXAMPLES

Example 1

Input
{
  "points": [
    [
      1,
      3
    ],
    [
      -2,
      2
    ]
  ],
  "k": 1
}

Output
[
  [
    -2,
    2
  ]
]

FUNCTION SHAPE

points: intMatrixk: int→intMatrix

SOLUTION NOTE

We need bottom K (smallest distances), so we use a max heap (negate values). The heap keeps the k closest points.

Reveal reference solution +

pythonREFERENCE

# Solution 1: Sort
def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
    # Trick: compare squared euclidean distance (x^2 is monotonic)
    # This saves compute because square roots are expensive
    points.sort(key=lambda x: x[0]*x[0] + x[1]*x[1])
    return points[:k]

# Solution 2: Max heap of size k (for bottom K, use max heap)
def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
    heap = []
    for x, y in points:
        heappush(heap, (-(x*x + y*y), x, y))
        if len(heap) == k + 1:
            heappop(heap)
    return [[x, y] for _, x, y in heap]

TimeO(n log k)

SpaceO(k)

Open on LeetCode ↗