LeetCode · #973

K Closest Points to Origin Solution

Given an array of points on the X-Y plane, return the k closest points to the origin (0, 0). Distance is Euclidean. The answer may be returned in any order.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #973

🏗️

Pattern

Heap — max-heap of size k by distance

Given an array of points points[i] = [x, y], return the k points closest to the origin. The Euclidean distance is √(x² + y²), but since we only compare distances, we can use x² + y² (skip the square root).

Example

 Input: points = [[1,3],[-2,2]], k = 1 Output: [[-2,2]]
// dist(1,3) = 1+9 = 10,  dist(-2,2) = 4+4 = 8 → (-2,2) is closer 

Example 2

 Input: points = [[3,3],[5,-1],[-2,4]], k = 2 Output: [[3,3],[-2,4]]
// Distances: 18, 26, 20 → top-2 closest: 18 and 20 

Constraints

 • 1 ≤ k ≤ points.length ≤ 10⁴ • -10⁴ ≤ x, y ≤ 10⁴  ↑ Squared distance fits in int (max 2×10⁸ < 2³¹) 

Section Two · Approach 1

Sort by Distance — O(n log n)

Sort all points by their squared distance from the origin, then return the first k. Correct and straightforward, but sorts all n points when we only need the top-k closest.

Why it works

Sorting by distance places the closest points first. Taking the first k gives the answer directly.

Why we can do better

Problem: Sorting does O(n log n) work, but we only need k points. A max-heap of size k processes each point in O(log k) — total O(n log k). When k ≪ n, this is significantly faster.

Java — Sort

 import java.util.Arrays;
class Solution {
public 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);
    }
}

Python — Sort

 class Solution:
def kClosest(self, points: list[list[int]], k: int) -> list[list[int]]:
        points.sort(key=lambda p: p[0]**2 + p[1]**2)
return points[:k]

Metric	Value
Time	O(n log n)
Space	O(1) — in-place sort (O(n) for copy)

Section Three · Approach 2

Max-Heap of Size k — O(n log k)

Maintain a max-heap of size k, ordered by distance. For each point: add it to the heap. If the heap exceeds size k, remove the farthest point (the root). After processing all points, the heap holds the k closest.

💡 Mental model: Imagine a lifeboat with k seats. Survivors swim toward the boat from various distances. The mate lets everyone climb aboard, but once k seats are full, the person farthest from shore (largest distance = max-heap root) is asked to leave whenever someone closer arrives. After all survivors have been checked, the boat holds the k closest.

Algorithm

Step 1: Create a max-heap ordered by squared distance (largest distance at root).
Step 2: For each point, offer it to the heap.
Step 3: If heap size > k, poll the root (farthest point).
Step 4: Heap contents = the k closest points.

🎯 When to recognize this pattern:

"Find k closest / k smallest" → max-heap of size k.
The inverse of "kth largest" (which uses a min-heap).
By keeping a max-heap, the root is the worst candidate among the k best — easy to evict when a better one arrives.
This pattern appears in LC 973, nearest-neighbor searches, and streaming top-k problems.

Skip the square root: Since √a < √b ⟺ a < b for non-negative values, comparing x² + y² directly gives the same ordering as Euclidean distance — no floating-point needed.

Section Four · Trace

Visual Walkthrough

Trace with points = [[3,3],[5,-1],[-2,4]], k = 2:

Max-Heap of size k=2 — evict farthest when full

Section Five · Implementation

Code — Java & Python

Java — Max-Heap of size k

 import java.util.PriorityQueue;
class Solution {
public int[][] kClosest(int[][] points, int k) {
// Max-heap by distance — farthest at root PriorityQueue<int[]> heap = new PriorityQueue<>(
            (a, b) -> (b[0]*b[0] + b[1]*b[1]) - (a[0]*a[0] + a[1]*a[1]));
for (int[] p : points) {
            heap.offer(p);
if (heap.size() > k)
                heap.poll(); // evict farthest point
}
return heap.toArray(new int[k][]);
    }
}

Python — Max-Heap (negate distance)

 import heapq
class Solution:
def kClosest(self, points: list[list[int]], k: int) -> list[list[int]]:
        heap = [] # max-heap via negated distance for x, y in points:
            dist = -(x * x + y * y) # negate for max-heap
heapq.heappush(heap, (dist, [x, y]))
if len(heap) > k:
                heapq.heappop(heap) # evict farthest return [p for _, p in heap]

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Sort by distance	O(n log n)	O(1)	Simple; sorts everything
Max-Heap size k ← optimal	O(n log k)	O(k)	Only stores k points. O(log k) per point.
Quickselect	O(n) avg	O(1)	Partitions by distance. O(n²) worst-case.

Why max-heap, not min-heap?:

We want the k closest (smallest distances).
A max-heap of size k keeps the root as the farthest among the k best — the one most likely to be replaced.
When a closer point arrives, it replaces the root.
If we used a min-heap, the root would be the closest point — polling it would remove a point we want to keep.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
k = n (all points)	`[[1,0],[0,1]], k=2`	Return all points. Heap never polls.
k = 1	`[[1,1],[3,4]], k=1`	Heap size 1 → just the closest point.
Origin point	`[[0,0],[1,1]], k=1`	Distance 0 is closest. Heap handles it.
Negative coordinates	`[[-2,-3]], k=1`	Squaring makes negatives positive. d² = 4+9 = 13.
Equal distances	`[[1,0],[0,1]], k=1`	Both have d²=1. Either is valid — answer order doesn't matter.
Large coordinates	`[[10000,10000]]`	d² = 2×10⁸ — fits in int (max ~2.1×10⁹).

⚠ Common Mistake: Computing Math.sqrt(x*x + y*y) and comparing floating-point distances. This is unnecessary and introduces precision errors. Since √a < √b ⟺ a < b, compare x²+y² directly as integers — faster and exact.

← Back to Heap problems

LearningTree

LC 973 · K Closest Points to Origin — Solution & Explanation | DSA Guide