K Closest Points to Origin (LC 973)

Pattern: Top K Elements
Difficulty: Medium
Key Concept: Track the k smallest distances using a max-heap of size k keyed by distance (evict the farthest when you have k + 1 candidates).

Problem Statement

Given an array points where points[i] = [xi, yi] represents a point on the X-Y plane, return the k points closest to the origin (0, 0).

The distance between (x, y) and the origin is the Euclidean distance sqrt(x² + y²).

You may return the answer in any order (unless a variant asks otherwise).

Input / Output

• Input: int[][] points, int k — 1 ≤ k ≤ points.length.
• Output: int[][] — exactly k points (each as [x, y]) that are closest to the origin.

Example

• points = [[1, 3], [-2, 2]], k = 1
• Distances: (1,3) → sqrt(10), (-2,2) → sqrt(8) → closest is [-2, 2].

---

1. Algorithm & Pseudocode

Brute force

1. For each point, compute distance (or squared distance).
2. Sort all points by distance ascending.
3. Take the first k.

Optimal — max-heap of size k

1. Use a heap that keeps the largest distance at the top (max-heap behavior).
2. For each point, insert into the heap.
3. If heap size exceeds k, remove the top (farthest among the k + 1).
4. After one pass, the heap holds the k closest points.

Pseudocode (optimal, squared distance)

heap = max-heap ordered by squared distance (largest on top)

for p in points:
    heap.push(p)
    if heap.size > k:
        heap.popMax()

return all elements in heap (as array)

Alternative — QuickSelect

• Partition by squared distance to place the k-th smallest distance at index k - 1 (average O(n), worst O(n²)). Good when k is large and in-place memory matters; heap is simpler and O(n log k) worst-case.

---

2. Step-by-Step Analysis (Beginner-Friendly)

1. Why squared distance? sqrt is monotone: comparing x₁² + y₁² vs x₂² + y₂² gives the same ordering as comparing real distances, avoids floating-point error and Math.sqrt cost.
2. Why max-heap here (not min-heap)? You want the k smallest distances. If you temporarily have k + 1 candidates, the one to discard is the farthest — the maximum among them. A max-heap exposes that in O(log k).
3. Contrast with “k largest elements in stream”: There you used a min-heap to drop the smallest among the top-k candidates. Here you drop the largest among your “closest k” candidates — opposite heap polarity, same “fixed size k” idea.
4. Brute force trade-off: Sorting is easy to code and fine for small n, but O(n log n) every time you solve this pattern is weaker than O(n log k) when k ≪ n.
5. QuickSelect intuition: You only need the partition boundary around the k-th order statistic; full sort is more than you need — but heaps are the standard interview solution for “top k” with a clear comparator.

---

3. The Dry Run

Input: points = [[1, 3], [-2, 2]], k = 1.

Squared distances:

Point	x² + y²
[1, 3]	1 + 9 = 10
[-2, 2]	4 + 4 = 8

We simulate a max-heap by distance squared (largest d² at top for eviction). With k = 1, the heap keeps a single closest point.

Step	Point processed	d²	Action	Heap (conceptual: point + d²)	Size after
1	[1, 3]	10	offer	{ [1,3] : 10 }	1
2	[-2, 2]	8	offer → size 2 > 1 → poll farthest (d² = 10)	{ [-2,2] : 8 }	1

Result: [[-2, 2]] — matches sorting all by distance and taking the first row.

Java note: PriorityQueue is a min-heap; the solution uses a comparator so that larger d² is ordered before smaller d², which yields max-heap behavior for eviction.

---

4. Java Solution

Brute Force

import java.util.*;

class SolutionBrute {
    public int[][] kClosest(int[][] points, int k) {
        Arrays.sort(points, (a, b) -> {
            long da = (long) a[0] * a[0] + (long) a[1] * a[1];
            long db = (long) b[0] * b[0] + (long) b[1] * b[1];
            return Long.compare(da, db);
        });
        return Arrays.copyOfRange(points, 0, k);
    }
}

• Time: O(n log n) for sort.
• Space: O(1) extra beyond output if sort is in-place (aside from sort stack); using long avoids int overflow on d².

Optimal

import java.util.PriorityQueue;

class Solution {
    public int[][] kClosest(int[][] points, int k) {
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> {
            long da = (long) a[0] * a[0] + (long) a[1] * a[1];
            long db = (long) b[0] * b[0] + (long) b[1] * b[1];
            return Long.compare(db, da); // larger distance first = max-heap by d²
        });

        for (int[] p : points) {
            maxHeap.offer(p);
            if (maxHeap.size() > k) {
                maxHeap.poll();
            }
        }

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

• Time: O(n log k) — each of n points does heap ops on size k.
• Space: O(k) for the heap.

---

5. The “Java vs. Others” Edge

• PriorityQueue + comparator: (a, b) -> Long.compare(db, da) makes the queue behave like a max-heap on squared distance without a separate Distance class (though a typed record/class can improve readability).
• Use long for d²: Coordinates can be large; int * int can overflow before you compare.
• Skip Math.sqrt: Same ordering, cleaner and faster — interviewers expect this optimization.
• C++: std::priority_queue<pair<int, pair<int,int>>, vector<...>, Cmp> with custom operator> or a lambda — default max-heap aligns naturally with “largest distance on top” if you store d² as the first element of pair.
• Python: heapq is min-only; people often push (-dist, point) or use heapq.nsmallest(k, points, key=...).

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	O(n log n)	O(1) to O(n)	Full sort by d²; easy, not optimal for tiny k.
Optimal (heap)	O(n log k)	O(k)	Max-heap evicts farthest; stable interview choice.
QuickSelect (avg)	O(n) average	O(1) extra	Worst O(n²); good when in-place and average-case OK.