Problem 27.3 · Minimum Spanning TreesHard

Optimize Water Distribution in a Village

What it teaches: A virtual node turns "build a well here" options into ordinary edges, so the whole problem becomes one MST.

Practise it on judges as “Optimize Water Distribution in a Village”.

The problem

Houses 1..n each need water. Building a well in house i costs wells[i − 1]; laying pipe [a, b, cost] lets water flow between two houses. Return the minimum total cost to supply every house.

Example 1

Input: n = 3, wells = [1,2,2], pipes = [[1,2,1],[2,3,1]]
Output: 3

Well in house 1 (1), pipes 1-2 (1) and 2-3 (1).

Constraints

1 ≤ n ≤ 10⁴

Pattern clues in the wording

→ Each node can either connect to the network or pay its own cost

These clues point to Minimum Spanning Tree: Connect all nodes with the cheapest total edges: sort edges and add each one that doesn't form a cycle (Kruskal).

Stuck? Take one hint at a time

Solution.java · starter

import java.util.*;

class Solution {
    public int minCostToSupplyWater(int n, int[] wells, int[][] pipes) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	n = 3 wells = [1,2,2] pipes = [[1,2,1],[2,3,1]]	3
2	n = 2 wells = [1,1] pipes = [[1,2,1],[1,2,2]]	2

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Virtual node + Kruskal · O((n + p) log(n + p))

Virtual node + Kruskal

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

Edges = pipes plus (0, i, wells[i − 1]). Kruskal over n + 1 nodes.

Approach 1

import java.util.*;

class Solution {
    private int[] parent;

    public int minCostToSupplyWater(int n, int[] wells, int[][] pipes) {
        List<int[]> edges = new ArrayList<>();
        for (int i = 1; i <= n; i++) edges.add(new int[]{0, i, wells[i - 1]});
        for (int[] p : pipes) edges.add(p);
        edges.sort(Comparator.comparingInt(e -> e[2]));
        parent = new int[n + 1];
        for (int i = 0; i <= n; i++) parent[i] = i;
        int total = 0;
        for (int[] e : edges) {
            int a = find(e[0]), b = find(e[1]);
            if (a == b) continue;
            parent[a] = b;
            total += e[2];
        }
        return total;
    }

    private int find(int x) {
        while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
        return x;
    }
}

Verdict: The virtual node is the whole trick.

Before you submit

Edge cases and common mistakes

Test these inputs

No pipes (sum of wells)
Cheap wells everywhere

Mistakes people make

Choosing the single cheapest well and then running MST (sometimes several wells are cheaper).

Interview

Follow-up questions

Where else does a virtual node help?

Command Palette

The problem

Approaches

Virtual node + Kruskal

Edge cases and common mistakes

Follow-up questions