The O(n) Club: K Closest Points to Origin: Or, How to Avoid a Heap of Regret

The O(n) Club: K Closest Points to Origin—Or, How to Avoid a Heap of Regret

⚡ TL;DR

Don’t overthink it: Want the k closest 2D points to (0, 0)? Skip the Math.sqrt and use a max heap. Here’s Java’s recipe for less pain:

// Top k (closest) using a max heap
PriorityQueue<int> heap = new PriorityQueue<>((a, b) -> squaredDist(b) - squaredDist(a));
for (int[] p : points) {
    heap.offer(p);
    if (heap.size() > k) heap.poll();
}</int>

🧠 How Devs Usually Mess This Up

If you see someone using Math.sqrt on every point, please gently tell them Java isn’t free and their CPU would like a break. Also, sorting the whole list for a tiny k is like vacuuming your neighbor’s apartment after sweeping yours… not wrong, but a waste. And using a min heap? Well, that’s almost like auto-accepting the k people farthest away for your party. Awkward!

🔍 What’s Actually Going On

Picture yourself as a robot chef in a food court. You want to serve the k hungriest people closest to your kitchen, not the ones teleporting in from Antarctica. If you just compare everyone’s squared distance (x² + y²), you don’t need to measure out the roots—just spot whose number is smallest. Use a max heap: every time you find someone closer, you evict the farthest from your little VIP club. Simple, fast, dopamine-friendly.

🛠️ PseudoCode

• Define squared distance:

  int squaredDist(int[] p) = p[0]*p[0] + p[1]*p[1];

  Use squared distance to compare; nobody’s grading your math beauty here.

• Prepare max heap (size k):

  PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> squaredDist(b) - squaredDist(a));

  Set up your VIP velvet rope. Only top k get in.

• Heap all points:

  for each point in points:
      heap.offer(point)
      if heap.size() > k: heap.poll()

  The moment you exceed capacity, toss the farthest guest. Politely, of course.

• Return them all:

  // Your heap now holds k closest. Just pluck them all out to an array.

  Order isn’t specified. Nobody cares. Move on.

💻 The Code

public int[][] kClosest(int[][] points, int k) {
    PriorityQueue<int> heap = new PriorityQueue<>((a, b) -> squaredDist(b) - squaredDist(a));
    for (int[] point : points) {
        heap.offer(point);
        if (heap.size() > k) heap.poll();
    }
    int[][] res = new int[k][2];
    for (int i = 0; i < k; ++i) res[i] = heap.poll();
    return res;
}
private int squaredDist(int[] point) {
    return point[0] * point[0] + point[1] * point[1];
}
</int>

⚠️ Pitfalls, Traps & Runtime Smacks

• Math.sqrt Syndrome: Unnecessary. Like bringing a blender to cut onions.
• Wrong Heap Direction: Min heap gets you the farthest, which is what you don’t want (unless your app is “find k nearest exit-row seats from cockpit”).
• Surprise Ties: If distances are equal, return order is dealer’s choice. Don’t panic.
• Bad for k = n: If you want all points, just sort instead of flexing with a heap.

🧠 Interviewer Brain-Tattoo

“Comparing distances? Ditch the square root. Heap responsibly. Legacy code will thank you.”