Connecting ropes with minimum cost

Question

Question:
There are given N ropes of different lengths, we need to connect these ropes into one rope. The cost to connect two ropes is equal to sum of their lengths. The task is to connect the ropes with minimum cost. Given N size array arr[] contains the lengths of the ropes.

Example 1:

Input: n = 4 arr[] = {4, 3, 2, 6} Output: 29 Explanation: We can connect the ropes in following ways.

1. First connect ropes of lengths 2 and 3. Which makes the array {4, 5, 6}. Cost of this operation 2+3 = 5.
2. Now connect ropes of lengths 4 and 5. Which makes the array {9, 6}. Cost of this operation 4+5 = 9.
3. Finally connect the two ropes and all ropes have connected. Cost of this operation 9+6 =15 Total cost for connecting all ropes is 5

• 9 + 15 = 29. This is the optimized cost for connecting ropes. Other ways of connecting ropes would always have same or more cost. For example, if we connect 4 and 6 first (we get three rope of 3, 2 and 10), then connect 10 and 3 (we get two rope of 13 and 2). Finally we connect 13 and 2. Total cost in this way is 10 + 13 + 15 = 38.

28 = 62. Your Task: You don't need to read input or print anything. Your task isto complete the function minCost() which takes an integer array arr[] and an integer n as arguments and returns the minimum cost.

Expected Time Complexity : O(nlogn) Expected Auxilliary Space : O(n)

Constraints: 1 ≤ N ≤ 200000 1 ≤ arr[i] ≤ 106

It is one of the questions from GeeksforGeeks, Minimum Cost of ropes.

class Solution:
    #Function to return the minimum cost of connecting the ropes.
    def minCost(self,arr,n) :
    
        # code here
        arr.sort()
        arr2=[]
        cost=0
        
        for x in range(len(arr)-1):
            
            cost=arr[0]+arr[1]
            arr.remove(arr[0])
            arr.remove(arr[0])
            arr.append(cost)
            arr2.append(cost)
            arr.sort()

        return(sum(arr2))

The code took 8 secs to run for one of the test cases
How can I reduce the time of the code?
Please suggest some measures to improve this code.

Answer 1

Coding style

I suppose your Solution class and function signature are not your call but were imposed by your programming exercise environment (I'm not familiar with GeeksForGeeks, but it looks very similar to LeetCode).

As such, the right call is to stick to these conventions, which you did and which is fine.

However, these conventions differ from the conventions recommended by PEP8. In case you want to practice your coding style as well, there are a few changes that you should make:

• Rename your method name using snake case: min_cost
• Document your class and methods using docstrings, not comments: see PEP257
• Remove unused variables, in this case the n argument which serve no purpose.

Also, some changes should be made even in the context of whatever conversion you are following:

• there is no need to initialize cost outside of its scope
• rename arr2 with a more descriptive name, perhaps costs
• the loop counter x is unused. Such throwaway variables are conventionally named _
• add some space around operators: cost = arr[0] + arr[1], return sum(arr2)

Performance

Small improvements

Get rid of arr2. You don't need to keep track of all individual costs, only their total.

As such, you can simply initialize total_cost = 0 and add the latest cost to the total instead of appending it to the list. Finally, simply return that value.

This matters especially on larger scales, are as values are appended to the list, memory is regularly allocated to fit the data, which is rather slow. Updating the value of a single integer requires no further allocation.

Algorithm

The problem states:

Expected Time Complexity : O(nlogn)

In your case, you loop over the size of the array (o(n)) and sort a list in each loop (o(m logm)). Since your list size decreases with each pass, the time complexity isn't quite o(n²logn), and in fact quick testing shows it is approximately o(n²). There lies your performance issue.

Appending and removing from the end of lists is o(1) in Python, so the append operations should scale fairly well (o(n), due to the loop). However, the remove operations on the start of the list are o(n), so you should find a way to do without them.

In fact, on a fairly large input, profiling shows that >90% of the time is spent sorting lists.

The obvious target here is to get rid of the sort. One possibility is to insert the cost into the right position in the array, saving quite some time. On my machine, execution for a list of size 100,000 dropped from 19 seconds to 5, an appreciable improvement. However, the algorithm is still o(n²) overall and won't scale nicely with larger inputs.

Unfortunately, I can't think of a solution right now to hit the o(n logn) target. Try to think outside of the box, and good luck.