How to approach a problem like this?

Answer) First, understand the problem. The best way is to use diagrams. Then write your algorithm. Then start with the Brute Force method. Lastly, try to optimise your code.

Answer) A look-alike of a binary tree; value in the root must be less than that of left and right child.

Connect N ropes with minimum cost

Introduction

In this blog, we will discuss a minimisation problem that has been asked frequently in Interviews.

The problem is to Connect N ropes with minimum cost.

We are given N number of ropes with their lengths, and we have to connect these N ropes with minimum cost. The cost of connecting any two ropes of lengths l₁ and l₂ are defined as their sum of lengths, i.e. l₁ + l₂.

Example: To connect five ropes of given lengths 1,2,3,4,5 respectively, the minimum cost will be 33.

The diagram mentioned above doesn’t give the minimal cost. It is just one of many solutions possible.

The optimal solution would be:

Naive Approach

The naive approach to connect N ropes with minimum cost would be finding the two most minor elements out of all existing elements, noting down their total cost and recursively repeating the step.

We can do this by sorting the elements after each iteration.

Best Time Complexity for sorting = n log n

So, for n iterations, it would take = n²log n

Sort all the elements in ascending order

⬇

Take two ropes of minimum lengths and combine them

⬇

Delete the two minimal lengths taken above and insert a new length(sum of lengths)

⬇

Repeat the above steps till the elements left in the array is less than 2.

Optimized Approach

To minimise the time complexity, we will bring the heap into the picture.

So in the most optimal approach, the time complexity for this problem will reduce from O (n²*log n) to O (n*log n).

Now we will be discussing our second, the optimized approach.

Create a min Heap

⬇

At any time, take two ropes of minimum lengths and combine them.

⬇

Pop the two minimal lengths taken above and insert a new length(sum of lengths) into the min-heap.

⬇

Find the most optimal Cost.

Till now, I assume you must have got the basic idea of what has been asked in the problem statement. So, I strongly recommend you first give it a try: Connect N Ropes With Minimum Cost

Please have a look at the algorithm, and then again, you must give it a try.

PseudoCode

Algorithm

___________________________________________________________________

procedure minimiseCost( ):

___________________________________________________________________

1. Declare min-heap on the lengths of the given ropes.

2. Initialise a variable, say cost=0.

3. Initialise two variables, first and second.

4. Pop the top element from the min-heap and assign it to the variable first.

5. Again, pop the top element from the min-heap and assign it to variable second.

6. Add the cost of combining these lengths as cost = cost + first + second.

7. Now insert this cost of combining these lengths(first + second) into a min-heap.

9. Repeat all the steps mentioned above till the size of the min-heap becomes less than 2.

10. Return cost.

end procedure

___________________________________________________________________

CODE IN C++

Now, let’s have a look at the Code:

#include <bits/stdc++.h>

using namespace std;

int main() {
  //Cost is to find the optimal result to connect all ropes.
  //n is for the number of ropes.
  //ropeLength is for the length of each rope.
  int cost=0,n, ropeLength;
  cout<<"Enter the number of ropes";
  cin>>n;

  //Declaring min-heap
priority_queue<int, vector<int>, greater<int>>minh;

  //Taking input from the user about the rope's length.
  for(int i=0; i<n; i++){
  cin>>ropeLength;
minh.push(ropeLength);
}

  //Run the loop till the size of the minheap becomes less than 2.
  while(minh.size()>=2){
  int first=minh.top();
minh.pop();
  int second=minh.top();
minh.pop();
cost=cost+first+second;
minh.push(first+second);
}

  //Returning the result
  cout<<cost<<endl;
}

Output

Sample Input:

1 2 3 4 5

Sample Output:

Time Complexity: O(n * log n).

Analysing Time Complexity:

Insertion in a heap costs log n time.Since we have to do for n iterations ∴ n log n.

Space complexity: O(n) as we maintain a min-heap to store the lengths of the ropes.

Frequently Asked Questions

How to approach a problem like this?
Answer) First, understand the problem. The best way is to use diagrams. Then write your algorithm. Then start with the Brute Force method. Lastly, try to optimise your code.
What is min-heap?
Answer) A look-alike of a binary tree; value in the root must be less than that of left and right child.

Key Takeaways

This article taught us how to Connect N ropes with minimum cost by approaching the problem using a min-heap. We discussed its implementation using illustrations, pseudocode, and then proper code.

We hope you could take away critical techniques like analyzing problems by walking over the execution of the examples and finding out the recursive pattern followed in most binary search tree problems.

Now, we recommend you practice problem sets based on binary search trees to master your fundamentals. You can get a wide range of questions similar to this on CodeStudio.