The ‘Connect n ropes’ problem is one of the popular questions commonly asked in technical interviews. This problem is the implementation of Huffman coding, well known greedy approach used to find greedy-based solutions.

So, without further ado, let’s jump into the problem statement.

There are n ropes of different lengths; connect n ropes into one rope. The cost of joining two ropes equals the sum of their lengths. We need to connect all the ropes at a minimum cost. The task is to find the minimum cost.

Example

Input

n=4
arr[] = {5,3,2,7}

You can also try this code with Online C++ Compiler

Here, we extract the minimum lengths from the list in every step to connect the ropes. We need min-heap to implement such an action as the smallest value always remains at the top(i.e., root).

In the above example, the 1st and 2nd smallest lengths are 2 and 3, respectively. So, we connect them first(2+3=5 ).

Now the available lengths are 5, 5, and 7, where the 1st and 2nd smallest lengths are 5 and 5, respectively, so we join them(5+5=10). After connecting them, the available lengths are 10 and 7.

Connecting these two lengths, the final length of the connected ropes (10+7)=17.

We connect the ropes three times to get the final length. So the cost is 5+10+17=32.

Greedy Approach

Here, we follow the optimal merging pattern to minimise the cost of connecting the n ropes. We will always take the greedy approach of connecting 1st and 2nd smallest ropes and repeat for the remaining ropes along with the newly connected rope.

Algorithm

Create a min-heap and insert all lengths of the ropes into the min-heap.

Do the following while the number of elements in the min-heap is greater than one.

Extract 1st and 2nd smallest lengths from min-heap

Add two extracted values and insert the added value(length of connected rope) to the min-heap.

Maintain a variable for total cost and increment it by the sum of extracted values.

Return the value of this total cost.

Dry Run

Suppose we have the following array of ropes:

Now, we insert all of the lengths of the ropes into the min heap. Let’s say we have a min heap named “Min Heap”.

Inserting all the elements in the min heap such that the minimum element always appears at the root:

Taking out two smallest elements from the heap and inserting their sum back into the heap.

Hence we take out 2 and 3 and insert 5(2+3) back into the heap. 5 will also be added to the total cost.

Now, again, remove the two minimum elements from the min heap and insert their sum into the heap. Update the total cost again.

Now, again taking out the two minimum elements from the min heap and inserting back their sum into the heap. Update the total cost again.

Now, there is only one element left in the min heap, so we can stop. We will return total cost as our final answer.

Code

Implementation In C++

//c++ code for the 'Connect n ropes' problem
#include<bits/stdc++.h>
using namespace std;
//function to return the minimum cost of connecting the ropes.
long long mincostRopes(long long arr[], long long n) {
// step 1: creating a min-heap
priority_queue<long long, vector<long long>,greater<long long> > pq;
for(int i=0;i<n;i++)
{
pq.push(arr[i]);
}
//Initialising cost variable
long long cost=0;
// step 2
while(pq.size()>1)
{
// extract 1st and 2nd smallest lengths from min-heap
long long a=pq.top();
pq.pop();
long long b=pq.top();
pq.pop();
long long combinedRope=a+b;
// incrementing the cost
cost+=combinedRope;
if(pq.size()==0)
{
return cost;
}
//inserting the added value
pq.push(combinedRope);
}
return 0;
}
// driver code
int main()
{
long long n=4;
long long arr[]={5,3,2,7};
cout<<"Minimum cost for connecting all the ropes = "<<mincostRopes(arr,n);
return 0;
}

You can also try this code with Online C++ Compiler

#python code for the 'Connect n ropes' problem
from queue import PriorityQueue
#function to return the minimum cost of connecting the ropes.
def mincostRopes(arr,n):
#step 1: creating a min-heap
pq = PriorityQueue()
for i in arr:
pq.put(i)
#Initialising cost variable
cost=0
#Step 2
while pq.qsize()>1:
#extract 1st and 2nd smallest lengths from min-heap
a=pq.get()
b=pq.get()
combinedRope=a+b
#Updating Cost
cost+=combinedRope
if pq.qsize()==0:
return cost
#inserting the added value
pq.put(combinedRope)
return 0
n=4
arr=[5,3,2,7]
print("Minimum cost for connecting all the ropes = ",mincostRopes(arr,n))

You can also try this code with Online Python Compiler

What is the time complexity of insertion operation in a min-heap?

The time complexity of the insertion operation in a min-heap is O(NlogN).

What is the height of a min heap with N elements?

The height of a min heap with N elements is O(logN).

Conclusion

This article on the problem ‘connect n ropes’ discussed the approach of connecting n ropes with minimum cost using the concept of greedily merging ropes.

Apart from this, you can practice a wide range of coding questions commonly asked in interviews in Coding Ninjas Studio. Along with coding questions, we can also find the interview experience of scholars working in renowned product-based companies here.