K-Nearest Neighbors Search

EasyML Coding

Problem statement

Given a list of points in $n$-dimensional space (each a tuple), a query point and an integer k, return the k points closest to the query under Euclidean distance.

Implement k_nearest_neighbors(points, query_point, k):

  • Compute $d(p, q) = \sqrt{\sum_{i=1}^{n} (p_i - q_i)^2}$ from the query to every point.
  • Return the k points with the smallest distances, nearest first, as a list of tuples.
  • Ties: when two points are equally far, the one that appears earlier in the input list comes first.
  • If k exceeds the number of points, return all of them (sorted). If points is empty or k <= 0, return [].

Example

Input:

points = [(1, 2), (3, 4), (1, 1), (5, 6), (2, 3)]
query_point = (2, 2)
k = 3
print(k_nearest_neighbors(points, query_point, k))

Output:

[(1, 2), (2, 3), (1, 1)]

Reasoning: The distances from $(2, 2)$ are 1.0, 2.24, 1.41, 5.0 and 1.0. The three nearest are $(1, 2)$ and $(2, 3)$ at distance 1, then $(1, 1)$. The two points at distance 1 tie, so $(1, 2)$ comes first because it appears earlier in the input.

Show hint

Can you compute the distance from the query to every point in one array operation instead of a Python loop?

Relevant roles: ML Engineer, Data Scientist, Applied Scientist and AI Engineer.

Related free problems