Watch 10 video solutions for Optimize Water Distribution in a Village, a hard level problem involving Union Find, Graph, Heap (Priority Queue). This walkthrough by Happy Coding has 4,054 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
There are n houses in a village. We want to supply water for all the houses by building wells and laying pipes.
For each house i, we can either build a well inside it directly with cost wells[i - 1] (note the -1 due to 0-indexing), or pipe in water from another well to it. The costs to lay pipes between houses are given by the array pipes where each pipes[j] = [house1j, house2j, costj] represents the cost to connect house1j and house2j together using a pipe. Connections are bidirectional, and there could be multiple valid connections between the same two houses with different costs.
Return the minimum total cost to supply water to all houses.
Example 1:
Input: n = 3, wells = [1,2,2], pipes = [[1,2,1],[2,3,1]] Output: 3 Explanation: The image shows the costs of connecting houses using pipes. The best strategy is to build a well in the first house with cost 1 and connect the other houses to it with cost 2 so the total cost is 3.
Example 2:
Input: n = 2, wells = [1,1], pipes = [[1,2,1],[1,2,2]] Output: 2 Explanation: We can supply water with cost two using one of the three options: Option 1: - Build a well inside house 1 with cost 1. - Build a well inside house 2 with cost 1. The total cost will be 2. Option 2: - Build a well inside house 1 with cost 1. - Connect house 2 with house 1 with cost 1. The total cost will be 2. Option 3: - Build a well inside house 2 with cost 1. - Connect house 1 with house 2 with cost 1. The total cost will be 2. Note that we can connect houses 1 and 2 with cost 1 or with cost 2 but we will always choose the cheapest option.
Constraints:
2 <= n <= 104wells.length == n0 <= wells[i] <= 1051 <= pipes.length <= 104pipes[j].length == 31 <= house1j, house2j <= n0 <= costj <= 105house1j != house2jProblem Overview: You need to supply water to n houses. Each house can either build its own well with a fixed cost or connect to another house using pipes with installation costs. The goal is to supply water to every house while minimizing the total cost.
This is a classic network optimization problem. Each house is a node and each pipe is an edge with cost. The trick is modeling the option of building a well. Instead of treating wells separately, you add a virtual node (node 0) connected to every house with an edge equal to the well cost. Once modeled this way, the problem becomes finding a Minimum Spanning Tree across all nodes.
Approach 1: Kruskal's Algorithm with Union-Find (Minimum Spanning Tree) (Time: O((n + m) log(n + m)), Space: O(n + m))
Create a virtual node 0 and connect it to each house i with an edge cost equal to wells[i]. Combine these edges with the given pipe edges. Now the graph has n + 1 nodes and n + m edges. Sort all edges by cost and run Kruskal's algorithm.
Use a Union Find (Disjoint Set Union) structure to track connected components. Iterate through the sorted edges, union the endpoints if they are not already connected, and add the edge cost to the total. Once all houses belong to the same component, the MST is complete. The key insight: building a well becomes just another edge choice competing with pipe connections.
Approach 2: Prim's Algorithm with Min Heap (Default Approach) (Time: O((n + m) log n), Space: O(n + m))
This approach builds the MST incrementally using a Priority Queue. Construct an adjacency list for the graph including edges from the virtual node to each house. Start Prim's algorithm from node 0.
Push all edges from the starting node into a min heap ordered by cost. Repeatedly pop the cheapest edge that connects a new house to the growing tree. Mark houses as visited and add their outgoing edges to the heap. Continue until all houses are connected. The heap ensures the algorithm always expands the cheapest possible connection.
Recommended for interviews: Both solutions are valid since the problem is fundamentally a graph Minimum Spanning Tree problem. Kruskal's algorithm with Union-Find is often preferred because the modeling trick (adding a virtual node for wells) clearly converts the problem into a standard MST. Interviewers like this approach because it demonstrates graph modeling skills and familiarity with MST patterns. Prim's algorithm is equally efficient and sometimes simpler if you already have an adjacency list structure.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Kruskal's Algorithm with Union-Find | O((n + m) log(n + m)) | O(n + m) | Best when edges are easy to list and sort; very common MST interview solution |
| Prim's Algorithm with Min Heap | O((n + m) log n) | O(n + m) | Preferred when using adjacency lists or when expanding the MST incrementally |