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

Optimize Water Distribution in Village

Problem (restated)

n houses. Building a well at house i costs wells[i-1]. Bidirectional pipes [house1, house2, cost] share water. Return the minimum cost so every house has water.

Intuition

A well is “a pipe from a virtual reservoir.” Add node 0 connected to house i with weight wells[i-1], then MST the n+1 nodes. Kruskal picks the cheapest mix of wells and pipes.

Approaches

Kruskal, virtual well

Unverified

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

Idea. Edges = well-edges (0, i, wells[i-1]) plus pipes. Sort, union until n edges (tree on n+1 vertices).

Walkthrough. n=3, wells [1,2,2], pipes [[1,2,1],[2,3,1]]. Well at 1 (cost 1) plus two pipes (1+1) beats three wells. Total 3.

Trade-offs. The template lists Prim for this id; Kruskal with a virtual node is the same MST. Houses are 1-indexed.

Solution

export function minCostToSupplyWater(n: number, wells: number[], pipes: number[][]): number {
  const edges: number[][] = [];
  for (let i = 0; i < n; i++) edges.push([0, i + 1, wells[i]!]);
  for (const p of pipes) edges.push(p);
  edges.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) return cost;
  }
  return cost;
}

export function minCostToSupplyWater(n: number, wells: number[], pipes: number[][]): number {
  const edges: number[][] = [];
  for (let i = 0; i < n; i++) edges.push([0, i + 1, wells[i]!]);
  for (const p of pipes) edges.push(p);
  edges.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) return cost;
  }
  return cost;
}

Template connection

Kruskal after a modeling trick. Same UF as LC 1135; the extra vertex encodes “build a well.”

Reflection

A well is an edge from a virtual node 0 to a house. Pipes are the real edges. Kruskal takes n edges on n + 1 vertices.
An expensive well loses to a cheap pipe. If every house already has its own well, no pipe is required.
One house costs that house’s well. The virtual node connects every house, so no component is left out.