Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem statement
2.1.
Example
2.2.
Explanation
3.
Greedy Approach 
3.1.
Algorithm
3.2.
Dry Run
4.
Code
4.1.
Implementation In C++
4.2.
Implementation In Python
5.
Complexity analysis
5.1.
Time Complexity
5.2.
Space Complexity
6.
Frequently Asked Questions
6.1.
What is Huffman coding?
6.2.
For which kind of problems should we apply the greedy-based approach?
6.3.
How to implement min-heap using the C++ STL library?
6.4.
What is the time complexity of insertion operation in a min-heap?
6.5.
What is the height of a min heap with N elements?
7.
Conclusion
Last Updated: Mar 27, 2024
Medium

Connect N Ropes

Author Rhythm Jain
0 upvote
gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
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.

OG image

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

Also Read, Prefix Sum Array

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

Example

Input

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

Output

32

Explanation

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

  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:

input array

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

dry run 1

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

dry run 2

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.

dry run 3

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

dry run 4

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.

dry run 5

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.

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!

Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass