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.
We assume that there is a well with the number 0. Then we can consider the connectivity between each house and the well 0 as an edge, and the weight of each edge is the cost of building a well for that house. At the same time, we consider the connectivity between each house as an edge, and the weight of each edge is the cost of laying a pipe. In this way, we can transform this problem into finding the minimum spanning tree of an undirected graph.
We can use Kruskal's algorithm to find the minimum spanning tree of the undirected graph. First, we add an edge between the well 0 and the house to the pipes array, and then sort the pipes array in ascending order of edge weights. Then, we traverse each edge. If this edge connects different connected components, we choose this edge and merge the corresponding connected components. If the current connected component is exactly 1, then we have found the minimum spanning tree. The answer at this time is the current edge weight, and we return it.
The time complexity is O((m + n) times log (m + n)), and the space complexity is O(m + n). Here, m and n are the lengths of the pipes array and the wells array, respectively.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Kruskal's Algorithm (Minimum Spanning Tree) | — |
| Default Approach | — |
| 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 |
LeetCode 1168. Optimize Water Distribution in a Village • Happy Coding • 4,054 views views
Watch 9 more video solutions →Practice Optimize Water Distribution in a Village with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor