Skip to main content

23. K Closest Points to Origin

mediumAsked at Meta

Find the k nearest geographic points to a center — Meta's location-based friend discovery and venue recommendations run exactly this top-K proximity filter at massive scale every second across billions of location signals.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given an array of points where points[i] = [xi, yi] and an integer k, return the k closest points to the origin (0, 0). The distance is the Euclidean distance. The answer may be returned in any order.

Constraints

  • 1 <= k <= points.length <= 10^4
  • -10^4 <= xi, yi <= 10^4

Examples

Example 1

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

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

Example 2

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

Approaches

1. Sort

Compute squared Euclidean distance for each point, sort ascending, return first k. Simple but uses more time than necessary.

Time
O(n log n)
Space
O(n)
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 k nearest points seen so far; evict the farthest when the heap exceeds k. Optimal when k is much smaller than n — avoids sorting the entire array.

Time
O(n log k)
Space
O(k)
function kClosest(points, k) {
  const dist = p => p[0]**2 + p[1]**2;
  // Simulate max-heap keeping k smallest
  const heap = [];
  for (const p of points) {
    heap.push(p);
    heap.sort((a, b) => dist(b) - dist(a));
    if (heap.length > k) heap.shift();
  }
  return heap;
}

Tradeoff:

Meta-specific tips

Meta interviewers often follow up with 'What if new points stream in continuously?' — pivot to the max-heap approach which handles streaming naturally. They also ask about the QuickSelect O(n) average-case alternative. Avoid computing sqrt — compare squared distances to keep it integer-safe and faster.

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 Meta interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →