Pinterest uses nearest-neighbor methods as one signal for understanding and grouping visually similar Pins. Given labeled training vectors and one query vector, implement a K-Nearest Neighbors classifier that predicts the query's label efficiently.
Implement knn_predict(points, labels, query, k). points is a list of n vectors, labels[i] is the label for points[i], and query is a vector with the same dimensionality. Return the label occurring most often among the k nearest points. Use squared Euclidean distance, since the square root does not affect ordering. If multiple labels have the same highest frequency, return the numerically smallest label.
When distances tie while selecting neighbors, prefer the point with the smaller original index. This makes the result deterministic.
def knn_predict(points, labels, query, k):