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 ...