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.
PseudoCode
Algorithm
___________________________________________________________________
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
___________________________________________________________________
CODE IN C++
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";
cin>>n;
//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++){
cin>>ropeLength;
minh.push(ropeLength);
}
//Run the loop till the size of the minheap becomes less than 2.
while(minh.size()>=2){
int first=minh.top();
minh.pop();
int second=minh.top();
minh.pop();
cost=cost+first+second;
minh.push(first+second);
}
//Returning the result
cout<<cost<<endl;
}
You can also try this code with Online C++ Compiler
Output
Sample Input:
5
1 2 3 4 5
Sample Output:
33
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.
Conclusion
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.
Cheers!
26+ registered 
