Unlabelled Seed Packet
A community seed library has a jar of seeds whose label fell off. Volunteers have measured many labelled seeds before (length and width in millimetres, sometimes more features), and they measure one seed from the mystery jar.
Their rule: find the k labelled seeds that are closest to the mystery seed, and go with the most common label among them. This is k-nearest neighbours, one of the simplest classifiers there is. The same "find the closest stored examples" step sits behind recommendation systems and embedding search.
Your task
Write classifySeed(seeds, labels, query, k). seeds[i] is a list of measurements with label labels[i]. query has the same number of measurements. Use straight-line (Euclidean) distance.
- Rank all seeds by distance to
query, nearest first. If two seeds are equally far, the one with the lower index ranks first. - Take the first
k. Return the label that appears most often among them. - If several labels tie for most votes, return the tied label whose highest-ranked seed comes first.
classifySeed(seeds: float[][], labels: string[], query: float[], k: int) → string
Examples
seeds = [[5, 2], [6, 2], [2, 1], [3, 1], [6, 3]] labels = ["rye", "rye", "flax", "flax", "oat"] query = [5, 3] k = 3
"rye"
Squared distances to (5, 3) are 1, 2, 13, 8 and 1. Ranked: seed 0 (1), seed 4 (1, higher index), seed 1 (2). Their labels are rye, oat, rye. Rye has 2 votes, so the answer is "rye".
seeds = [[0, 0], [4, 0], [0, 5], [10, 10]] labels = ["oat", "rye", "rye", "oat"] query = [1, 0] k = 2
"oat"
Distances: 1, 3, about 5.1 and about 13.5. The 2 nearest are seed 0 (oat) and seed 1 (rye), one vote each. The tie goes to the label whose seed ranks first: seed 0 is nearer, so the answer is "oat".
seeds = [[1], [2], [3], [10], [11]] labels = ["a", "a", "a", "b", "b"] query = [9] k = 1
"b"
With one measurement, distance is just the gap. The nearest seed to 9 is 10, label "b". With k = 1 the nearest seed decides alone, even though most seeds overall are "a".
Constraints
- 1 ≤ k ≤ seeds.length ≤ 1,000
- 1 ≤ number of measurements ≤ 10
- -1,000 ≤ each measurement ≤ 1,000
- Labels are non-empty lowercase strings.
Start with brute force
Pick the nearest seed, then the nearest of the rest, and so on, k times. Each pick scans every seed, so it costs O(n · k), which becomes O(n²) when k is close to n.
Sorting once by distance costs O(n log n) and gives the whole ranking. The bigger risks here are the rules, not the speed: forgetting the index tie-break, breaking vote ties alphabetically, or voting over all seeds instead of the nearest k.
Hints
0 of 4 shown- Hint 1
In the first example, list the five distances first. Which seeds end up in the top 3, and does it matter which of the two seeds at distance 1 comes first?
- Hint 2
You only compare distances with each other, never use their values. Is the order of squared distances the same as the order of real distances? That saves a square root per seed.
- Hint 3
Rank seeds by the pair (distance, index). That one rule handles equal distances. Then count labels among the first
k. - Hint 4
Sort indexes by (squared distance, index). Count labels in the first
k. Find the top count, then walk the firstkagain in rank order and return the first label whose count equals the top. That walk is exactly the tie rule.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
k-nearest neighbours has no training step. All the work happens when a question arrives: measure the distance to every stored example, keep the closest k, and let them vote.
Trace the first example, query (5, 3), k = 3, using squared distances:
- Seed 0 (5, 2): 0 + 1 = 1. Seed 1 (6, 2): 1 + 1 = 2. Seed 2 (2, 1): 9 + 4 = 13. Seed 3 (3, 1): 4 + 4 = 8. Seed 4 (6, 3): 1 + 0 = 1.
- Sort by (distance, index): seed 0, seed 4, seed 1, seed 3, seed 2.
- First 3 labels: rye, oat, rye. Votes: rye 2, oat 1.
- Top count is 2. Walking in rank order, rye is the first label with 2 votes. Return "rye".
Squared distances work because squaring keeps the order of non-negative numbers: if one distance is smaller, its square is smaller too. It also avoids rounding differences that a square root could add between two equal distances.
function classifySeed(seeds, labels, query, k) {
// Squared distance: same order as real distance, no square root needed.
const dist = (p) => p.reduce((sum, v, d) => sum + (v - query[d]) ** 2, 0);
const order = seeds.map((p, i) => [dist(p), i]);
order.sort((a, b) => a[0] - b[0] || a[1] - b[1]); // nearer first, then lower index
const votes = new Map();
let best = null;
for (let r = 0; r < k; r++) {
const label = labels[order[r][1]];
votes.set(label, (votes.get(label) || 0) + 1);
}
// Walk neighbours nearest-first: the first label to reach the top count wins ties.
const top = Math.max(...votes.values());
for (let r = 0; r < k && best === null; r++) {
const label = labels[order[r][1]];
if (votes.get(label) === top) best = label;
}
return best;
}def classify_seed(seeds, labels, query, k):
# Squared distance: same order as real distance, no square root needed.
def dist(p):
return sum((v - q) ** 2 for v, q in zip(p, query))
order = sorted(range(len(seeds)), key=lambda i: (dist(seeds[i]), i))
nearest = [labels[i] for i in order[:k]]
votes = {}
for label in nearest:
votes[label] = votes.get(label, 0) + 1
top = max(votes.values())
# Walk neighbours nearest-first: the first label to reach the top count wins ties.
for label in nearest:
if votes[label] == top:
return labelRun your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.