27. K Closest Points to Origin

mediumAsked at Instacart

Find the k nearest pickup points to a warehouse — Instacart's last-mile team uses this to assign the closest available shoppers to a new order when multiple drivers are in range.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-26

Problem

Given an array of points where points[i] = [x_i, y_i] on a 2D plane and an integer k, return the k closest points to the origin (0, 0). The distance is the Euclidean distance. You may return the answer in any order; it is guaranteed to be unique.

Constraints

1 <= k <= points.length <= 10^4
-10^4 <= x_i, y_i <= 10^4

Examples

Example 1

Input

points = [[1,3],[-2,2]], k = 1

Output

[[-2,2]]

Explanation: Distance of [1,3] = sqrt(10); distance of [-2,2] = sqrt(8). [-2,2] is closer.

Example 2

Input

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

Output

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

Approaches

1. Sort by squared distance

Sort all points by x^2 + y^2 (no sqrt needed since we only compare) and return the first k.

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

function kClosest(points, k) {
  return points
    .sort((a, b) => (a[0] ** 2 + a[1] ** 2) - (b[0] ** 2 + b[1] ** 2))
    .slice(0, k);
}

Tradeoff:

2. Max-heap of size k

Maintain a max-heap of the k closest points seen so far. When a new point is closer than the farthest in the heap, evict the farthest and insert the new one. O(n log k) — better than full sort when k << n.

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

function kClosest(points, k) {
  // Max-heap: keep the k smallest distances, drop anything larger
  const dist = p => p[0] ** 2 + p[1] ** 2;

  // Simulated max-heap with sorted array (declare real MaxHeap in interview)
  const heap = [];

  function heapPush(p) {
    heap.push(p);
    heap.sort((a, b) => dist(b) - dist(a)); // largest dist at front
  }
  function heapPop() { return heap.shift(); }

  for (const p of points) {
    heapPush(p);
    if (heap.length > k) heapPop();
  }

  return heap;
}

Tradeoff:

Instacart-specific tips

Instacart's dispatch algorithm needs the k nearest drivers to a new order in real time. The sort approach is fine at small scale, but the max-heap variant is the answer that signals production thinking: it streams over the point set and never holds more than k entries in memory — critical when the driver list is continuously updated and you can't afford a full re-sort on every new order.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill K Closest Points to Origin and other Instacart interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →