Skip to content
RED SAGSkills
hard60 ptsunion-findgraphgreedy

Water Supply for Every House

A village has n houses numbered 1 to n. Every house needs water. House i can either drill its own well for wells[i - 1], or be connected by pipes to a house that has water. Each entry [a, b, cost] of pipes is a possible two-way pipe; there may be several options between the same two houses.

Return the minimum total cost to supply every house with water. A neat trick: treat the water source as an extra node 0, with a pipe of cost wells[i - 1] to each house, then find a minimum spanning tree.

Example 1

Input: n = 4, wells = [5,4,3,6], pipes = [[1,2,2],[2,3,2],[3,4,8],[1,4,1]]
Output: 8
Explanation: Pipes 1-4 (1), 1-2 (2) and 2-3 (2) plus a well at house 3 (3).

Example 2

Input: n = 2, wells = [1,1], pipes = [[1,2,5]]
Output: 2
Explanation: Both houses drill wells.

Constraints

  • 1 <= n <= 5000
  • wells.length == n
  • 0 <= pipes.length <= 2 * 10^4
  • 1 <= wells[i], cost <= 10^5
  • 1 <= a, b <= n, a != b
Hint 1

Add a virtual node 0 (the water source) joined to house i by an edge of cost wells[i - 1].

Hint 2

Now every house must connect to node 0: run Kruskal's algorithm with union-find on all edges.

Discussion 0

Join free to post in the discussion.

Good practice for: Backend Developer, Cloud Engineer, DevOps Engineer, Data Engineer, Site Reliability Engineer

Run checks your code on 3 sample tests. Submit runs all 8 tests, including hidden ones, and earns points. Use console.log to debug. Python's first run can take a few seconds while it starts.