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

Solution: Connecting n Pipes with Minimum Cost

Explore methods to connect pipes with minimal cost using various greedy algorithm strategies. Understand brute force, sorting, min heap, and priority queue approaches, and analyze their time complexities to solve this optimization problem efficiently using C++.

We'll cover the following...

Solution #1: Brute Force

C++
int minCost(int pipes[], int n) {
  int cost;
  bool isFirstRun = true;
  int tempCost = 0;
  int tempPipes[n];
  std::sort(pipes, pipes + n); // built in function of a C++ library
  // find value for all combinations
  do {
    for (int pipeIndex = 0; pipeIndex < n; pipeIndex++) {
      tempPipes[pipeIndex] = pipes[pipeIndex];
    }
    for (int i = 0; i < n - 1; i++) {
      tempCost += (tempPipes[i] + tempPipes[i + 1]); //find current cost
      tempPipes[i + 1] = tempPipes[i] + tempPipes[i + 1];
    }
    if (isFirstRun) { //for first run add as it is in cost
      cost = tempCost;
      isFirstRun = false;
    } else if (tempCost < cost) //for later runs perform comparison
    {
      cost = tempCost;
    }
    tempCost = 0;
  } while (std::next_permutation(pipes, pipes + n)); // produces all combinations
  return cost;
}
int main() {
  int pipes[] = {4, 3, 2, 6 };
  int size = sizeof(pipes) / sizeof(pipes[0]);
  cout << "Total cost for connecting pipes list 1 is " << minCost(pipes, size);
  cout << endl << endl;
  int pipes1[] = {1, 1, 2, 6};
  int size1 = sizeof(pipes1) / sizeof(pipes1[0]);
  cout << "Total cost for connecting pipes list 2 is " << minCost(pipes1, size1);
  return 0;
}

In the brute force method, we try all combinations of pipes possible (line34) in order to find the minimum possible cost.

Time Complexity

The time Complexity is O(2n)O(2^n) because we find all possible combinations and out of that choose the one where we can find the minimum cost.

Solution #2: Sorting

C++
int minCost(int pipes[], int n) {
  int cost;
  std::sort(pipes, pipes + n); // to generate all combinations.
   
    for (int i = 0; i < n - 1 ; i++) {
      int prevCost = cost; //store previous cost for later use
      
      cost = (pipes[i] + pipes[i+1]); //find current cost
      pipes[i + 1] = cost; //insert in array
      
      cost = cost + prevCost; //add with previous cost
    }
  
  return cost;
}
int main() {
  int pipes[] = {4, 3, 2, 6 };
  int size = sizeof(pipes) / sizeof(pipes[0]);
  cout << "Total cost for connecting pipes list 1 is " << minCost(pipes, size);
  cout << endl << endl;
  int pipes1[] = {1, 1, 2, 6};
  int size1 = sizeof(pipes1) / sizeof(pipes1[0]);
  cout << "Total cost for connecting pipes list 2 is " << minCost(pipes1, size1);
  return 0;
}

We optimize the solution by sorting the array and choosing the minimum pipes first.

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!! Grab and connect the smallest two pipes first and recur for remaining pipes.

We always try and put the smallest pipes down the tree so that they can be repeated multiple times, otherwise the longer pipes will be added multiple times.

Time Complexity:

The time complexity for this solution is O(nlogn)O(nlogn), because of the optimized built-in C++ sort function.

Solution #3: Using MinHeap

C++
#include "minHeap.cpp"
int minCost(int pipes[], int n) {
  int cost = 0;
  struct MinHeap * minHeap = createAndBuildMinHeap(pipes, n);
  while (!isSizeOne(minHeap)) {
    int min = extractMin(minHeap);
    int secondMin = extractMin(minHeap);
    cost += (min + secondMin);
    insertMinHeap(minHeap, min + secondMin);
  }
  return cost;
}
int main() {
  int pipes[] = {4, 3, 2, 6 };
  int size = sizeof(pipes) / sizeof(pipes[0]);
  cout << "Total cost for connecting pipes list 1 is " << minCost(pipes, size);
  cout << endl << endl;
  int pipes1[] = {1, 1, 2, 6};
  int size1 = sizeof(pipes1) / sizeof(pipes1[0]);
  cout << "Total cost for connecting pipes list 2 is " << minCost(pipes1, size1);
  return 0;
}

Pseudocode

minCost(pipes, n)
     Let there be n pipes of lengths stored in an array
     create a minHeap 
     insert lengths into the min heap.
     while ( number of elements in min heap != 1)
        Extract the minimum and second minimum from min heap
        Add the two extracted values 
        Insert to the min-heap.
        Maintain variable for total cost 
Return the value of the total cost.

Time Complexity

The time complexity of the algorithm is O(nlogn)O(nlogn) only if we use a O(nlogn)O(nlogn) sorting algorithm.

Note: Heap operations that we have used in our solution like insert and extract take O(logn)O(logn) time.

Solution #4: Using Priority Queues

We use STL Priority Queue for our solution. If you want to get an idea of how they are used, have a look at the appendix.

C++
#include<iostream> 
#include<queue> 
using namespace std; 
int minCost(int pipes[], int n) {
  priority_queue <int, vector <int> , greater <int>> myPriorityQueue(pipes, pipes + n);
  int result = 0;
  while (myPriorityQueue.size() > 1) {
    int firstPipe = myPriorityQueue.top();
    myPriorityQueue.pop();
    int secondPipe = myPriorityQueue.top();
    myPriorityQueue.pop();
    result += firstPipe + secondPipe;
    myPriorityQueue.push(firstPipe + secondPipe);
  }
  return result;
}
int main() {
  int pipes[] = {4, 3, 2, 6 };
  int size = sizeof(pipes) / sizeof(pipes[0]);
  cout << "Total cost for connecting pipes list 1 is " << minCost(pipes, size);
  cout << endl << endl;
  int pipes1[] = {1, 1, 2, 6};
  int size1 = sizeof(pipes1) / sizeof(pipes1[0]);
  cout << "Total cost for connecting pipes list 2 is " << minCost(pipes1, size1);
  return 0;
}

This solution uses a C++ data structure priority_queue. Priority queues are a type of container adaptor.

Here, highlighted in the above code (line 2), the syntax of a priority queue is important to note.

Syntax used for priority queues used.

  priority_queue <int, vector <int> , greater <int> > myPriorityQueue(pipes, pipes + n);

We use the greater keyword to use priority queue like a min heap where the first element is the smallest and so on.

In Priority Queues, the first element is always the greatest or the smallest (depending on our choice) of the elements it contains.

This context is very similar to a heap just like we have used in our first solution, where elements can be inserted at any moment, and only the min heap element can be retrieved (the one at the top in the priority queue).

Time Complexity

The time complexity of the algorithm will remain the same because priority queues use heap implementation and therefore sorting takes O(nlogn)O(nlogn) time.