K Closest Points to Origin
Ramayana — Lanka's Sentinels — The k Warriors Nearest to Ravana's Throne
उत्पत्ति के k निकटतम बिंदु — दूरी² ≤ x²+y²। महा-ढेर रखो k बिंदुओं का — शीर्ष सबसे दूर॥
*k points closest to origin — distance² = x²+y². Max-heap of k points — top is farthest of the k closest.*
The Story
Find the k closest points to the origin (0,0). Distance² = x²+y² (no need for sqrt).
For `points=[[1,3],[-2,2]]`, k=1: answer=[[-2,2]] (distance²: 1+9=10 vs 4+4=8 → [-2,2] is closer).
**Max-Heap of size k by distance²:** - Maintain a max-heap of k closest points seen so far (max by distance) - For each point: add to heap - If heap size > k: poll the farthest (it's farther than the kth closest → doesn't belong) - After processing: all k points in heap are the answer
```java PriorityQueue<int[]> pq = new PriorityQueue<>( (a,b) -> (b[0]*b[0]+b[1]*b[1]) - (a[0]*a[0]+a[1]*a[1])); // Max by distance² for (int[] p : points) { pq.offer(p); if (pq.size() > k) pq.poll(); } return pq.toArray(new int[k][]); ```
Same pattern as hp-1 (kth smallest uses max-heap). Here: - We want k CLOSEST (smallest distance²) - Use MAX-heap (opposite) - The max-distance point at the top gets evicted when a closer point arrives
Trace `[[1,3],[-2,2],[5,1]]`, k=2: - Add [1,3]: pq=[[1,3]] (d²=10) - Add [-2,2]: pq=[[-2,2],[1,3]] (d²=8,10). Max at top=[1,3] - size=2≤2 → keep both - Add [5,1]: d²=26. pq=[[5,1],[-2,2],[1,3]]. size=3>2→poll max [5,1] (d²=26) - Result: [[-2,2],[1,3]] ✓
The Sort-by-Distance Approach
Sort all points by distance². Return first k. O(n log n).
public int[][] kClosestBruteForce(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.copyOf(points, k);
}The Max-Distance-Heap Wisdom
public int[][] kClosest(int[][] points, int k) {
PriorityQueue<int[]> pq = new PriorityQueue<>(
(a, b) -> (b[0]*b[0]+b[1]*b[1]) - (a[0]*a[0]+a[1]*a[1])); // Max by distance²
for (int[] p : points) {
pq.offer(p);
if (pq.size() > k) pq.poll();
}
return pq.toArray(new int[k][]);
}Step-by-Step Walkthrough
[[1,1]], k=1 Add [1,1]: pq=[[1,1]]. size=1≤1. Return [[1,1]] ✅
Deep Insight
**Distance² not distance:** Avoid sqrt by comparing x²+y² directly. Preserves ordering since sqrt is monotone.
**Max-heap for k-closest (same as k-smallest):** - k-smallest values → MAX-heap (hp-1) - k-closest points → MAX-heap by distance (hp-5) - Both are 'k smallest by some measure' → same pattern
**Quickselect alternative:** O(n) average for exact k-closest, but heap works well for streams.
**Return any order:** The problem doesn't require sorted output, so returning heap elements directly is valid.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n log n) | O(1) | Sort by distance |
| Optimal | O(n log k) | O(k) | Max-heap of size k |
Pattern Recognition
✅ k closest points → MAX-heap by distance (size k) ✅ Distance² = x²+y² (skip sqrt) ✅ Same pattern as k-smallest (max-heap) ✅ Poll when farthest point exceeds k **LeetCode Trigger Phrases:** → "k closest points to origin" → K nearest neighbors (2D) → Max-heap for k-minimum by custom metric
Bhagavad Gita 6.30
यो मां पश्यति सर्वत्र सर्वं च मयि पश्यति। तस्याहं न प्रणश्यामि स च मे न प्रणश्यति॥
One who sees Me everywhere and sees everything in Me — I am never lost to that person, and that person is never lost to Me.
Connection: Distance to the origin (the divine center) is the measure. The k closest points are those who maintain proximity to the source. The max-heap continuously tests each point: is it close enough to remain in the inner circle of k nearest? Those that drift too far are released. The algorithm finds the k most connected — closest to origin — just as the Gita speaks of those who stay spiritually nearest to the divine.