Connect N Ropes

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

1. Create a min-heap and insert all lengths of the ropes into the min-heap.
2. Do the following while the number of elements in the min-heap is greater than one. 
   1. Extract 1st and 2nd smallest lengths from min-heap
   2. Add two extracted values and insert the added value(length of connected rope) to the min-heap.
   3. Maintain a variable for total cost and increment it by the sum of extracted values.
3. 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

Run Code

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

You can also try this code with Online Python Compiler

Run Code

Output

Minimum cost for connecting all the ropes =  32

You can also try this code with Online Python Compiler

Run Code

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.

priority_queue<type, vector<type>, greater<type> > pq;

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. 

You can learn more about Greedy algorithms.

Check Interview experience for top tech companies. Also, you can go through Top Computer Science Interview Questions and Answers.

Refer to our Guided Paths on Coding Ninjas Studio to learn more about DSA, JavaScript, System Design, DBMS, Java, etc. Enrol in our courses and refer to the mock test and problems available. Take a look at the interview experiences and interview bundle for placement preparations.

Happy learning!