Optimize Water Distribution in a Village — LeetCode 1168 Python Solution
HardLeetCode PremiumUnion FindGraphMinimum Spanning TreeHeap (Priority Queue)
- Problem
- #1168
- Pattern
- Union-Find
- 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
Python
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
| Measure | Complexity |
|---|---|
| Time | O((m + n) \times \log (m + n)) |
| Space | O(m + n) auxiliary |
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
LeetCode 743Network Delay TimeMediumLeetCode 882Reachable Nodes In Subdivided GraphHardLeetCode 1368Minimum Cost to Make at Least One Valid Path in a GridHardLeetCode 1514Path with Maximum ProbabilityMediumLeetCode 2290Minimum Obstacle Removal to Reach CornerHardLeetCode 2577Minimum Time to Visit a Cell In a GridHard
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) \times \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.