LeetCode 973: K Closest Points to Origin | Sorting vs Heap Approach (Python)

LeetCode 973 — K Closest Points to Origin

Below are two Python implementations from my GitHub repository showing different approaches:

Version 1 (Sort-based)

This solution sorts all points by distance from the origin and returns the first k:

        
# LC973_V1.py
# https://github.com/RohitSingh-04/Python-Solutions/blob/main/LC973_V1.py

class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        buffer = [(point[0]**2 + point[1]**2, index) for index, point in enumerate(points)]
        buffer.sort(key=lambda x: x[0])
        answer = [points[buffer[i][1]] for i in range(k)]
        return answer
        
      

👉 View full file on GitHub: LC973_V1.py

Version 2 (Heap-based)

This version uses a heap to maintain the k closest points efficiently:

        
# LC973_V2.py
# https://github.com/RohitSingh-04/Python-Solutions/blob/main/LC973_V2.py

import heapq
from typing import List

class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        maxHeap = []

        for x, y in points:
            dist = x * x + y * y
            heapq.heappush(maxHeap, (-dist, [x, y]))
            if len(maxHeap) > k:
                heapq.heappop(maxHeap)

        return [point for (_, point) in maxHeap]
        
      

👉 View full file on GitHub: LC973_V2.py

LeetCode 973 description: find the k closest points to the origin based on Euclidean distance (using squared distance x² + y² for comparison). :contentReference[oaicite:0]{index=0}