Euclidean distance matrix

Background

A distance matrix holds the pairwise distances between two sets of points — the core operation behind k-NN, k-means assignment, kernel methods, and clustering. Computing it efficiently uses the identity $\lVert a - b\rVert^2 = \lVert a\rVert^2 + \lVert b\rVert^2 - 2\,a\cdot b$, which turns explicit per-pair subtraction into a single matrix product.

Problem statement

Implement pairwise_euclidean(A, B) returning the matrix of Euclidean distances between every row of A and every row of B:

$$D_{ij} = \lVert A_i - B_j\rVert_2 = \sqrt{\lVert A_i\rVert^2 + \lVert B_j\rVert^2 - 2\,A_i\cdot B_j}$$

Input

• A — np.ndarray of shape (n, d).
• B — np.ndarray of shape (m, d).

Output

Returns an np.ndarray of shape (n, m) where D[i, j] is the distance from A[i] to B[j].

Examples

Example 1

Input:  A = [[0, 0], [3, 4]], B = [[0, 0], [3, 0]]
Output: [[0, 3], [5, 4]]

Explanation: $\lVert[0,0]-[0,0]\rVert = 0$, $\lVert[0,0]-[3,0]\rVert = 3$, $\lVert[3,4]-[0,0]\rVert = 5$, and $\lVert[3,4]-[3,0]\rVert = 4$.

Constraints

• Vectorise via the $\lVert a\rVert^2 + \lVert b\rVert^2 - 2\,a\cdot b$ identity — no Python loops over points.
• Clamp tiny negative squared distances to 0 before the square root.
• Output shape is (n, m); tests compare with atol=1e-6.

Notes

• Squared distances can come out slightly negative from rounding; np.maximum(sq, 0) before sqrt avoids NaNs, notably on the zero diagonal when A is B.
• This is the kernel of k-NN and k-means: both reduce to "find the nearest row of B for each row of A".