Code Implementation

class Solution:
    def minCostToSupplyWater(self, n, wells, pipes):
        # Add a virtual node 0, connect it to every house with cost wells[i]
        edges = []
        for i, cost in enumerate(wells):
            edges.append((cost, 0, i+1))
        for u, v, w in pipes:
            edges.append((w, u, v))
        # Kruskal's algorithm
        edges.sort()
        parent = [i for i in range(n+1)]
        def find(x):
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x
        res = 0
        for w, u, v in edges:
            pu, pv = find(u), find(v)
            if pu != pv:
                parent[pu] = pv
                res += w
        return res
      

class Solution {
public:
    int minCostToSupplyWater(int n, vector<int>& wells, vector<vector<int>>& pipes) {
        vector<tuple<int,int,int>> edges;
        for (int i = 0; i < n; ++i)
            edges.emplace_back(wells[i], 0, i+1);
        for (auto& p : pipes)
            edges.emplace_back(p[2], p[0], p[1]);
        sort(edges.begin(), edges.end());
        vector<int> parent(n+1);
        iota(parent.begin(), parent.end(), 0);
        function<int(int)> find = [&](int x) {
            while (parent[x] != x) {
                parent[x] = parent[parent[x]];
                x = parent[x];
            }
            return x;
        };
        int res = 0;
        for (auto& [w, u, v] : edges) {
            int pu = find(u), pv = find(v);
            if (pu != pv) {
                parent[pu] = pv;
                res += w;
            }
        }
        return res;
    }
};
      

class Solution {
    public int minCostToSupplyWater(int n, int[] wells, int[][] pipes) {
        List<int[]> edges = new ArrayList<>();
        for (int i = 0; i < n; ++i)
            edges.add(new int[]{wells[i], 0, i+1});
        for (int[] p : pipes)
            edges.add(new int[]{p[2], p[0], p[1]});
        edges.sort((a, b) -> a[0] - b[0]);
        int[] parent = new int[n+1];
        for (int i = 0; i <= n; ++i) parent[i] = i;
        int res = 0;
        for (int[] e : edges) {
            int w = e[0], u = e[1], v = e[2];
            int pu = find(parent, u), pv = find(parent, v);
            if (pu != pv) {
                parent[pu] = pv;
                res += w;
            }
        }
        return res;
    }
    private int find(int[] parent, int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
}
      

var minCostToSupplyWater = function(n, wells, pipes) {
    let edges = [];
    for (let i = 0; i < n; ++i)
        edges.push([wells[i], 0, i+1]);
    for (let [u, v, w] of pipes)
        edges.push([w, u, v]);
    edges.sort((a, b) => a[0] - b[0]);
    let parent = Array(n+1).fill(0).map((_,i)=>i);
    function find(x) {
        while (parent[x] !== x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
    let res = 0;
    for (let [w, u, v] of edges) {
        let pu = find(u), pv = find(v);
        if (pu !== pv) {
            parent[pu] = pv;
            res += w;
        }
    }
    return res;
};
      

Problem Description

You are given n houses in a village, numbered from 1 to n. Each house needs access to water. There are two ways to supply water to a house:

• Build a well in the house at a cost given by wells[i] (for house i+1).
• Connect the house to another house using a pipe, described by pipes. Each pipe is represented as [house1, house2, cost] and can supply both houses if connected.

Your task is to supply water to every house with the minimum total cost. You may build wells, lay pipes, or use a combination of both. Each pipe can only be used once, and you cannot reuse wells. There is always at least one valid way to supply water to all houses.

Thought Process

At first glance, the problem seems to ask for choosing the cheapest way to supply water to each house: either build a well or connect via pipes. But since pipes can connect multiple houses and share water, simply picking the cheapest option for each house independently may not yield the minimum total cost.

A brute-force approach would try all possible combinations of wells and pipes, but this quickly becomes impractical as the number of houses and pipes grows. Instead, we recognize this as a variation of the Minimum Spanning Tree (MST) problem, where each house is a node, pipes are edges, and building a well is like connecting the house to a virtual water source node.

The key insight is to model building a well as an edge from a virtual node (say, node 0) to each house, with the cost being the well's price. Then, we find the MST of this augmented graph: the minimum cost to connect all houses (and the water source) together.

Solution Approach

• Step 1: Graph Augmentation
  Add a virtual node (node 0) to represent the water source. For each house i, add an edge from node 0 to node i+1 with cost wells[i]. All pipes are already edges between houses.
• Step 2: Minimum Spanning Tree (MST)
  The problem now reduces to finding the MST in this graph. The MST ensures all nodes (houses) are connected (directly or indirectly) to the water source at the lowest possible cost.
• Step 3: Kruskal's Algorithm
  Since the graph is sparse and edges are given explicitly, Kruskal's algorithm is efficient. It sorts all edges by cost and iteratively adds them to the MST, skipping any that would create a cycle (using Union-Find for cycle detection).
• Step 4: Implementation Details
  • Initialize a Union-Find (Disjoint Set) structure for all nodes (including node 0).
  • Sort all edges (pipes and well-edges) by cost.
  • Iterate through edges, adding them if they connect two different components (houses not already connected).
  • Sum the costs of the chosen edges; that's the answer.

Example Walkthrough

Suppose n = 3, wells = [1,2,2], and pipes = [[1,2,1],[2,3,1]].

• Step 1: Augment the graph
  • Edges from node 0: (0,1,1), (0,2,2), (0,3,2)
  • Pipes: (1,2,1), (2,3,1)
• Step 2: Sort edges by cost
  • (0,1,1), (1,2,1), (2,3,1), (0,2,2), (0,3,2)
• Step 3: Kruskal's Algorithm
  • Add (0,1,1): Connects water source to house 1. Total cost = 1.
  • Add (1,2,1): Connects house 1 and 2. Total cost = 2.
  • Add (2,3,1): Connects house 2 and 3. Total cost = 3.
  • Now all houses are connected (either directly or indirectly) to the water source. We stop here.
• Result: The minimum total cost is 3.

Time and Space Complexity

• Brute-force approach: Exponential time, as it would try all combinations of building wells and laying pipes. Not feasible for large n.
• Optimized (MST/Kruskal):
  • Sorting edges: O(E \log E), where E is the number of edges (pipes + wells).
  • Union-Find operations: nearly O(E) due to path compression.
  • Total: O(E \log E) time and O(n) space for parent array.

Summary

By modeling well-building as connecting houses to a virtual water source, the problem becomes a classic Minimum Spanning Tree scenario. Using Kruskal's algorithm efficiently finds the minimum cost to connect all houses to water, cleverly combining wells and pipes as needed. This approach is both elegant and optimal, leveraging well-known graph algorithms to solve a practical resource allocation problem.