Search⌘ K
AI Features
Home
Courses
Algorithms for Coding Interviews in Python

Solution: Connecting n Pipes With Minimum Cost

This review provides a detailed analysis of how to connect n pipes with the minimum cost.

We'll cover the following...

Solution: sorting

Python 3.5
import heapq
def min_cost(pipes):
    """
    Calculates the minimum cost of connecting pipes
    :param pipes: A list where its length is the number of pipes and indexes are the specific lengths of the pipes.
    :return: The minimum cost
    """
    
    # Create a priority queue out of the
    # given list
    heapq.heapify(pipes)
     
    # Initializ result
    cost = 0
     
    # While size of priority queue
    # is more than 1
    while(len(pipes) > 1):
         
        # Extract shortest two pipes from the priority queue
        first = heapq.heappop(pipes)
        second = heapq.heappop(pipes)
         
        # Connect the pipe: update cost
        # and insert the new pipe to pipes queue
        cost += first + second
        heapq.heappush(pipes, first + second)
         
    return cost
# Main program to test above function
if __name__ == "__main__":
    pipes = [4, 3, 2, 6]
    print(min_cost(pipes))

Explanation

If you look at the animation present in the previous lesson, you will notice that the lengths of the pipes which are picked first are included iteratively (i.e. each time). Therefore, we want them to be as small as possible. Now, let’s be greedy!

First, we initialize the priority queue with the pipes. The priority queue ensures that the two smallest length pipes are selected in every iteration. In this way, in every iteration, the previous cost (which is the length of the last two pipes connected) is added to the cost of connected pipes in this iteration until all pipes are connected.

Time complexity

The time complexity for this solution is O(nlogn)O(nlogn) because both the push and pop operations of the priority queue take O(logn) time.