Skip to main content
Talentd

Optimize Water Distribution in a Village - Solution & Explanation

HardPremiumFree on FleetCodeUnion FindGraphHeap (Priority Queue)Minimum Spanning Tree18 min readAsked at: Apple, Google
Practice this problem

Problem Statement

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 <= 104
  • wells.length == n
  • 0 <= wells[i] <= 105
  • 1 <= pipes.length <= 104
  • pipes[j].length == 3
  • 1 <= house1j, house2j <= n
  • 0 <= costj <= 105
  • house1j != house2j

Approach Overview

Problem 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.

Approach 1: Kruskal's Algorithm (Minimum Spanning Tree)

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.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Approach 2: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Kruskal's Algorithm (Minimum Spanning Tree)—
Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Kruskal's Algorithm with Union-FindO((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 HeapO((n + m) log n)O(n + m)Preferred when using adjacency lists or when expanding the MST incrementally

Video Solution

LeetCode 1168. Optimize Water Distribution in a Village • Happy Coding • 4,150 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Optimize Water Distribution in a Village easy or hard?
Optimize Water Distribution in a Village is categorized as a Hard problem because it requires recognizing the Minimum Spanning Tree transformation with a virtual node. Once modeled correctly, the implementation of Kruskal or Prim is standard, but the graph modeling step makes the problem challenging.
Optimize Water Distribution in a Village Python/Java solution
Most implementations use either Kruskal's algorithm with Union-Find or Prim's algorithm with a priority queue. Python solutions typically use heapq for the min heap, while Java implementations use PriorityQueue and a DSU class for Union-Find operations. Both achieve O((n + m) log n) time complexity.
How to solve Optimize Water Distribution in a Village in O(n log n)?
Use Prim's algorithm with a min heap. Represent wells as edges from a virtual node 0 to each house. Start from node 0, push edges into a priority queue, and repeatedly add the smallest cost edge connecting a new house. This builds a Minimum Spanning Tree with time complexity O((n + m) log n).
What is the best approach for Optimize Water Distribution in a Village?
The best approach models the problem as a Minimum Spanning Tree. Add a virtual node connected to every house with edge cost equal to the well cost, then run Kruskal's algorithm with Union-Find. This ensures the algorithm chooses the cheapest option between building a well or connecting via pipes. The overall time complexity is O((n + m) log(n + m)).
Is Optimize Water Distribution in a Village asked at Google/Amazon/Meta?
Minimum Spanning Tree problems similar to this one frequently appear in interviews at companies like Google, Amazon, and Meta. The question tests graph modeling, Union-Find, and MST algorithms such as Kruskal and Prim, which are common interview topics for backend and infrastructure roles.
What data structure is used in Optimize Water Distribution in a Village?
The main data structures are Union-Find (Disjoint Set Union) for Kruskal's algorithm and a Priority Queue (Min Heap) for Prim's algorithm. Both solutions operate on a graph representation of houses and pipes, and both rely on Minimum Spanning Tree techniques.
What is the time complexity of Optimize Water Distribution in a Village?
The optimal MST solutions run in O((n + m) log n) or O((n + m) log(n + m)) time depending on the algorithm used. Kruskal's algorithm requires sorting edges, while Prim's algorithm uses a priority queue to expand the tree. Both approaches use O(n + m) space for storing graph edges and structures.

Ready to solve this problem?

Practice Optimize Water Distribution in a Village with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Consecutive Sequence

Next

Surrounded Regions