Q9: How do you find the K Closest Points to the Origin (0,0)?

Calculate distance squared $x^2 + y^2$. Use a Max-Heap (PriorityQueue) of size $k$ ordered by Euclidean distance descending. Push points into the heap; if heap size exceeds $k$, pop the maximum distance point. Returns $k$ closest points in $O(n log k)$ time.

K Closest Points Max-Heap Solution

import java.util.PriorityQueue;

public class KClosestPoints {
    public static int[][] kClosest(int[][] points, int k) {
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>(
            (a, b) -> Integer.compare((b[0]*b[0] + b[1]*b[1]), (a[0]*a[0] + a[1]*a[1]))
        );
        for (int[] p : points) {
            maxHeap.offer(p);
            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;
    }
}

💡 Maintains $k$ smallest Euclidean distance points inside a bounded Max-Heap.

Key Takeaways

Avoid Math.sqrt() by comparing squared distances ($x^2 + y^2$).
Use size-bounded Max-Heap ($O(n log k)$ runtime).

Knowledge Check

Why is comparing (x1^2 + y1^2) directly preferred over using Math.sqrt(x1^2 + y1^2)?

Q9: How do you find the K Closest Points to the Origin (0,0)?

STAY UPDATED WITH BYTES!