Data structures & algorithms (Beginner to Intermediate)

Free guided path13 chapters99+ problems

Earn badges and level up

Introduction

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}

Output

32

Explanation

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.

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

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;
}

Output

Minimum cost for connecting all the ropes = 32

Implementation In Python

#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))

Output

Minimum cost for connecting all the ropes = 32

Complexity analysis

Time Complexity

In the ‘connect n ropes’ problem O(nlogn) is the time complexity as heap operation takes O(logn) time for inserting or extracting elements.

Space Complexity

The space complexity is O(n) for n elements in the min-heap.

Frequently Asked Questions

What is Huffman coding?

Huffman code is a particular type of optimal prefix code commonly used as a lossless data compression algorithm.

For which kind of problems should we apply the greedy-based approach?

The problems where choosing local optimal solutions leads to the global optimal solution, are the best fit for the greedy-based approach.

How to implement min-heap using the C++ STL library?

In C++, STL library priority_queue is by default made max-heap. To use priority_queue as min-heap, we need to add two extra arguments as shown below.

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.