Skip to main content

973. K Closest Points to Origin

medium

Return the k points closest to the origin from a 2D list. A frequent on-site question that rewards spotting the 'top k by metric' template and reaching for a max-heap.

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

Problem

Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0). The distance between two points on the X-Y plane is the Euclidean distance (sqrt((x1 - x2)^2 + (y1 - y2)^2)). You may return the answer 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: The distance between (1, 3) and the origin is sqrt(10). The distance between (-2, 2) and the origin is sqrt(8). Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin. We only want the closest k = 1 points from the origin, so the answer is just [[-2,2]].

Example 2

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

Explanation: The answer [[-2,4],[3,3]] would also be accepted.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Square root is monotonic — compare x^2 + y^2 directly. No need to compute sqrt.

Hint 2

Sort by squared distance is O(n log n). Can you do better when k << n?

Hint 3

Max-heap of size k, ordered by squared distance. Push every point; pop when size > k. The heap ends holding the k smallest distances.

Hint 4

Quickselect on squared distance is O(n) average, no extra structure — the optimal follow-up.

Solution approach

Reveal approach

For each point compute the squared distance d = x*x + y*y (avoid sqrt — it's monotonic and costs you nothing here). Push points into a max-heap keyed on d. When the heap size exceeds k, pop the worst. After processing every point, the heap holds the k closest points. O(n log k) time, O(k) space. Quickselect is the O(n)-average follow-up: partition around a pivot's squared distance and recurse only into the side containing rank k. Mention both.

Complexity

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

Related patterns

  • heap
  • quickselect
  • top-k

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Meta
  • Uber
  • LinkedIn

Practice these live with InterviewChamp.AI

Drill K Closest Points to Origin and Heaps problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →