Optimize Water Distribution in a Village

Problem Description

Imagine you live in a village where the only source of water is a well, and you have to figure out how to get that water to your house without breaking the bank. Sounds like a fun day, right? Well, welcome to the “Optimize Water Distribution in a Village” problem on LeetCode!

In this delightful scenario, you have n houses and a number of wells, each with a different cost to dig. You also have pipes that can connect the houses, but they come with their own costs. Your mission, should you choose to accept it, is to minimize the total cost of supplying water to all the houses.

Code Solution


class Solution:
    def minCostToSupplyWater(
        self,
        n: int,
        wells: list[int],
        pipes: list[list[int]],
    ) -> int:
        ans = 0
        graph = [[] for _ in range(n + 1)]
        minHeap = []  # (d, u)

        for u, v, w in pipes:
            graph[u].append((v, w))
            graph[v].append((u, w))

        # Connect virtual 0 with nodes 1 to n.
        for i, well in enumerate(wells):
            graph[0].append((i + 1, well))
            heapq.heappush(minHeap, (well, i + 1))

        mst = {0}

        while len(mst) < n + 1:
            d, u = heapq.heappop(minHeap)
            if u in mst:
                continue
            # Add the new vertex.
            mst.add(u)
            ans += d
            # Expand if possible.
            for v, w in graph[u]:
                if v not in mst:
                    heapq.heappush(minHeap, (w, v))

        return ans

Approach Explanation

The solution employs a graph-based approach using a Minimum Spanning Tree (MST) algorithm, specifically Prim's algorithm. Here’s a brief rundown of what’s happening:

Graph Representation: The problem is modeled as a graph where nodes represent houses and the well, and edges represent the pipes and their costs.
Heap for Minimum Cost: A min-heap is used to always expand the least costly option first, ensuring that we are always adding the cheapest connection to our MST.
MST Construction: Starting from a virtual node (the well), we keep adding the cheapest edges until all houses are connected.

Time and Space Complexity

Time Complexity: O((n + m) log n), where n is the number of houses and m is the number of pipes. This is due to the heap operations and the graph traversal.

Space Complexity: O(n + m) for storing the graph and the heap.

Real-World Example

Think of a small village where every household is trying to get water from a single well. Each household has a different budget for digging a well, and there are various options for connecting pipes. The goal is to ensure that every household has access to water without spending a fortune. This problem mirrors the real-life challenge of optimizing resources in a community, ensuring that everyone has access to essential services without breaking the bank.