Introduction

To find the k nearest points to a target point in a 2D plane, you compare distances from the target and keep the smallest ones. The best implementation depends on the size of the input and whether you need a fully sorted answer or just the nearest set.

Start with Squared Distance

You do not need the square root to compare Euclidean distances. Squared distance is enough and avoids extra computation.

1def squared_distance(point, target):
2    dx = point[0] - target[0]
3    dy = point[1] - target[1]
4    return dx * dx + dy * dy

That works because the square root function preserves ordering. If point A has a smaller squared distance than point B, it also has a smaller actual distance.

Use a Max-Heap for O(n log k)

When n is large and k is much smaller, a max-heap of size k is a strong general solution. Keep the closest k points seen so far and discard anything farther away.

1import heapq
2
3
4def k_nearest(points, target, k):
5    heap = []
6
7    for point in points:
8        dist = squared_distance(point, target)
9        entry = (-dist, point)
10
11        if len(heap) < k:
12            heapq.heappush(heap, entry)
13        else:
14            heapq.heappushpop(heap, entry)
15
16    return [point for _, point in heap]
17
18
19points = [(1, 2), (2, 3), (3, 3), (6, 6), (1, -1)]
20print(k_nearest(points, (2, 2), 2))

The heap stores the current best k points, with the farthest of those k at the top. That makes replacement efficient when a closer point appears.

Sort When Simplicity Matters More Than Asymptotic Cost

If the dataset is moderate or you need the results sorted by distance anyway, sorting may be simpler:

def k_nearest_sorted(points, target, k):
    ranked = sorted(points, key=lambda p: squared_distance(p, target))
    return ranked[:k]

This costs O(n log n), which is fine for many real programs and easier to explain in interviews or small utilities.

For very large inputs, a selection algorithm such as quickselect can reduce the average cost toward linear time, but the heap solution is often the best balance of clarity and performance.

If the points are reused for many nearest-neighbor queries rather than one query, a spatial index such as a k-d tree can be a better long-term choice than recomputing distances from scratch every time in production systems at scale globally.

Common Pitfalls

The biggest mistake is computing the full Euclidean distance with square roots when only comparison is needed. That adds work without changing the ranking.

Another common issue is choosing the wrong data structure for the constraints. Sorting everything is simple, but it does more work than necessary when k is tiny compared with n.

People also forget tie behavior. If several points are equally distant from the target, the problem statement may allow any order, but production code should be clear about whether stable ordering matters.

Finally, watch for edge cases:

• 'k = 0'
• 'k greater than the number of points'
• duplicate points
• negative coordinates

Those cases are usually easy to support once you decide the desired behavior.

Summary

• Compare squared distances instead of using square roots.
• Use a max-heap of size k for an efficient O(n log k) solution.
• Use sorting when simplicity is more important than minimizing work.
• Quickselect can be faster on average, but it is more complex to implement correctly.
• Pick the approach that matches the input size and the output-ordering requirement.