{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsChat
New
Blog
Ctrl + K

K Closest Points to Origin – Solution & Complexity

Interview solutions
/
K Closest Points to Origin

Solution Walkthrough

1. Brute-force baseline

  • Compute every distance, sort all n points, and take the first k.
  • That is correct, but sorting the whole array does more work than necessary when k is small.

2. Keep only the current best k

  • Use a max-heap keyed by (distance, x, y) so the current worst selected point stays on top.
  • If a new point is better than that worst point, replace it.

3. Finish with deterministic ordering

  • Heap order is not the same as output order.
  • Sort the k retained points by (distance, x, y) before returning them.

4. Final solution (all languages)

A size-k max-heap keeps selection efficient, then a final sort satisfies the exact judge contract.

import heapq

def k_closest(points: list[list[int]], k: int) -> list[list[int]]:
    heap: list[tuple[int, int, int, int, int]] = []

    for x, y in points:
        distance = x * x + y * y
        entry = (-distance, -x, -y, x, y)
        if len(heap) < k:
            heapq.heappush(heap, entry)
        elif entry > heap[0]:
            heapq.heapreplace(heap, entry)

    answer = [[x, y] for _, _, _, x, y in heap]
    answer.sort(key=lambda point: (point[0] * point[0] + point[1] * point[1], point[0], point[1]))
    return answer

5. Complexity summary

  • Time: O(n log k + k log k).
  • Space: O(k) besides the returned output.

FAQ

See also

Practice K Closest Points to Origin online (run code in the browser)Kth Largest Element in an Array solution (medium)Top K Frequent Elements solution (medium)Find Median from Data Stream solution (hard)Merge K Sorted Lists solution (hard)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?