Min Cost to Connect Points

The problem

Implement `minCostConnectPoints(points)` where `points[i] = [xi, yi]`. The cost to connect two points is their Manhattan distance, `|xi - xj| + |yi - yj|`. Return the minimum total cost to connect every point such that there's exactly one path between any pair — the minimum spanning tree over the complete graph of all pairwise Manhattan distances.

`points = [[0,0],[2,2],[3,3],[2,4],[4,2]]` returns `10`. Unlike every earlier graph entry, there's no `edges` input at all — every pair of points is a potential edge, and the question is which `n - 1` of the `n * (n - 1) / 2` possible ones make the cheapest tree.

The approach

There's no edge list to reuse this time — `points` gives coordinates, not connections, so every pair `(i, j)` becomes a candidate edge first, weighted by Manhattan distance, before Kruskal's algorithm (union-find, same as `redundantConnection`) can run at all. Sorting those candidate edges ascending by cost is what turns 'always take the cheapest edge that doesn't close a cycle' into a single linear pass instead of a search.

The `find`/union core — path compression, `parent[rootA] = rootB` — is unchanged from `redundantConnection`/`numberOfProvinces`/the Union-Find variant of `countComponents`; this is the fourth reuse of that exact primitive in this log, with the loop body changed a fourth way.

Where `redundantConnection` returned the instant it found an edge whose endpoints already shared a root — that was the whole answer — here it's the opposite edges, the ones whose endpoints *don't* share a root, that matter: each one is a genuine merge, so its cost is added to `totalCost` and `edgesUsed` increments. The loop stops as soon as `edgesUsed === n - 1`, since a spanning tree over `n` nodes never needs more edges than that.

The solution

class Solution {
    /**
     * @param {number[][]} points
     * @return {number}
     */
    minCostConnectPoints(points) {
        const n = points.length;
        const parent = Array.from({ length: n }, (_, i) => i);

        const find = (x) => {
            while (parent[x] !== x) {
                parent[x] = parent[parent[x]];
                x = parent[x];
            }
            return x;
        };

        const edges = [];
        for (let i = 0; i < n; i++) {
            for (let j = i + 1; j < n; j++) {
                const cost = Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1]);
                edges.push([cost, i, j]);
            }
        }
        edges.sort((a, b) => a[0] - b[0]);

        let totalCost = 0;
        let edgesUsed = 0;

        for (const [cost, a, b] of edges) {
            if (edgesUsed === n - 1) break;
            const rootA = find(a);
            const rootB = find(b);
            if (rootA !== rootB) {
                parent[rootA] = rootB;
                totalCost += cost;
                edgesUsed++;
            }
        }

        return totalCost;
    }
}

Time O(n^2 log n)Space O(n^2)