K-Nearest Neighbors
The simplest classifier there is: to label a new point, look at the k closest labeled points and let them vote. No training, no weights — just distances. The whole model is the dataset. No numpy, just the math.
The problem
Implement k-nearest-neighbors classification. You are given points (a list of training feature vectors), labels (the integer class of each training point), a query vector, and an integer k. Measure the Euclidean distance from the query to every training point, take the k closest, and return the majority label among them. Tie-breaks (both deterministic): when two points are equidistant, prefer the one that appears earlier in points; when two labels are tied on votes, return the smaller label.
points=[[0,0],[10,10]], labels=[0,1], query=[1,1], k=10points=[[0,0],[0,1],[1,0],[10,10],[10,11],[11,10]], labels=[0,0,0,1,1,1], query=[0.5,0.5], k=30points=[[0,0],[2,0]], labels=[1,0], query=[1,0], k=20- Euclidean distance:
√(Σ (pᵢ − qᵢ)²)across the feature dimensions. - Break distance ties by original index (earlier point in
pointsis "nearer"). - Break vote ties by returning the smaller integer label.
- Pyodide has no numpy — use the
mathstdlib and plain lists only.
Your turn — write it
Edit the stub, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are right above and Reveal solution is one click away.
Implement knn(points, labels, query, k). Find the k training points closest to the query by Euclidean distance, then return the majority label (smaller label wins a vote tie).
- For each training point compute √(Σ (pᵢ − qᵢ)²) to the query.
- Sort by (distance, original index) so equidistant points keep a stable order, then take the first k.
- Tally the labels of those k neighbors in a dict / Map.
- Return the label with the most votes; on a tie, the smaller label.
Explore the topic
See this challenge alongside everything else on the same subject — handbooks, system designs, algorithms and tools, in one place.