{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

K Closest Points to Origin – Solution & Complexity

Interview solutions
/
K Closest Points to Origin

Solution Walkthrough

  1. Step 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. Step 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. Step 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. Step 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. Step 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?