Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumminimum-spanning-tree

Connecting Cities With Minimum Cost

Problem (restated)

n cities 1…n and bidirectional connections [x, y, cost]. Return the minimum cost to connect all cities, or -1 if impossible.

Intuition

Connect every city at minimum total cost — that is an MST. Kruskal: sort edges, union-find skips cycles, stop at n-1 edges.

Approaches

Kruskal

Unverified

Time O(E log E)Space O(n)

Idea. Sort by cost. Union endpoints unless already connected. If you ever take n-1 edges, that sum is the answer; leftover components → -1.

Walkthrough. n=3, [[1,2,5],[1,3,6],[2,3,1]]. Take 2-3 (1), then 1-2 (5). Total 6. The 1-3 edge is a cycle.

Trade-offs. Cities are 1-indexed — size the parent array n+1. Prim is the same MST on a dense graph; here E is given explicitly.

Solution

export function minimumCost(n: number, connections: number[][]): number {
  const edges = [...connections].sort((a, b) => a[2]! - b[2]!);
  const parent = Array.from({ length: n + 1 }, (_, i) => i);
  const find = (x: number): number => (parent[x] === x ? x : (parent[x] = find(parent[x]!)));
  let cost = 0, used = 0;
  for (const e of edges) {
    const a = find(e[0]!), b = find(e[1]!);
    if (a === b) continue;
    parent[a] = b;
    cost += e[2]!;
    used++;
    if (used === n - 1) return cost;
  }
  return -1;
}

export function minimumCost(n: number, connections: number[][]): number {
  const edges = [...connections].sort((a, b) => a[2]! - b[2]!);
  const parent = Array.from({ length: n + 1 }, (_, i) => i);
  const find = (x: number): number => (parent[x] === x ? x : (parent[x] = find(parent[x]!)));
  let cost = 0, used = 0;
  for (const e of edges) {
    const a = find(e[0]!), b = find(e[1]!);
    if (a === b) continue;
    parent[a] = b;
    cost += e[2]!;
    used++;
    if (used === n - 1) return cost;
  }
  return -1;
}

Template connection

Plain Kruskal. LC 1584 builds the edge list from Manhattan pairs first; LC 1168 adds a virtual well node.

Reflection

Sort edges by cost and union with a disjoint set. If you cannot take n - 1 edges, the answer is −1.
An edge whose ends already share a root is a cycle and is skipped. Equal costs do not change the total.
n = 1 answers 0. A disconnected city is −1. The MST cost is the sum of the chosen edges.