LeetEye LeetEye
Hard Heap / Priority Queue ~5 min

K Closest Points to Origin

heap k-closest-points-to-origin

Problem

Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).

The distance between two points on the X-Y plane is the Euclidean distance (i.e., sqrt((x1 - x2)^2 + (y1 - y2)^2)).

You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in).

Examples

Example 1
Input: points = [[1,3],[-2,2]], k = 1
Output: [[-2,2]]
Distance of (1,3) = sqrt(10), (-2,2) = sqrt(8). Closest is (-2,2).
Example 2
Input: points = [[3,3],[5,-1],[-2,4]], k = 2
Output: [[3,3],[-2,4]]
Key Insight

Use max-heap of size k. Keep only the k smallest distances.

Max-heap of size k for 'k smallest': root is farthest among candidates. If new point closer than root, swap. Final heap = k closest.

How to Approach This Problem

Pattern Recognition: When you see keywords like k closest points to origin heap, think Heap / Priority Queue.

Step-by-Step Reasoning

1 To compare distances without computing sqrt, we can use:
Answer: x^2 + y^2 (squared distance)
sqrt is monotonic. Comparing squared distances gives same ordering, avoids floating point.
2 For k closest, we use:
Answer: Max-heap of size k
We want the k smallest. Max-heap lets us kick out the largest among our k candidates.
3 The heap should store:
Answer: (distance, point) pairs
Need distance for comparison, need point for final answer.
4 If new point is closer than heap root (and heap full):
Answer: Pop root (farthest), push new point
New point deserves to be in top k. Current farthest doesn't.
5 After processing all points, the answer is:
Answer: All points in the heap
Heap contains exactly the k closest points.
6 Another valid O(n) average approach is:
Answer: Quickselect
Quickselect finds k smallest in O(n) average. Heap is O(n log k).

Solution

import heapq

def kClosest(points: List[List[int]], k: int) -> List[List[int]]:
    # Max-heap of size k (negate distances)
    heap = []
    
    for x, y in points:
        dist = -(x*x + y*y)  # Negative for max-heap
        
        if len(heap) < k:
            heapq.heappush(heap, (dist, x, y))
        elif dist > heap[0][0]:  # Closer than farthest
            heapq.heapreplace(heap, (dist, x, y))
    
    return [[x, y] for _, x, y in heap]

Complexity Analysis

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

Master This Pattern

Build intuition with interactive MCQs. Practice Heap / Priority Queue problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye