Top K Elements

K Closest Points

Use a max-heap of size K sorted by distance. As you process points, if a point is closer than the farthest point in the heap, replace it. The max-heap keeps the K closest by evicting the farthest.

O(n log k)

O(k)

How It Works

K closest points to the origin flips the top-K recipe: to keep the K smallest distances, maintain a max-heap of size K keyed by distance. Push the first K points, then for each remaining point compare its distance to the heap top — the farthest of the current K. If the newcomer is closer, evict the top and push it. When input ends, the heap holds exactly the K closest points, in no particular order.

Use squared distance (x² + y²) to avoid floating-point square roots — comparisons are unaffected since squaring preserves order for non-negative values. The runtime is O(n log K) with O(K) memory, versus O(n log n) for sorting all points. The symmetry with Kth-largest is worth internalizing: keeping the K smallest needs a max-heap, keeping the K largest needs a min-heap — always the opposite heap of what the problem name suggests.

Step-by-Step Visualization

K=2 closest points to origin: (1,3),(-2,2),(5,1)

-2

Distances²10, 8, 26

1/2

Code

Java

static int[][] kClosest(int[][] points, int k) {
  Arrays.sort(points, (a, b) -> (a[0]*a[0] + a[1]*a[1]) - (b[0]*b[0] + b[1]*b[1]));
  return Arrays.copyOfRange(points, 0, k);
}

// Optimal: use max-heap of size k or quickselect

Tips & Gotchas

1Use a max-heap of size K (keep K closest = smallest distances)

2If new point is closer than heap root, replace it

3Distance formula: sqrt not needed for comparison — use x²+y²

Practice Problems

1K Closest Points to Origin
2Find K Closest Elements
3K-th Smallest Prime Fraction

About the Top K Elements Pattern

Use a min-heap of size K. As you process elements, if the current element is larger than the heap's minimum, swap it in. When done, the heap contains exactly the K largest elements. The top is the Kth largest.

Key insight

Need the K largest? Use a min-heap of size K — anything larger than the min gets in. For median, split into two heaps: max-heap for lower half, min-heap for upper half.

Common Heap Interview Problems

Kth Largest Element
Top K Frequent Elements
Find Median from Data Stream
Merge K Sorted Lists
Task Scheduler
K Closest Points to Origin

Frequently Asked Questions

Why compute squared distance instead of true Euclidean distance?

The square root is monotonic, so comparing squared distances gives identical orderings while avoiding both the cost and the floating-point precision issues of sqrt. Only compute the real distance if the answer itself must be reported as one.

Is Quickselect a better fit for this problem?

If all points fit in memory and you only answer once, Quickselect partitions around the Kth smallest distance in O(n) average time and beats the heap. The heap remains preferable for streaming input, stable worst-case guarantees, or when n is huge and only O(K) memory is available.