Problem Link: https://leetcode.com/problems/optimize-water-distribution-in-a-village/

Problem Statement Explanation:

Imagine that we have 'n' number of houses in a village that need to be supplied with water, but to supply the water from one house to another we have two options:
1. We build a pipe connection from one house ( which already has a water connection ) to another
2. We built a well inside that house to fetch water.

Now, we need to go about the cost-efficient way. ie, given a house, we simply need to check if building a well there would be cheaper or constructing a pipe with the nearby house to that house.

Assuming that we have the cost to build a well at any given house and the cost of pipe connection from one house to another. How would we solve this problem?

Solution Explanation:

For us to start with water connection, we need to make sure that our first house has a well ( because there should be a source of water and that if we only connect all the houses just because connecting them is cheaper than digging a well, we would have a bunch of houses with pipe connection but no water in it ), so the bottom line is: WE NEED AT LEAST ONE WELL

So, if we are given a list of costs which has the cost of digging a well for each house then one little optimization that we can do here is that we can start off with digging a well in a house that costs the least among all the other houses.

so whatever our further calculation is going to be, we have to add the above digging cost to our totalCost

Now that we have a well, for our next step we take the following steps:
1. Connect the house with the cheapest pipe cost
2. For this house, we check if the pipecost is cheaper or building a well is cheaper and go about with the cheapest option.
Repeating the same for all the houses would give us the optmialCost, don't you think?
However, what we could do at every house is that have a check if the cost of having a well at that house is cheaper than the connection that we are going to have. Remember our problem is to provide water supply to every house and not just to connect them with pipes.

Turning Solution to Code:

Now that you can solve this problem given a pen and paper and let's say for 10 houses, wouldn't it be great to solve this problem for 10000000 houses as well? In that case, you'd technically be solving a water supply problem for the Indian villages at scale.

wells = [] #The array of costs of building well for each house (i+1)

pipes = [ (house1, house2, cost) ] #The cost of constructing a pipe from house1 to house2

To start off with the solution, we need to first create a well.
But instead of deliberately creating a well and starting from the cheapest, let's create a dummy house ( house 0 ) and an edge from that house to itself with the cost.

        for i in range(n):
            pipes.append((0, i+1, wells[i]))

        for pipe in pipes:
            house1, house2, cost = pipe
            graph[house1].append((cost, house2))
            graph[house2].append((cost, house1))

Well, if you ask, the above thing might not make sense as of now, and is not really needed absolutely to solve this problem, in fact I would encourage you to go ahead and try to solve the problem using your own approach.

Now that we have all the pipes, we'll basically have to create a heap ( if this term overwhelms you, then think of it as a list that's always sorted, irrespective of how many times you insert ). We just follow a simple DFS now. What I mean by that is, that we start with a house ( 0 ) and then we add all the possible pipes ( edges ) for that house in our heap. The key sorting factor for the heap would be our "piping cost". And yeah, for each house we find the cheapest possible way to bring water in that house

            cost, house = heapq.heappop(heap)
            if house not in visited:
                visited.add(house)
                if wells[house-1] > cost:
                    totalCost+=cost
                else:
                    totalCost+= wells[house-1]

                children = graph[house]
                for child in children:
                    cost, house = child
                    if house not in visited:
                        heapq.heappush(heap, (cost, house))

we continue the above operation until we have visited all the nodes.

Here's the entire code:

class Solution:
    def minCostToSupplyWater(self, n: int, wells: List[int], pipes: List[List[int]]) -> int:
        graph = collections.defaultdict(list)
        totalCost = 0
        heap = []
        visited = set()
        minCost = float('inf')
        minHouse = -1

        for i in range(n):
            pipes.append((0, i+1, wells[i]))

        for pipe in pipes:
            house1, house2, cost = pipe
            graph[house1].append((cost, house2))
            graph[house2].append((cost, house1))

        heap.append((0,0))
        while len(visited) < n+1 and len(heap)>0:
            cost, house = heapq.heappop(heap)
            if house not in visited:
                visited.add(house)
                if wells[house-1] > cost:
                    totalCost+=cost
                else:
                    totalCost+= wells[house-1]

                children = graph[house]
                for child in children:
                    cost, house = child
                    if house not in visited:
                        heapq.heappush(heap, (cost, house))
        if len(visited)<n:
            for i in range(1,n+1):
                if i not in visited:
                    totalCost+= wells[i-1]        
        return totalCost

If you were able to understand the solution then Congratulations, you just solved a Leetcode HARD!