Optimize Water Distribution
Hard · Advanced Graphs · Union Find · Graph · Heap (Priority Queue) · Minimum Spanning Tree
Problem
A village has n houses numbered 1 to n. Every house needs water, which it can get in one of two ways:
- Build a well inside house i at cost wells[i - 1].
- Receive water through pipes from another house that has water. pipes[j] = [house1_j, house2_j, cost_j] means a two-way pipe between those houses can be laid for cost_j. There may be several pipe options between the same pair of houses, with different costs.
Return the minimum total cost to supply water to every house.
Examples
Input: n = 3, wells = [2,5,4], pipes = [[1,2,1],[2,3,3]] Output: 6
Build a well at house 1 (2) and lay both pipes (1 + 3), for 6.
Input: n = 2, wells = [1,1], pipes = [[1,2,5]] Output: 2
Two wells cost 2, cheaper than any pipe.
Input: n = 2, wells = [4,9], pipes = [[1,2,7],[1,2,2]] Output: 6
A well at house 1 plus the cheaper of the two parallel pipes costs 6.
Constraints
- 2 <= n <= 10^4
- len(wells) == n
- 0 <= wells[i] <= 10^5
- 1 <= len(pipes) <= 10^4
- len(pipes[j]) == 3
- 1 <= house1_j, house2_j <= n, house1_j != house2_j
- 0 <= cost_j <= 10^5
Approaches
- Virtual source + Prim on a matrix — time O(n^2 + m), space O(n^2)
Follow-up
The virtual source is the whole trick: it turns a choice between two kinds of cost into a single spanning tree. The use cases add houses that already have water (free edges from the source) and give every pair of houses a price, where Prim's O(n^2) beats sorting all the pairs.
Related problems
Start free on Cariara · Coding problems · System design studio
