K Closest Points to Origin

LeetCode 973: K Closest Points to Origin Solution & Explanation

Problem Overview

TL;DR: We utilize a Max-Heap of size K to maintain the K smallest distances found so far, efficiently discarding the farthest points as we iterate through the input.

The problem asks us to find the k points from a given list of (x, y) coordinates that are closest to the origin (0, 0). The distance is measured using Euclidean distance. While the output can be in any order, the set of points returned must be the unique k closest points. This is a classic example of a "Top K" problem, making the LeetCode 973 challenge a staple in technical interviews.

Brute Force Approach for K Closest Points to Origin

The most straightforward way to solve K Closest Points to Origin is to calculate the distance for every point and then sort the entire list based on these distances.

Naive Algorithm:

1. Create a list of tuples containing the distance and the original point coordinates.
2. Calculate the Euclidean distance for every point: $\sqrt{x^2 + y^2}$. (Note: We can omit the square root since distance is monotonic; comparing squared distances yields the same order).
3. Sort the entire list of points in ascending order of their squared distances.
4. Return the first k points from the sorted list.

1# Pseudo-code for Brute Force
2def kClosest(points, k):
3    # Calculate squared distance for all points
4    points_with_dist = []
5    for x, y in points:
6        dist = x*x + y*y
7        points_with_dist.append((dist, [x, y]))
8    
9    # Sort entire array - O(N log N)
10    points_with_dist.sort(key=lambda p: p[0])
11    
12    # Return top k
13    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.

Algorithm Strategy: Heap (Priority Queue) Patterns

1. Metric Calculation: We will compare points based on their squared Euclidean distance, $x^2 + y^2$. We avoid the square root operation because it is computationally expensive and floating-point precision issues can occur, while squared distances preserve the exact same order.
2. Heap Initialization: Initialize an empty Max-Heap (Priority Queue).
3. Iteration: Iterate through the points array one by one.
4. Maintenance:
   • Push the current point and its distance into the heap.
   • Since most standard libraries provide a Min-Heap, we may need to invert the distance (store negative distance) to simulate a Max-Heap.
   • If the size of the heap exceeds K, remove the top element. The top element of a Max-Heap is the largest distance, which represents the point "farthest" from the origin among the current candidates. Removing it ensures we only keep the K closest points seen so far.
5. Output: After processing all points, the heap will contain exactly K points. Return them.

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 $> k$.
   • Identify the max element in the heap. The max is (10, [1, 3]).
   • Pop the max.
   • Heap state: [(8, [-2, 2])].
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 $K$ 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.

Pattern Reuse Notes

The Heap - Top K Elements pattern is highly reusable. Understanding how to maintain a bounded heap allows you to solve several other popular interview questions:

• LeetCode 215: Kth Largest Element in an Array - Uses a Min-Heap of size K to find the Kth largest number.
• LeetCode 347: Top K Frequent Elements - Uses a Min-Heap of size K to keep the elements with the highest frequencies.
• LeetCode 451: Sort Characters By Frequency - Similar to Top K Frequent, but requires sorting the output.
• LeetCode 506: Relative Ranks - Assigns ranks based on score, essentially sorting or using a heap to determine placement.

In all these cases, the logic remains the same: use a heap to maintain a "window" of the top candidates while iterating through the data.

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.

1#include <vector>
2#include <queue>
3
4using namespace std;
5
6class Solution {
7public:
8    vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
9        // Max-Heap to store pairs of (distance_squared, point_coordinates)
10        // By default, priority_queue sorts by the first element of the pair descending
11        priority_queue<pair<long, vector<int>>> maxHeap;
12
13        for (const auto& point : points) {
14            long x = point[0];
15            long y = point[1];
16            long dist = x * x + y * y;
17
18            maxHeap.push({dist, point});
19
20            // If heap size exceeds k, remove the farthest point (largest distance)
21            if (maxHeap.size() > k) {
22                maxHeap.pop();
23            }
24        }
25
26        vector<vector<int>> result;
27        while (!maxHeap.empty()) {
28            result.push_back(maxHeap.top().second);
29            maxHeap.pop();
30        }
31
32        return result;
33    }
34};

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).

1import java.util.PriorityQueue;
2
3class Solution {
4    public int[][] kClosest(int[][] points, int k) {
5        // Max-Heap: orders points by distance in descending order
6        // We store indices or the points themselves. Here we store the point arrays.
7        PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> {
8            long distA = (long) a[0] * a[0] + (long) a[1] * a[1];
9            long distB = (long) b[0] * b[0] + (long) b[1] * b[1];
10            return Long.compare(distB, distA); // Descending order
11        });
12
13        for (int[] point : points) {
14            maxHeap.offer(point);
15            
16            // If we have more than k elements, remove the one with the largest distance
17            if (maxHeap.size() > k) {
18                maxHeap.poll();
19            }
20        }
21
22        int[][] result = new int[k][2];
23        for (int i = 0; i < k; i++) {
24            result[i] = maxHeap.poll();
25        }
26        
27        return result;
28    }
29}

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.

1import heapq
2
3class Solution:
4    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
5        # Max-Heap simulated using Min-Heap with negative values
6        heap = []
7        
8        for x, y in points:
9            dist = -(x*x + y*y) # Negate distance for Max-Heap behavior
10            heapq.heappush(heap, (dist, [x, y]))
11            
12            # If heap grows beyond k, remove the smallest item
13            # (which corresponds to the largest actual distance)
14            if len(heap) > k:
15                heapq.heappop(heap)
16        
17        # Extract points from the heap
18        return [point for (_, point) in heap]