DSA problem
Optimize Water Distribution in a Village
There are n houses in a village, labelled from 1 to n. You want to supply water to every house. For each house i, you can either build a well inside it with cost wells[i - 1], or pipe water from another house. The pipe options are given as pipes[j] = [house1, house2, cost] meaning a bidirectional pipe between house1 and house2 costs cost. Return the minimum total cost to supply water to all n houses.
The clever modelling trick is to introduce a virtual node 0 representing an "infinite water source". Every well at house i becomes an edge from node 0 to node i with weight wells[i - 1]. Combined with the original pipes, the problem becomes "find the minimum spanning tree of a graph on n + 1 nodes". Once you see this reformulation, the problem reduces to a standard MST.
After the reduction, Kruskal's algorithm fits perfectly: sort all edges (wells + pipes) by ascending cost, and greedily accept each edge that joins two different components via a Disjoint Set Union (DSU). The MST has exactly n edges because there are n + 1 nodes; every accepted edge either builds a well (connects a house to the virtual source) or lays a pipe between two houses.
The total work is dominated by the sort, giving O((n + p) log (n + p)) time where p = pipes.length, and the DSU contributes O(n) extra space. The result is the sum of accepted edge weights, which equals the minimum cost to water every house.
Examples
n = 3, wells = [1,2,2], pipes = [[1,2,1],[2,3,1]]3n = 2, wells = [1,1], pipes = [[1,2,1]]2n = 3, wells = [5,5,5], pipes = []15Constraints
- 2 <= n <= 10^4
- wells.length == n
- 0 <= wells[i] <= 10^5
- 1 <= pipes.length <= 10^4
- pipes[j].length == 3
- 1 <= house1, house2 <= n
- house1 != house2
- 0 <= cost <= 10^5
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.