Optimize Water Distribution in a Village
Understanding the Problem
At first, this doesn't look like a standard graph problem. We have two types of costs: building a well in a house, or laying a pipe between two houses. The challenge is deciding which houses get their own wells and which houses receive water through pipes from other houses.
A virtual node makes both costs comparable. Introduce a node 0 that represents the water source. Building a well in house i becomes an edge from house i to node 0 with cost wells[i - 1], and a pipe between two houses is already an edge. Every cost is now an edge in one graph, and the goal becomes connecting all houses to the water source for the least total cost. That is a Minimum Spanning Tree (MST) problem on n + 1 nodes.
Key Constraints:
2 <= n <= 10^4andpipes.length <= 10^4-> Addingnwell-edges to the pipe-edges gives at most about 20,000 edges. An O(E log E) algorithm sorts that in well under a millisecond, so MST is fast enough.0 <= wells[i], cost_j <= 10^5-> Costs can be zero. A well with cost 0 means free water for that house. An MST uses exactlynedges, so the total cost is at mostn * 10^5 = 10^4 * 10^5 = 10^9, which fits in a signed 32-bit integer (max about2.1 * 10^9). A plainintaccumulator is safe here.
Approach 1: Kruskal's Algorithm with Union-Find
Intuition
With the virtual node in place, connecting all n houses to the water source at minimum cost is a Minimum Spanning Tree over n + 1 nodes (node 0 plus the houses). Kruskal's algorithm builds that tree directly: sort all edges by cost, then scan from cheapest to most expensive, adding each edge whose two endpoints are not already connected.
The "not already connected" check is what Union-Find (Disjoint Set Union) handles. Each node starts in its own component. Adding an edge merges the two components it joins, and an edge is skipped when both endpoints are in the same component (adding it would form a cycle and waste cost). With path compression and union by rank, both the lookup and the merge run in near-constant amortized time.
A house gets water when it is connected (directly or through pipes) to node 0, the source. So every house must share a component with node 0, and the cheapest structure that connects all n + 1 nodes with no redundant edges is an MST. Kruskal's correctness rests on the cut property: for any way of splitting the nodes into two groups, the cheapest edge crossing that split belongs to some MST. Scanning edges in cost order, the first edge that joins two separate components is always the cheapest edge crossing the cut between them, so adding it is safe. Equal-cost edges break no ties wrongly, since any of them is a valid minimum-crossing edge.
Algorithm
- Create a list of all edges. For each house
i(1 to n), add an edge(0, i, wells[i-1])representing the cost to build a well. - Add all pipe edges
(house1, house2, cost)to the same list. - Sort all edges by cost in ascending order.
- Initialize a Union-Find structure with n + 1 nodes (0 through n).
- Iterate through sorted edges. For each edge, if the two endpoints are in different components, union them and add the edge cost to the total.
- Stop when we've added n edges (an MST over n + 1 nodes has exactly n edges).
- Return the total cost.
Visualization and Code
Loading animation...
- Time Complexity: O(E log E), where E = n + len(pipes). Building the edge list is O(E). Sorting is O(E log E). Iterating through edges with Union-Find operations is O(E * alpha(n)), where alpha is the inverse Ackermann function (practically constant). Sorting dominates.
- Space Complexity: O(E + n). O(E) for the edge list and O(n) for the Union-Find arrays.
Kruskal's sorts every edge upfront, even when the MST is complete after the first few. The next approach avoids the global sort by growing the tree from the source and pulling edges out of a min-heap one at a time.
Approach 2: Prim's Algorithm with Priority Queue
Intuition
Prim's algorithm builds the MST a different way. Instead of sorting all edges globally, it grows the tree from a starting node, repeatedly picking the cheapest edge that connects a node already in the tree to a node still outside it. A min-heap keeps track of the candidate edges so the cheapest one is always available at the top.
The same virtual node applies. We start the tree at node 0 (the water source) and grow it outward. Each time a new house joins the tree, we push its edges to unvisited neighbors into the heap. Because the heap orders by cost, every edge we pop is the cheapest one currently crossing from the tree to the outside, which is the edge Prim's needs.
The difference from Kruskal's is that edges enter and leave the heap lazily, so there is no upfront sort of the whole edge list. For the edge counts here, both run in O(E log E) and perform similarly.
Algorithm
- Build an adjacency list. For each house
i, add an edge(0, i, wells[i-1]). For each pipe, add edges in both directions. - Initialize a min-heap with all edges from node 0 (the well costs).
- Mark node 0 as visited. Initialize
totalCost = 0andconnected = 0. - While
connected < n: - Pop the cheapest edge
(cost, node)from the heap. - If
nodeis already visited, skip it (a cheaper edge already reached it). - Otherwise, mark it visited, add
costtototalCost, incrementconnected. - Add all edges from
nodeto unvisited neighbors into the heap. - Return
totalCost.
Visualization and Code
Loading animation...
- Time Complexity: O(E log E), where E = n + len(pipes). Each edge is pushed into and popped from the heap at most once. Each heap operation is O(log E). So the total is O(E log E).
- Space Complexity: O(E + n). O(E) for the adjacency list and O(E) for the heap in the worst case. O(n) for the visited array.