hard

Optimize Water Distribution in a Village

Minimize the total cost of wells and pipes needed to supply water to every house.

1. Define the problem

Optimize Water Distribution in a Village

There are n houses numbered 1 to n. For house i, you can either build a well directly in that house for wells[i - 1], or connect it to another house that already has water using a pipe from pipes, where pipesj = [house1, house2, cost] is the cost to lay a pipe between two houses. Return the minimum total cost so every house has water. Add a virtual source node connected to every house by an edge weighted at that house's well cost — a well is just another edge once you do that. Then run Prim's algorithm from the source: grow the tree by always absorbing the cheapest frontier edge, whether it is a well or a pipe.

Constraints

  • 1 ≤ n ≤ 104
  • wells.length == n
  • 0 ≤ wellsi ≤ 105
  • 0 ≤ pipes.length ≤ 104
  • pipesj.length == 3
  • 1 ≤ house1, house2 ≤ n
  • 0 ≤ cost ≤ 105
  • house1 != house2

Example

Inputn = 3, wells = [1, 2, 2], pipes = [[1, 2, 1], [2, 3, 1]]
Output3

Explanation Dig a well at house 1 for 1, then pipe water to house 2 for 1 and on to house 3 for 1. Total cost 1 + 1 + 1 = 3.

2. Know the words first

In plain terms

Virtual source node
A fictional extra node added purely to model a choice — here, digging a well — as just another edge weight in the same graph.
Frontier edge
The cheapest known edge connecting the tree built so far to a house that doesn't have water yet.
3. Visualize the solution

Grow the tree from a virtual source made of well costs

Grow the tree from a virtual source made of well costs
Statusinit

Add a virtual source with an edge to every house, weighted by that house's well cost: House 1 costs 1, House 2 and House 3 cost 2 each.

What happens in this step

virtual source (node 0) connects to every house with an edge weighted by that house's well cost:
0→House1 (w=1), 0→House2 (w=2), 0→House3 (w=2)

tree = {source}. cheapest frontier edge is 0→House1 (w=1) — absorb it next.
Step 1 of 4

Steps to visualize

  1. Add a virtual source connected to every house by an edge weighted at that house's well cost.
  2. Run Prim's algorithm from the source: always absorb the cheapest frontier edge.
  3. A pipe to an already-reachable house only updates the frontier when it beats the current best known cost for that house.
  4. The total of every absorbed edge is the minimum cost — wells and pipes are just different edge weights in the same graph.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Grow the tree from a virtual source made of well costs
Statusinit

Add a virtual source with an edge to every house, weighted by that house's well cost: House 1 costs 1, House 2 and House 3 cost 2 each.

What happens in this step

virtual source (node 0) connects to every house with an edge weighted by that house's well cost:
0→House1 (w=1), 0→House2 (w=2), 0→House3 (w=2)

tree = {source}. cheapest frontier edge is 0→House1 (w=1) — absorb it next.
Step 1 of 4
5. Solution

Solution

solution.tsTypeScript
function minCostToSupplyWater(n, wells, pipes) {
  const adjacency = new Map();
  for (let house = 0; house <= n; house++) adjacency.set(house, []);
  for (let house = 1; house <= n; house++) {
    adjacency.get(0).push([house, wells[house - 1]]);
    adjacency.get(house).push([0, wells[house - 1]]);
  }
  for (const [a, b, cost] of pipes) {
    adjacency.get(a).push([b, cost]);
    adjacency.get(b).push([a, cost]);
  }

  function heapPush(heap, item) {
    heap.push(item);
    let i = heap.length - 1;
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (heap[parent][0] <= heap[i][0]) break;
      [heap[parent], heap[i]] = [heap[i], heap[parent]];
      i = parent;
    }
  }

  function heapPop(heap) {
    const top = heap[0];
    const last = heap.pop();
    if (heap.length > 0) {
      heap[0] = last;
      let i = 0;
      while (true) {
        const left = 2 * i + 1;
        const right = 2 * i + 2;
        let smallest = i;
        if (left < heap.length && heap[left][0] < heap[smallest][0]) smallest = left;
        if (right < heap.length && heap[right][0] < heap[smallest][0]) smallest = right;
        if (smallest === i) break;
        [heap[smallest], heap[i]] = [heap[i], heap[smallest]];
        i = smallest;
      }
    }
    return top;
  }

  const visited = new Set([0]);
  const frontier = [];
  for (const [neighbor, weight] of adjacency.get(0)) {
    heapPush(frontier, [weight, neighbor]);
  }

  let totalCost = 0;
  let housesToConnect = n;

  while (frontier.length > 0 && housesToConnect > 0) {
    const [weight, node] = heapPop(frontier);
    if (visited.has(node)) continue;
    visited.add(node);
    totalCost += weight;
    housesToConnect--;
    for (const [neighbor, edgeWeight] of adjacency.get(node)) {
      if (!visited.has(neighbor)) heapPush(frontier, [edgeWeight, neighbor]);
    }
  }

  return totalCost;
}
Time
O(E log V)
Space
O(V + E)
6. Test cases

Test cases

InputExpectedCovers
n = 3, wells = [1, 2, 2], pipes = [[1, 2, 1], [2, 3, 1]]3example from the docstring
n = 2, wells = [1, 1], pipes = [[1, 2, 1]]2one well plus one pipe beats two wells
n = 3, wells = [5, 4, 3], pipes = []12no pipes available, every house must dig its own well
n = 4, wells = [10, 10, 10, 10], pipes = [[1, 2, 0], [2, 3, 0], [3, 4, 0]]10one well plus a free pipe chain covers every remaining house
n = 1, wells = [7], pipes = []7smallest valid input, a single house with only a well option
n = 4, wells = [1, 100, 100, 100], pipes = [[1, 2, 2], [2, 3, 2], [3, 4, 2]]7one cheap well plus a pipe chain beats digging expensive wells everywhere
n = 3, wells = [2, 2, 2], pipes = [[1, 2, 1], [1, 3, 1], [2, 3, 1]]4redundant pipe in a cycle is never absorbed

Keep reading