#66 Medium Time O(n log k) Space O(k) Animated

K Closest Points to Origin

Find the k closest points to origin.

LeetCode ↗

Tutor Mode Build the mental model before you memorize the code.

1 Predict
2 Trace
3 Explain
4 Implement

Pattern Priority queue for the next best choice

Keep only candidates that may become the next answer, ordered by the priority that matters.

Approach: Min-Heap

Click play to start

Step 0 / 0

Press play to start the visualization.

1×

Core Insight

Keep only candidates that may become the next answer, ordered by the priority that matters.

Common Pitfall

Push only meaningful candidates and remove stale entries before trusting the root.

Description

Find the k closest points to origin.

Constraints

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

Solution — Min-Heap

TimeO(n log k) SpaceO(k)

Implementation Plan

Translate the invariant into these small, testable moves.

Choose the priority key.
Push initial candidates.
Pop the best valid candidate.
Add newly eligible candidates and repeat.

def kClosest(points, k):
    minHeap = []
    for x, y in points:
        dist = (x ** 2) + (y ** 2)
        minHeap.append((dist, x, y))
    
    heapq.heapify(minHeap)
    res = []
    for _ in range(k):
        _, x, y = heapq.heappop(minHeap)
        res.append([x, y])
    return res

Last Stone Weight

Kth Largest Element in an Array

K Closest Points to Origin

Steps

Description

Constraints

Tags

Solution — Min-Heap