Code360 powered by Coding Ninjas X Code360 powered by Coding Ninjas X
Table of contents
Naive Approach
Optimized Approach
Frequently Asked Questions
How to approach a problem like this?
What is a min-heap? 
Last Updated: Mar 27, 2024

Connect N ropes with minimum cost

Author Urwashi Priya
0 upvote
Master Python: Predicting weather forecasts
Ashwin Goyal
Product Manager @


DSA Problems

In this blog, we will discuss a minimization 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 l1 and l2 are defined as their sum of lengths, i.e. l1 + l2.

(Also see, Data Structures)

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

illustration image

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

The optimal solution would be:

illustration image

Also read, Euclid GCD Algorithm

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.

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

Optimized Approach

To minimize 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.




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 a variable second.

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

7.   Now insert the 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



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";
    //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++){
    //Run the loop till the size of the minheap becomes less than 2.
    //Returning the result


Sample Input: 


1 2 3 4 5

Sample Output:


Time Complexity: O(n *  log n).

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

Check out this problem - Two Sum Problem

Frequently Asked Questions

How to approach a problem like this?

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 optimize your code.

What is a min-heap? 

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


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 Coding Ninjas Studio.

Recommended Readings:

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, Basics of C++, Basics of Java, Basics of Python, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.


Previous article
Kth Smallest Element in a Row-Wise and Column-Wise sorted 2D Array
Next article
Sum and Product of K Smallest and Largest Fibonacci Numbers in the Array
Live masterclass