The Question
Coding

Optimize Water Distribution System

There are n houses in a neighborhood. You want to provide water to every house at the minimum possible cost. For each house i, you have two options: 1. Build a well directly at the house with cost wells[i-1]. 2. Lay a pipe connecting house i to another house j with a specific cost given in an array pipes, where pipes[k] = [house1, house2, cost]. Connections are bidirectional. Multiple pipes can exist between the same pair of houses. Find the minimum total cost to ensure every house has access to water (either via its own well or via a connection to a house that has access to water).
Java
Kruskal's Algorithm
Union-Find
MST
Greedy
Questions & Insights

Clarifying Questions

What is the range of $n$ (number of houses)? (Typically n \le 10,000, which influences whether we use Kruskal's O(E \log E) or Prim's O(E \log V)).
Can there be multiple pipes between the same two houses? (The problem states yes; an MST algorithm like Kruskal's naturally handles this by picking the cheapest edge first).
Is the graph guaranteed to be connected? (With the option to build a well at every house, a solution is always possible. By using a virtual node, we ensure the graph is connected).
What are the constraints on the costs? (Assuming costs are non-negative integers).

Assumptions

n is up to 10^4, and the number of pipe connections is also up to 10^4.
We use a 0-indexed or 1-indexed approach carefully (houses are 1 to n, wells is 0-indexed).
The "virtual node" technique will be used to transform the well-building into an edge-selection problem.

Thinking Process

Virtual Node Transformation: The problem asks to either build a well or connect to an existing supply. We can simplify this by introducing a "Virtual Water Source" (Node 0). Building a well at house is mathematically equivalent to laying a pipe between Node 0 and House with a cost equal to the well's construction cost.
MST Formulation: Once all well costs are converted into edges connected to Node 0, the problem becomes finding the Minimum Spanning Tree (MST) that connects all nodes \{0, 1, \dots, n\}.
Algorithm Selection: Kruskal's Algorithm is ideal here. We aggregate all pipe edges and the new "virtual" well edges into a single list, sort them by cost, and use a Union-Find data structure to build the MST.
Greedy Strategy: By sorting edges and picking the smallest ones that don't form a cycle, we ensure that for every house, we either build a well or connect to a house that eventually leads to a well at the minimum possible cost.
Implementation Breakdown

Problem Set

Functional Requirements: Calculate the minimum cost to ensure every house has water.
Constraints:
1 \le n \le 10,000
1 \le wells[i] \le 10^5
1 \le pipes[j][2] \le 10^5
1 \le pipes.length \le 10,000

Approach

Algorithm: Kruskal's Algorithm
Data Structure: Union-Find (Disjoint Set Union) with Path Compression and Union by Rank.
Complexity:
Time: O(E \log E), where E is the total number of edges (pipes + wells). Sorting dominates.
Space: O(V + E) to store the edges and the Union-Find structure.

Implementation

Wrap Up

Advanced Topics

Prim's vs. Kruskal's: Kruskal's is generally better for sparse graphs (E \approx V), while Prim's with a Fibonacci Heap can be faster for dense graphs (E \approx V^2). Since we add N virtual edges to existing pipes, the density depends on the pipes array.
Scalability: If the number of houses N becomes extremely large (e.g., 10^9) but the number of pipes is small, we cannot use a standard Union-Find array. We would need a Map-based Union-Find or a coordinate compression approach, though this usually isn't the case for MST problems.
Parallelization: Kruskal's sorting step can be parallelized. For Union-Find, concurrent DSU implementations exist using atomic operations to handle graph components in parallel during the edge processing stage.