k-means vs KNN: what is the difference?

In this article

1. Before you start
2. Why interviewers ask this
3. What each one is
4. Worked example
5. Trade-offs and edge cases
6. How to answer it in an interview
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

Why interviewers ask this

The two names share a letter and a distance, so they are easy to mix up, and mixing them up reveals whether a candidate knows what problem each one solves. Questions on this topic include "how does k-means work and what formula does it minimise", "how do you choose k", "what is the curse of dimensionality", and "for a million data points would you use a deep network or KNN".

A weak answer says "both use distance to find neighbours". A strong answer says that k-means has no labels and learns centroids, that KNN has labels and learns no parameters, that the k in each means something different, and that the cost lands at different times: training for one, prediction for the other.

What each one is

k-means

k-means is a clustering algorithm that splits unlabeled points into k groups by choosing k centre points so that the total squared distance from each point to its nearest centre is as small as it can get. It needs k in advance and returns the groups.

k-nearest neighbors

k-nearest neighbors (KNN) is a prediction method that stores every labeled training example and answers a query by finding the k stored points closest to it and returning their majority label, or the average of their values for a number. It learns no parameters; at most it builds a search index, such as a k-dimensional (KD) tree, when it is fitted.

k-means in plain words

k-means repeats two moves: assign every point to its nearest centroid, then move each centroid to the mean of its points. The scikit-learn 1.9.1 guide calls this Lloyd's algorithm: initialise the centroids, assign each sample to its nearest centroid, update each centroid to the mean of its samples, and repeat until they stop moving. Its centroids "are not, in general, points from X". Think of three post offices placed so walks to the nearest one are short. The analogy breaks in one place: the mean minimises the total of squared walks, not the total walk. For houses at 1, 2 and 9 the mean is 4 with a total walk of 10, while the median, 2, gives 8.¹

The guide says k-means always converges, but possibly to a local minimum (a result no small change improves, though a better one may exist) that depends on the starting centroids. It describes k-means++ initialisation as picking starting centroids that are generally far apart. The KMeans reference page (read 2026-10-26) makes init='k-means++' the default and runs it once, against 10 runs for init='random'.

KNN in plain words

KNN remembers all labeled examples and, for a new point, takes a vote among the k closest. The scikit-learn guide calls neighbours-based methods "non-generalizing" because they "simply 'remember' all of its training data", and says classification "is computed from a simple majority vote of the nearest neighbors of each point". The k here is the number of voters: the guide says a larger k suppresses the effects of noise but makes the classification boundaries less distinct. Think of asking the five nearest neighbours which shop to use and following the majority. The analogy breaks when the neighbours are not like you in the way that matters, because KNN trusts the distance measure completely.

Why does KNN cost more at prediction time than k-means?

KNN does its work when you ask, and k-means did its work when you trained. To label one query, brute-force KNN compares the query with every stored point, so with a million points of 128 numbers that is 128,000,000 multiply-adds for each query. A multiply-add is one multiplication plus one addition, the unit step of a distance calculation. A trained k-means model compares a query only with its k centroids, so with k = 100 it is 12,800, which is 10,000 times less¹. The scikit-learn nearest-neighbors guide gives the same shape: brute-force query time grows in proportion to D times N, which it writes O[D N], where D is the number of dimensions and N the number of stored samples.

The cost moves the other way at training time. k-means must run many passes, and one pass over a million points with 100 centroids is 12.8 billion multiply-adds¹, while KNN learns no parameters, so its training is at most building a search index. This is the number-gap an interviewer is probing: where each method spends its compute.

Worked example

A synthetic set of 300 points, 100 from each of three overlapping Gaussian blobs (bell-shaped clouds of points around a centre) in two dimensions, each with a standard deviation of 1.5 (a typical distance from the centre; seed 0), shows each method on data where the truth is known. The data is illustrative, not from a real problem¹.

The two k values in the two tables are unrelated.

The drop in inertia from k = 2 to k = 3 is 1,275, against 184 from k = 3 to k = 4, which is the bend, called the elbow, that suggests three clusters; the three centroids at k = 3 land near the true centres, at about (−0.25, 0.24), (2.63, 4.64) and (4.89, −0.31) against true centres at (0, 0), (2.5, 4.5) and (5, 0)¹. For KNN, accuracy hardly moves from k = 1 to k = 51 and drops to 0.8889 at k = 150, when each vote covers most of the 210 training points. On 90 test points one point is 1.1 percentage points, so differences of one or two points are noise.

Text description of the diagram

• Inertia is 3935.4 at k = 1, 1136.2 at k = 3 and 664.2 at k = 6.
• The drop in inertia from k = 2 to k = 3 is 1,275, against 184 from k = 3 to k = 4.

The proof that the centroid is the mean takes two lines. For points $x_1,\dots ,x_n$ and a candidate centre $c$, the squared error is ${\sum }_i(x_i-c{)}^2$, and setting its derivative to zero gives:

That is the mean for any set of points, which is why k-means updates centroids by averaging. For the points 1, 2 and 9 the mean is 4 and the squared error around it is 38, while around the median, 2, it is 50¹.

Trade-offs and edge cases

The choice follows from what you have and what you want. The table summarises the differences; the cases below it are where each method breaks.

