K Closest Points to Origin

1import heapq
2import math
3
4def k_closest(points, k):
5    # Max-heap to store k closest points
6    # Store negative distances for max-heap behavior
7    heap = []
8
9    for i in range(len(points)):
10        x, y = points[i]
11        distance = math.sqrt(x**2 + y**2)
12
13        if len(heap) < k:
14            # Heap not full, add point
15            heapq.heappush(heap, (-distance, i))
16        else:
17            # Heap full, compare with max
18            max_distance = -heap[0][0]
19
20            if distance < max_distance:
21                # Current point is closer, replace max
22                heapq.heapreplace(heap, (-distance, i))
23
24    # Extract result
25    return [points[i] for _, i in heap]

pointsArray

[[1,3],[-2,2],[5,8],[0,1],[-3,-1]]

kInteger

Variable	Value
points	Matrix(5x2) [[1,3]...]
k	2
heap	-
i	-

Variable	Value
x	-
y	-
distance	-
max_distance	-

0 / 15

pointsArray

[[1,3],[-2,2],[5,8],[0,1],[-3,-1]]

kInteger

1import heapq
2import math
3
4def k_closest(points, k):
5    # Max-heap to store k closest points
6    # Store negative distances for max-heap behavior
7    heap = []
8
9    for i in range(len(points)):
10        x, y = points[i]
11        distance = math.sqrt(x**2 + y**2)
12
13        if len(heap) < k:
14            # Heap not full, add point
15            heapq.heappush(heap, (-distance, i))
16        else:
17            # Heap full, compare with max
18            max_distance = -heap[0][0]
19
20            if distance < max_distance:
21                # Current point is closer, replace max
22                heapq.heapreplace(heap, (-distance, i))
23
24    # Extract result
25    return [points[i] for _, i in heap]

0 / 15