Domain 2MediumMEDIUM

K Closest Points to Origin

Uses a max-heap (simulated via negation in Python's min-heap) to maintain the k smallest distances, achieving O(N log K) time complexity.

Domain: medium•Updated: 2026-09-05
#heap#priority queue#O(N log K)#O(K)

Problem Breakdown

We are given an array of points where each point is [x, y], and we need to return exactly k points closest to the origin (0, 0).

Key Inputs & Outputs:

  • Input: A list of lists (2D coordinates), integer k.
  • Output: List containing exactly k coordinate pairs. Order does not matter.

Implicit Constraints & Optimizations:

  1. Distance Metric: Euclidean distance involves a square root (√(x² + y²)). Since we only need to compare distances, using squared Euclidean distance (x*x + y*y) is sufficient and avoids floating-point precision issues/costs of sqrt.
  2. Order Independence: The result order does not matter, allowing us to discard points once they are no longer in the top k closest set.
  3. Constraints: Coordinates range from -10^4 to 10^4, array length up to 10^4. Squared distances fit within standard integer types (Python handles large integers automatically).

Intuition

A brute-force approach would be to calculate the distance for every point, sort all points by this metric, and slice off the first k. This takes O(Nlog⁡N)O(N \log N) time. While acceptable given constraints (N=104N=10^4), it is not optimal if we only care about finding a subset of size K where K << N.

Key Insight: We are looking for the “Top K” smallest elements in an unsorted collection. This pattern strongly suggests using a Heap (Priority Queue).

  • Using a Min-Heap to store all points would require popping until we have k, which is inefficient (O(Nlog⁡N)O(N \log N)).
  • To optimize, we can maintain a heap of size exactly K. As we iterate through the input:
    1. Add current point’s distance info to our collection (heap).
    2. If the collection exceeds size k, remove the element with the largest distance from this subset.
  1. Python Specifics: Python’s standard library provides a Min-Heap (heapq). To simulate removing the “farthest” point when we exceed capacity, we store negative distances in our heap (Max-Heap behavior using negation). The smallest value popped will be the most negative number, corresponding to the largest positive distance.

Approach

  1. Initialize an empty list heap which acts as a priority queue.
  2. Iterate through each point (x, y) in the input array:
    • Calculate squared Euclidean distance: dist = x*x + y*y.
    • Push tuple (-dist, x, y) onto the heap. We negate dist so that Python’s min-heap pops the largest actual distances first when we need to trim our set of closest points.
  3. Check if the length of the heap exceeds k:
    • If yes: Perform a pop operation (heappop). This removes the point with the largest distance (worst candidate) from our current top-k selection, keeping only the closer ones.
  4. After iterating through all points, convert the remaining tuples in the heap back into lists of coordinates and return them.

Complexity Analysis

  • Time Complexity: O(Nlog⁡K)O(N \log K) where N is the number of points and K is the target count. We iterate once (O(N)O(N)) and perform a push/pop operation on a heap of size at most k. Each heap operation takes logarithmic time relative to its current size ($\le k$).
    • Note: If we used sorting, it would be O(Nlog⁡N)O(N \log N). Since log⁡K<log⁡N\log K < \log N, the Heap approach is theoretically faster when K is small. Given Python’s Timsort efficiency (N=104N=10^4), both pass easily, but this demonstrates algorithmic optimization skills required for senior roles.
  • Space Complexity: O(K)O(K) to store the heap elements (excluding input storage).

Solution

import heapq

def kClosest(points: list[list[int]], k: int) -> list[list[int]]:
    # Use a min-heap but store negative distances to simulate max-heap behavior.
    # We want to evict the point with the largest distance when size > k.
    heap = []
    
    for x, y in points:
        dist_sq = x * x + y * y
        
        # Push (-dist, x, y) so that heappop removes the farthest point (smallest negative value)
        heapq.heappush(heap, (-dist_sq, x, y))
        
        # Maintain heap size at k. If larger, remove the worst candidate (farthest).
        if len(heap) > k:
            heapq.heappop(heap)
            
    # Extract coordinates from tuples and convert to list format as per return type requirements
    result = [list(point[1:]) for point in heap]
    
    return result

Edge Cases Handled

  • Empty Input: The loop simply won’t execute; returns empty list. Though constraints guarantee points.length >= k.
  • k == len(points): The heap grows to full size and never pops, returning all points (correct).
  • Negative Coordinates: Squared distance calculation (x*x) handles negative signs correctly without special logic.
  • Duplicate Distances: If multiple points have the exact same squared distance, heapq maintains stability based on insertion order or tuple comparison of subsequent elements; any valid subset is accepted by problem statement (“answer in any order”).