Three cases matter. First, shape: the scikit-learn clustering guide says inertia assumes clusters are convex (no dents) and isotropic (spread evenly in every direction), and responds poorly to elongated or irregular ones. Second, scale: both methods use distances, so a feature measured in thousands drowns one measured in fractions; standardise features first, as the feature engineering page explains. Third, dimensions: the curse of dimensionality is the loss of meaning of distance as the number of dimensions grows. Beyer et al. (1999) show that under broad conditions the distance to the nearest point approaches the distance to the farthest, and report the effect for as few as 10 to 15 dimensions while noting some high-dimensional workloads avoid it.

For 1,000 uniform random points and 200 random queries in each dimension count, the median query finds its nearest point at 0.014 of the distance to its farthest point in 2 dimensions, 0.262 in 10, 0.697 in 100 and 0.894 in 1,000¹. A share near 1 means every point is about equally far, so "nearest" carries little information.

The scikit-learn nearest-neighbors guide reports the same pressure on tree-based search: KD trees are efficient below about 20 dimensions and become inefficient as dimensions grow, and its automatic setting chooses brute force above 15 dimensions. Use dimensionality reduction before either method, for example principal component analysis, which replaces many correlated features with a few new axes that keep most of the variation; the clustering guide suggests it before k-means.

Text description of the diagram

• For 1,000 uniform random points, the nearest point is a median of 0.014 of the distance to the farthest in 2 dimensions.
• That share is 0.262 in 10 dimensions, 0.697 in 100 and 0.894 in 1,000.

For a million labeled points, the choice is between a trained network and a stored-data lookup. A small illustrative network with layers of 128, 512, 512 and 10 units costs 332,800 multiply-adds per query whatever the training set size, against 128 million for brute-force KNN search¹. Approximate neighbour search, covered in similarity search and embeddings and vector search, narrows the gap, but the network's query cost is still fixed by its size.

Text description of the diagram

• With labels and a prediction goal, use KNN.
• Without labels, use k-means to group the points.

How to answer it in an interview

The spoken structure is: split by labels, define each in one line, say what k means in each, compare the cost, then add the distance caveat.

Common mistakes

• "KNN is the supervised version of k-means" (wrong). They are separate algorithms with different goals (right: k-means groups, KNN predicts).
• "k means the same in both" (wrong). It is the number of clusters in one and of voters in the other (right: say which).
• "k-means finds the best clustering" (wrong). It converges to a local minimum that depends on the start, so the start matters; scikit-learn's default k-means++ start runs once, while init='random' runs 10 starts and keeps the lowest inertia (right: say the result depends on the start, and that best of several starts is a choice you make).
• "Pick k where inertia is smallest" (wrong). Inertia always falls as k grows, to zero when k equals the number of points (right: look for the bend).
• "Skip feature scaling" (wrong). A large-scale feature dominates the distance (right: standardise first).

Follow-up questions

How to choose k in k-means?

Run k-means for a range of k, plot inertia, and pick the bend where extra clusters stop buying much, as in the elbow at k = 3 above. Check the clusters make sense for the use case, since inertia alone never says that.

What is the curse of dimensionality, and when should you reduce dimensions?

As dimensions grow, distances between random points concentrate, so the nearest neighbour is barely nearer than the farthest, as the nearest point sitting at 0.894 of the farthest distance at 1,000 dimensions shows. Reduce dimensions, for example with principal component analysis, when many features are correlated or noisy.

Can you write the formula for the distance that you minimize?

k-means minimises inertia, the sum over all points $x_i$ of the squared Euclidean distance to the nearest centroid ${\mu }_j$:

$$J=\sum _{i=1}^N\underset{j}{\min }\Vert x_i-{\mu }_j{\Vert }^2$$

Here $N$ is the number of points, $x_i$ is point $i$, ${\mu }_j$ is centroid $j$, and $\Vert ·\Vert$ is the straight-line length of the gap. In words, $J$ is the sum of squared gaps between each point and its closest centroid, the same quantity the scikit-learn guide defines as inertia.

What is the distance between two points in n dimensions?

The Euclidean distance between $x$ and $y$ is the square root of the sum of squared coordinate gaps, over all n coordinates:

$$d(x,y)=\sqrt{\sum _{i=1}^n(x_i-y_i{)}^2}$$

For $(0,0)$ and $(3,4)$ it is $\sqrt{9+16}=5$. Other choices exist, such as the Hamming distance for bit strings, covered on the Hamming distance page.

If you have a million data points, would you use a deep network or KNN?

If you have labels and queries are frequent, a trained network has a query cost fixed by its size, while brute-force KNN scales with the data. KNN is reasonable for small data, for a quick baseline, or with an approximate index. The bias-variance page explains how a choice like k trades flexibility against noise, and the interview loops guide shows how rounds like this one are structured.

Sources

1. sklearn.cluster.KMeans (scikit-learn 1.9.1 API reference) — scikit-learn developers, 26 Oct 2026
2. Clustering: K-means (scikit-learn 1.9.1 user guide, section 2.3.2) — scikit-learn developers, 26 Oct 2026
3. Nearest Neighbors (scikit-learn 1.9.1 user guide, section 1.6) — scikit-learn developers, 26 Oct 2026
4. When Is 'Nearest Neighbor' Meaningful? (Beyer, Goldstein, Ramakrishnan, Shaft), ICDT'99, LNCS 1540 (Springer, 1998) — Springer LNCS (copy hosted by LORIA), 24 Oct 2026