HardNo. 1168LeetCode Premium
Optimize Water Distribution in a Village — LeetCode 1168 Python Solution
- Pattern
- Union-Find
- Topics
- Union Find, Graph, Minimum Spanning Tree, Heap (Priority Queue)
- Reading time
- 4 min
- Source
- leetcode.com
The problem
There are n houses in a village. We want to supply water for all the houses by building wells and laying pipes.
Example
- 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.
Python solution
class Solution:
def minCostToSupplyWater(
self, n: int, wells: List[int], pipes: List[List[int]]
) -> int:
def find(x: int) -> int:
if p[x] != x:
p[x] = find(p[x])
return p[x]
for i, w in enumerate(wells, 1):
pipes.append([0, i, w])
pipes.sort(key=lambda x: x[2])
p = list(range(n + 1))
ans = 0
for a, b, c in pipes:
pa, pb = find(a), find(b)
if pa != pb:
p[pa] = pb
n -= 1
ans += c
if n == 0:
return ansComplexity
- Time
- O((m + n) × log (m + n))
- Space · auxiliary
- O(m + n)
Pattern: Union-Find
Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 1168. Optimize Water Distribution in a Village is filed here because LeetCode tags it Union Find, which is the vocabulary this hub collects.
The union-find guide has the Python template for the pattern and the 83 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0743 | Network Delay Time | Medium |
| 0882 | Reachable Nodes In Subdivided Graph | Hard |
| 1368 | Minimum Cost to Make at Least One Valid Path in a Grid | Hard |
| 1514 | Path with Maximum Probability | Medium |
| 2290 | Minimum Obstacle Removal to Reach Corner | Hard |
| 2577 | Minimum Time to Visit a Cell In a Grid | Hard |
Frequently asked questions
- How hard is LeetCode 1168. Optimize Water Distribution in a Village?
LeetCode 1168. Optimize Water Distribution in a Village is rated Hard on LeetCode.
- What is the time complexity of LeetCode 1168. Optimize Water Distribution in a Village?
The Python solution on this page runs in O((m + n) × log (m + n)).
- What is the space complexity of LeetCode 1168. Optimize Water Distribution in a Village?
The Python solution on this page uses O(m + n) auxiliary space.
- What topics does LeetCode 1168. Optimize Water Distribution in a Village cover?
LeetCode 1168. Optimize Water Distribution in a Village is tagged Union Find, Graph, Minimum Spanning Tree and Heap (Priority Queue) on LeetCode.
- Is LeetCode 1168. Optimize Water Distribution in a Village a premium problem?
Yes. LeetCode 1168. Optimize Water Distribution in a Village is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.