Definition
- Max-heap of size K – the root is the farthest of the K points currently kept, making the keep-or-discard decision a single comparison.
- Squared distance – comparing x*x + y*y avoids the cost and precision loss of computing the actual square root.
- Eviction rule – a new point replaces the root only if its squared distance is less than the root's, keeping the K closest.
- Order preservation – squared distance preserves the same ordering as Euclidean distance, so the results are identical.
- Integer safety – when coordinates are integers, squared distance stays in integer arithmetic, avoiding floating-point rounding.
At the National Bank of India, each branch is a point on a map and the operations team wants the K branches nearest to head office at the origin for a cash-logistics route. They keep a small bucket of the K nearest branches, with the farthest of them on top. A new branch enters only if it is nearer than that farthest one, and they rank by distance-squared to avoid unnecessary square root calculations.
Understanding the Concepts
What is the K Closest Points problem?
Given a list of points on a 2D plane, each with coordinates (x, y), and a value K, find the K points closest to the origin (0, 0). The result does not need to be sorted by distance. This is a Top K Elements problem where the comparison key is distance from the origin.
package com.bank.logistics;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
public class KClosestPoints {
public static List<int[]> findKClosest(int[][] branches, int k) {
// Max-heap by squared distance (farthest at root)
PriorityQueue<int[]> maxHeap = new PriorityQueue<>(
(a, b) -> squaredDist(b) - squaredDist(a)
);
for (int[] branch : branches) {
if (maxHeap.size() < k) {
maxHeap.offer(branch);
} else if (squaredDist(branch) < squaredDist(maxHeap.peek())) {
maxHeap.poll();
maxHeap.offer(branch);
}
}
return new ArrayList<>(maxHeap);
}
private static int squaredDist(int[] point) {
return point[0] * point[0] + point[1] * point[1];
}
}
Why use squared distance instead of Euclidean distance?
The Euclidean distance from a point (x, y) to the origin is sqrt(x*x + y*y). But for ordering purposes, comparing x*x + y*y gives the same result because the square root is a monotonically increasing function. Using squared distance avoids two costs: the computational expense of the square root operation, and the floating-point precision loss that comes with it. When coordinates are integers, squared distance stays entirely in integer arithmetic.
package com.bank.logistics;
public class SquaredDistDemo {
public static void compare() {
int[] branchA = {3, 4}; // squared dist = 9 + 16 = 25, actual = 5.0
int[] branchB = {1, 1}; // squared dist = 1 + 1 = 2, actual = 1.414...
int[] branchC = {2, 3}; // squared dist = 4 + 9 = 13, actual = 3.605...
// Ordering by squared distance: B(2) < C(13) < A(25)
// Ordering by Euclidean: B(1.414) < C(3.605) < A(5.0)
// Same ordering! No need for square root.
// Bonus: no floating-point rounding issues
System.out.println("Squared distances: A=25, B=2, C=13");
System.out.println("Same order as Euclidean, no sqrt needed");
}
}
Why use a max-heap instead of a min-heap for closest points?
This is the symmetric choice from Top K Largest. To find the K closest (smallest distances), you use a max-heap so the root is the farthest of the K kept points. The root is the weakest candidate: if a new point is closer than the root, it deserves a place and the root is evicted. A min-heap would have the closest point at the root, giving no efficient way to find and evict the farthest.
// Max-heap for K closest (root = farthest of K nearest):
// New point closer than root? → evict root, insert new point
// New point farther? → discard
// Min-heap for K largest (root = smallest of K largest):
// New number larger than root? → evict root, insert new number
// New number smaller? → discard
// Pattern: the heap root is always the WEAKEST candidate
// For "K largest": weakest = smallest → use min-heap
// For "K closest": weakest = farthest → use max-heap
How does the keep-or-discard decision work?
Fill the heap with the first K points. For each subsequent point, compare its squared distance with the root's squared distance. If the new point is closer, poll the root and offer the new point. After processing all points, the heap contains the K closest.
package com.bank.logistics;
import java.util.PriorityQueue;
public class KeepOrDiscardDemo {
public static void trace() {
int[][] branches = {{3,4}, {1,1}, {5,5}, {2,3}, {0,1}};
int k = 3;
// Squared distances: 25, 2, 50, 13, 1
// Fill K=3: heap = [(3,4)=25, (1,1)=2, (5,5)=50], root=(5,5)=50
// (2,3)=13 < 50? Yes → evict (5,5), insert (2,3)
// heap = [(3,4)=25, (1,1)=2, (2,3)=13], root=(3,4)=25
// (0,1)=1 < 25? Yes → evict (3,4), insert (0,1)
// heap = [(2,3)=13, (1,1)=2, (0,1)=1], root=(2,3)=13
// Final: 3 closest = (1,1), (0,1), (2,3)
}
}
What is the time and space complexity?
| Approach | Time | Space | Notes |
|---|---|---|---|
| Sort by distance | O(n log n) | O(1) | Simple but slower for small K |
| Max-heap of size K | O(n log K) | O(K) | Optimal for small K |
| Quickselect on distance | O(n) average | O(1) | Best average, O(n^2) worst |
What about overflow with squared distance?
When coordinates are large, x*x can overflow a 32-bit int. For safety, cast to long before multiplying. In a banking context where branch coordinates might be in meters or grid units, this is important for precision.
package com.bank.logistics;
public class OverflowSafety {
private static long squaredDistSafe(int[] point) {
return (long) point[0] * point[0] + (long) point[1] * point[1];
}
public static void showRisk() {
int[] farBranch = {50000, 50000};
// int: 50000*50000 = 2,500,000,000 → overflows int (max ~2.1 billion)
// long: 50000L*50000 = 2,500,000,000L → correct
System.out.println("Safe squared distance: " + squaredDistSafe(farBranch));
}
}
What are common mistakes?
The most common mistake is using a min-heap instead of a max-heap, which keeps the closest point at the root and gives no way to evict the farthest. Another mistake is computing the actual Euclidean distance with Math.sqrt, introducing unnecessary floating-point arithmetic.
package com.bank.logistics;
public class CommonMistakes {
// WRONG: min-heap for K closest
// Root = closest point, cannot identify farthest to evict
// Fix: use max-heap so root = farthest of K kept
// WRONG: using Math.sqrt for comparison
public static double wrongDistance(int[] p) {
return Math.sqrt(p[0] * p[0] + p[1] * p[1]); // unnecessary!
}
// CORRECT: squared distance
public static int correctDistance(int[] p) {
return p[0] * p[0] + p[1] * p[1]; // same ordering, no sqrt
}
}
What are common interview follow-up questions?
Interviewers may ask how to find K closest to an arbitrary point instead of the origin (just subtract the point coordinates before computing distance), how to handle 3D points (add z*z to the squared distance), or how to handle a stream of points arriving one at a time (the heap approach works naturally for streaming).
// Follow-up: K closest to arbitrary point (px, py)
private static int squaredDistTo(int[] point, int px, int py) {
int dx = point[0] - px;
int dy = point[1] - py;
return dx * dx + dy * dy;
}
// Follow-up: 3D points
private static int squaredDist3D(int[] point) {
return point[0]*point[0] + point[1]*point[1] + point[2]*point[2];
}
Visual Overview
Max-Heap for K Closest Points
==============================
Branches: (3,4)=25 (1,1)=2 (5,5)=50 (2,3)=13 (0,1)=1
K=3
Step 1: Fill to size K
(3,4)=25 → heap
(1,1)=2 → heap
(5,5)=50 → heap root = (5,5) dist=50
Step 2: Keep-or-discard
(2,3)=13 < 50? Yes → evict (5,5)
heap: root = (3,4) dist=25
(0,1)=1 < 25? Yes → evict (3,4)
heap: root = (2,3) dist=13
Final K=3 closest: (1,1), (0,1), (2,3)
Heap Structure (max-heap by squared dist)
=========================================
┌──────┐
│(2,3) │ dist=13 ← root (farthest of K nearest)
│ │
└──┬───┘
┌───┴───┐
┌──┴──┐ ┌──┴──┐
│(1,1)│ │(0,1)│
│ d=2 │ │ d=1 │
└─────┘ └─────┘
New point arrives:
┌────────────────────────┐
│ dist(new) < dist(root)?│
├───────┬────────────────┤
│ Yes │ No │
│ Evict │ Discard │
│ root │ new point │
└───────┴────────────────┘
Squared Distance vs Euclidean
==============================
Point (3,4):
Squared: 3*3 + 4*4 = 25 (integer, fast)
Euclidean: sqrt(25) = 5.0 (float, slow)
Ordering preserved: sqrt is monotonic
2 < 13 < 25 ⟺ 1.41 < 3.61 < 5.0
Key Takeaway
K Closest Points to the Origin is a Top K Elements problem where the comparison key is distance from the origin, and you solve it with a max-heap of size K ordered by squared distance. The root of the max-heap is the farthest of the K points you are currently keeping, so the keep-or-discard decision for each new point is a single comparison: if the new point is closer than the root, evict the root and insert the new point.
The squared distance optimization is a telling detail of numerical care. Comparing x*x + y*y gives the same ordering as Euclidean distance because the square root is monotonically increasing, but squared distance avoids the computational cost of sqrt and, when coordinates are integers, avoids floating-point rounding entirely by staying in integer arithmetic.
At the National Bank of India, the operations team used this to find the K branches nearest head office for planning cash-logistics routes. They kept a size-K max-heap keyed on squared distance, so each nearer branch evicted the farthest kept one. The route planner ran in O(n log K) time without sorting all branches.
The senior-level insight is knowing when to use max-heap versus min-heap: for K largest use min-heap (root = weakest = smallest), for K closest use max-heap (root = weakest = farthest). Always watch for integer overflow in squared distance when coordinates are large.
Remember one sentence: max-heap of size K by squared distance, evict the farthest kept point when a closer one arrives, and never compute the actual square root.
---