python
# Pseudo-code for Brute Force
def kClosest(points, k):
    # Calculate squared distance for all points
    points_with_dist = []
    for x, y in points:
        dist = x*x + y*y
        points_with_dist.append((dist, [x, y]))
    
    # Sort entire array - O(N log N)
    points_with_dist.sort(key=lambda p: p[0])
    
    # Return top k
    return [p[1] for p in points_with_dist[:k]]

Complexity Analysis: The time complexity is dominated by the sorting step, which is $O(N \log N)$, where $N$ is the number of points. The space complexity is $O(N)$ to store the distances.

Why it fails (or is suboptimal): While $O(N \log N)$ is acceptable for smaller constraints, it performs unnecessary work. We sort the entire array of $N$ points, even though we only care about the top $K$. If $N$ is 10 million and $K$ is 5, sorting the entire dataset is extremely wasteful. The optimal solution should scale better with $N$ when $K$ is small.

Core Insight for K Closest Points to Origin

The core insight that optimizes the brute force approach is realizing we only need to maintain the "best" K candidates at any given time. We don't need to know the relative order of the points that are not in the top K.

To efficiently maintain the K smallest elements, we can use a Max-Heap of size K.

Why a Max-Heap for finding the smallest elements? This is often counter-intuitive. To keep the smallest distances, we need to be able to identify and remove the largest distance among our currently selected K points.

• If we have a heap of K points, the root of a Max-Heap gives us the point with the largest distance in that group (the "worst" of the "best").
• When we encounter a new point, we compare its distance to the root of the Max-Heap.
• If the new point's distance is smaller than the root, it means the new point is closer to the origin than the farthest point currently in our top K. We pop the root (remove the farthest) and push the new point.
• If the new point's distance is larger, it is farther away than all K points currently in the heap, so we discard it.

Visual Description: Imagine a bucket that can only hold K balls. We assign a "size" to each ball based on its distance from the origin. We want the bucket to hold the K smallest balls. As we pick up new balls from a pile, we look at the bucket. If the bucket isn't full, we toss the ball in. If the bucket is full, we look for the largest ball inside it. If the new ball is smaller than the largest ball in the bucket, we swap them. The Max-Heap acts as this bucket, keeping the largest ball at the top for easy access and removal.

Execution Flow

Let's trace the algorithm with points = [[1,3], [-2,2]] and k = 1.

1. Initialize: Max-Heap heap = [].
2. Process Point [1, 3]:
   • Calculate squared distance: $1^2 + 3^2 = 10$.
   • Push to heap. Heap state: [(10, [1, 3])].
   • Heap size is 1. Since $1 \le k$, we do not pop.
3. Process Point [-2, 2]:
   • Calculate squared distance: $(-2)^2 + 2^2 = 8$.
   • Push to heap. Heap state (conceptually): [(10, [1, 3]), (8, [-2, 2])].
   • Heap size is 2, which is $$.
4. Result: The heap contains [[-2, 2]]. Return this list.

Proof of Correctness

We maintain an invariant: after processing the $i$-th element, the heap contains the $K$ points with the smallest distances among the first $i$ points.

Base Case: For the first $K$ elements, the heap simply stores all of them. The invariant holds trivially. Inductive Step: Suppose the heap holds the $K$ closest points among the first $i$ elements. Let $d_{max}$ be the largest distance in the heap (the root). Consider the $(i+1)$-th element with distance $d_{new}$.

1. If $d_{new} < d_{max}$, then the point with distance $d_{max}$ is strictly farther than the new point. To maintain the set of $K$ closest, we must remove the point with $d_{max}$ and include the new point. The heap property handles this by popping the root and inserting the new item.
2. If $d_{new} \ge d_{max}$, then the new point is farther than (or equal to) the farthest point currently in our top $K$. Therefore, it cannot be part of the top closest points. The algorithm pushes it and immediately pops it (or simply ignores it), maintaining the existing set.

Thus, after $N$ steps, the heap contains the global $K$ closest points.

Reference Implementation

C++ Solution for LeetCode 973

In C++, std::priority_queue is a Max-Heap by default. We store pairs of {squared_distance, index} or the point vector itself.

cpp
#include <vector>
#include <queue>

using namespace std;

class Solution {
public:
    vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
        // Max-Heap to store pairs of (distance_squared, point_coordinates)
        // By default, priority_queue sorts by the first element of the pair descending
        priority_queue<pair<long, vector<int>>> maxHeap;

        for (const auto& point : points) {
            long x = point[0];
            long y = point[1];
            long dist = x * x + y * y;

            maxHeap.push({dist, point});

            // If heap size exceeds k, remove the farthest point (largest distance)
            if (maxHeap.size() > k) {
                maxHeap.pop();
            }
        }

        vector<vector<int>> result;
        while (!maxHeap.empty()) {
            result.push_back(maxHeap.top().second);
            maxHeap.pop();
        }

        return result;
    }
};

Java Solution for LeetCode 973

In Java, PriorityQueue is a Min-Heap by default. To create a Max-Heap, we provide a custom comparator that reverses the natural ordering (b - a).

java
import java.util.PriorityQueue;

class Solution {
    public int[][] kClosest(int[][] points, int k) {
        // Max-Heap: orders points by distance in descending order
        // We store indices or the points themselves. Here we store the point arrays.
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> {
            long distA = (long) a[0] * a[0] + (long) a[1] * a[1];
            long distB = (long) b[0] * b[0] + (long) b[1] * b[1];
            return Long.compare(distB, distA); // Descending order
        });

        for (int[] point : points) {
            maxHeap.offer(point);
            
            // If we have more than k elements, remove the one with the largest distance
            if (maxHeap.size() > k) {
                maxHeap.poll();
            }
        }

        int[][] result = new int[k][2];
        for (int i = 0; i < k; i++) {
            result[i] = maxHeap.poll();
        }
        
        return result;
    }
}

Python Solution for LeetCode 973

Python's heapq module implements a Min-Heap. To simulate a Max-Heap, we store the negative of the distance. The "largest" distance becomes the "smallest" negative number, sitting at the root of the Min-Heap.

python
import heapq

class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        # Max-Heap simulated using Min-Heap with negative values
        heap = []
        
        for x, y in points:
            dist = -(x*x + y*y) # Negate distance for Max-Heap behavior
            heapq.heappush(heap, (dist, [x, y]))
            
            # If heap grows beyond k, remove the smallest item
            # (which corresponds to the largest actual distance)
            if len(heap) > k:
                heapq.heappop(heap)
        
        # Extract points from the heap
        return [point for (_, point) in heap]