28. K Closest Points to Origin

mediumAsked at Tripadvisor

Return the k nearest coordinates to a center point — Tripadvisor's geo-search engine applies this heap/quickselect pattern to surface the k nearest hotels, restaurants, or attractions to a traveler's current location.

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

Problem

Given an array of points where points[i] = [xi, yi] on a 2D plane, and an integer k, return the k closest points to the origin (0, 0). The distance is measured by Euclidean distance. The answer may be returned in any order. The answer is guaranteed to be unique (except for the order that it is in).

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] = sqrt(10); distance of [-2,2] = 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 by squared distance

Compute squared Euclidean distance for each point (avoid sqrt for performance), sort ascending, and slice the first k points.

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 (optimal for streaming)

Maintain a max-heap of the k closest points seen so far. For each new point, if it is closer than the heap's maximum, replace it. Final heap contains the k closest. O(n log k) — better when k << n.

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

function kClosest(points, k) {
  // Simulate max-heap with an array and manual sift for clarity
  const dist = p => p[0] ** 2 + p[1] ** 2;
  const heap = points.slice(0, k).sort((a, b) => dist(b) - dist(a));
  for (let i = k; i < points.length; i++) {
    if (dist(points[i]) < dist(heap[0])) {
      heap[0] = points[i];
      // Re-sort to maintain max at front (simplified; use real heap in production)
      heap.sort((a, b) => dist(b) - dist(a));
    }
  }
  return heap;
}

Tradeoff:

Tripadvisor-specific tips

Tripadvisor's 'nearby' features power millions of queries daily — knowing whether to use sort vs. heap vs. quickselect is a real engineering decision. The sort approach is fine for small datasets, but for large streaming location feeds a max-heap of size k avoids holding all n points in memory. Push the conversation toward quickselect O(n) average if the interviewer asks for the absolute optimal — it's the same algorithm underlying `nth_element` in C++ STL. Always use squared distance (avoid sqrt) and state this explicitly — interviewers listen for it.

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

Practice these live with InterviewChamp.AI →