DSA AnimatorDSA animations
K Closest Points to Origin LC #973 Medium Max Heap · Size K
Problem

Given an array of points where points[i] = [xi, yi] and the origin [0, 0], return the k closest points to the origin. Distance is Euclidean. You may return the answer in any order.

Example 1
Input: points = [[1,3],[-2,2]], k = 1
Output: [[-2,2]]
Explanation: √8 < √10, so (-2,2) is closer to origin.
Example 2
Input: points = [[3,3],[5,-1],[-2,4]], k = 2
Output: [[3,3],[-2,4]]
Explanation: d²: 18, 26, 20. Two closest: (3,3) and (-2,4).
Constraints: 1 ≤ k ≤ points.length ≤ 10⁴  |  −10⁴ ≤ xi, yi ≤ 10⁴
Try Examples
Custom:
Approach
Max-Heap of size k: track the k closest points by dist²=x²+y²
If heap grows > k, remove the farthest. Remaining k points are the answer.
Coordinate Plane
Max-Heap (root = farthest)
Empty
Variables
Current Point
—
dist² (x²+y²)
—
Heap Size
0
k
—
Step Logic
Press ▶ Play or Next Step to begin the animation.
🎉
Ready
0 / 0
Select an example above and press Play.
Algorithm
1
Max-heap by dist² — root = farthest among current k closest
2
Add each point to the heap
3
If size > k: evict max (farthest) — root of max-heap
4
Return heap contents — the k closest points
Time
O(n log k)
Space
O(k)
Why MAX-Heap for K Closest?

Counter-intuitive but elegant: to keep the k smallest distances, use a MAX-heap. The root is always the farthest point in your current selection. When a new point arrives and the heap is full (k+1 items), you evict the root — the current farthest. What remains is always the k closest seen so far. Using dist² instead of dist avoids the sqrt operation while preserving comparison order.

How to solve K Closest Points to Origin

LeetCode 973 · Medium · Heap / Priority Queue · Pattern: Max Heap of Size K

Why the obvious approach is slow

Sorting all points by distance takes O(n log n). We only need the k closest ones.

The key idea

Compare squared distances, x squared plus y squared, so no square root is needed. Keep a max heap of at most k points, ordered by distance. The root is the farthest point among the current k closest. When a new point makes the heap bigger than k, poll the root, because it is the worst candidate.

Remember

For the k smallest, use a max heap of size k. Compare squared distances to skip the square root.

Run the animation above on your own input, or watch the 1:43 video explanation of K Closest Points to Origin with a dry run and Java code.

More Heap / Priority Queue problems