K Closest Points to Origin

You are given a list of points on a plane, points, where each point is [x, y], and an integer k. Return the k points that are closest to the origin (0, 0) by ordinary straight-line (Euclidean) distance, √(x2 + y2).

The points may be returned in any order. The tests guarantee the answer is unique: the k-th closest point is strictly closer than the (k+1)-th, so there is never a tie at the cut-off.

Example 1

Example 2

Example 3

Constraints

• 1 <= k <= points.length <= 104
• -104 <= x, y <= 104
• The set of k closest points is unique.

Pattern Path · Heaps & Top-K · problem 103 of 169

Start simple

Sort every point by its squared distance and return the first k: O(n log n) time, O(n) space for the sorted copy.

The key idea

You need the k smallest distances, not a full ranking, so keep a running "best k so far" and update it cheaply.

Store the current candidates in a max-heap keyed by squared distance (squaring preserves order, so no square roots are needed). Its top is always the worst of the current k. For each new point:

• If the heap has fewer than k points, push it.
• Otherwise, if the new point is closer than the top, pop the top and push the new point. If it is not closer, it can never be in the answer, because k better points are already known.

After the scan the heap holds exactly the k closest points. Each heap operation costs O(log k), so the total is O(n log k), which beats sorting when k is much smaller than n, and memory stays at O(k). Python's heapq is a min-heap, so store negated distances to simulate a max-heap.

For average O(n) time, quickselect can partition the points around the k-th distance instead.

Complexity

• Time: O(n log k)
• Space: O(k)

Python

class Solution:
    def kClosest(self, points, k):
        heap = []  # max-heap via negated squared distance: (-dist, x, y)
        for x, y in points:
            dist = x * x + y * y
            if len(heap) < k:
                heapq.heappush(heap, (-dist, x, y))
            elif dist < -heap[0][0]:  # closer than the farthest kept point
                heapq.heapreplace(heap, (-dist, x, y))
        return [[x, y] for _, x, y in heap]

JavaScript

var kClosest = function(points, k) {
  const dist = ([x, y]) => x * x + y * y;
  const heap = []; // max-heap of points, ordered by distance

  const swap = (i, j) => { [heap[i], heap[j]] = [heap[j], heap[i]]; };
  const siftUp = (i) => {
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (dist(heap[parent]) >= dist(heap[i])) break;
      swap(i, parent);
      i = parent;
    }
  };
  const siftDown = (i) => {
    while (true) {
      const l = 2 * i + 1, r = l + 1;
      let largest = i;
      if (l < heap.length && dist(heap[l]) > dist(heap[largest])) largest = l;
      if (r < heap.length && dist(heap[r]) > dist(heap[largest])) largest = r;
      if (largest === i) break;
      swap(i, largest);
      i = largest;
    }
  };

  for (const p of points) {
    if (heap.length < k) {
      heap.push(p);
      siftUp(heap.length - 1);
    } else if (dist(p) < dist(heap[0])) { // closer than the farthest kept point
      heap[0] = p;
      siftDown(0);
    }
  }
  return heap;
};

What the interviewer is checking

It tests the top-k pattern: choosing a bounded heap of the right polarity (a max-heap to find minimums), and knowing when quickselect or sorting is a better trade-off.

Mistakes to avoid

• Using a min-heap of all n points, which works but costs O(n log n) and O(n) memory.
• Keeping a min-heap of size k, which evicts the closest point instead of the farthest.
• Computing square roots and comparing floats unnecessarily.
• Squared coordinates can overflow 32-bit integers in some languages if the range grows.

Follow-ups to expect

• Can you get average linear time? (Quickselect on squared distance.)
• What if points arrive as an endless stream? (Keep the size-k max-heap.)
• What if you need the k closest to an arbitrary point? (Shift coordinates; same method.)

In real software

Finding the nearest drivers, stores or hotels to a user, or the top-k most similar items in a recommendation system, is the same bounded-heap selection.

Practice next