Connect Ropes(code and explanation)

#leetcode #algorithms #python #beginners

Yet another question on a mixture on Greedy approach utilizing heap data structure
Problem Statement
Given ‘N’ ropes with different lengths, we need to connect these ropes into one big rope with minimum cost.
The cost of connecting two ropes is equal to the sum of their lengths.
Example 1:
Input: [1, 3, 11, 5]
Output: 33
Explanation: First connect 1+3(=4), then 4+5(=9), and then 9+11(=20). So the total cost is 33 (4+9+20)
Example 2:
Input: [3, 4, 5, 6]
Output: 36
Explanation: First connect 3+4(=7), then 5+6(=11), 7+11(=18). Total cost is 36 (7+11+18)
SOLUTION
This question is a perfect example of how heap data structure can be utilized in solving a question that requires greedy approach
In this case, everytime you have to add the smallest two numbers.You can even do this question using a auxillary array that will store all the prefix sums
but here we will be utilizing an heap to do so
ALGORITHM
1.Make a min heap
2.Push all the elements in the heap
3.Remove top two elements from the heap and store its sum in another variable
4.Push this sum again in the heap
5.Continue till heap is empty

from heapq import *
def connectRopes(ropeLengths):
    minHeap = []
    for length in ropeLengths: #push all the lengths in heap
        heappush(minHeap, length)

    finalLength = 0
    while len(minHeap) > 1:
        temp = heappop(minHeap) + heappop(minHeap) #pop the first two elements
        finalLength += temp #Calculate its sum and store in another variable 
        heappush(minHeap, temp) #Push the current sum again in heap for further calculations
    return finalLength

Time Complexity
Inserting all the elements inside a heap will take O(NlogN)
Removing top two elements and again push in heap will take a maximum of O(NlogN) time
So overall time complexity is O(NlogN)
Space Complexity
minHeap will require a space of O(N)