## Minimum cost of connecting n ropes

Given n ropes of different lengths, connect these ropes in one rope. The cost to connect two ropes is equal to the sum of their lengths. We have to connect these ropes with minimum cost.

For example,

```Input:
5, 2, 3, 9.
Output:
34
Explanation:
We can connect the ropes in the following way: First, connect the ropes of lengths 2 and 3, the cost of this connection is the sum of lengths of ropes which is 2 + 3 = 5. We are left with three ropes with lengths5,5, and 9. Next, connect the ropes of lengths 5 and 5. The cost of connection is 10. Total cost till now is 5 + 10 = 15. We have two ropes left with lengths 10 and 9. Finally, connect the last two ropes and all ropes have connected, Total Cost would be 15 + 19 = 34.
```

Another way of connecting ropes would be: connect ropes with lengths 5 and 9 first (we get three ropes of 3, 2, and 14), then connect 14 and 3, which gives us two ropes of lengths 17 and 2. Finally, we connect 19 and 2. Total cost in this way is 14 + 17 + 21 = 52. which is much higher than the optimal cost we had earlier.

## Connect n ropes with minimum cost: A priority queue problem

When we were doing calculations in examples, did you notice one thing? Lengths of the ropes connected first are added subsequently in all the connections. For example, we connected ropes with length 2 and 3 in the first example, it gets added to next connect as part of the rope with length 5, and again when we connect the ropes with lengths 15 and 9, 2 + 3 is already inside 15.

Read Huffman coding to understand how to solve this problem from this hint.

All we have to make sure that the most repeated added rope is the smallest, then the second smallest and so on. This gives the idea that if we sort the ropes by their sizes and add them, sort again the array again until there are no ropes to add. It will always give us the optimal solution to connect ropes.

What will be the complexity of sorting based implementation? The complexity will be dominated by the sorting algorithm, best we can achieve is O(nlogn) using quicksort or merge sort. Also, connecting two ropes we have to sort the arry again. So overall complexity of this method is O(n2logn)

Can we do better than this? Do we need the array sorted at all times? All we need is the two ropes with the least length. What data structure gives us the minimum element in the least time. Priority queue will be our data structure. If we create a min-heap with lengths of ropes, we can easily find the two ropes with the least length in O(1) complexity.

1. Create a min heap (priority queue) from the array of rope lengths
2. Fetch the root which will give us smallest rope
3. Fetch the root again which will give us second smallest rope
4. Add two ropes and put it back into heap (heapify)
5. Go back to step 2 ### Min cost to connect ropes java implementation

```
package com.company;

import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.stream.Collectors;

/**
* Created by sangar on 3.1.19.
*/
public class ConnectRopes {

public int getMinimumCost(int[] ropeLength){

PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();

/*
There is no shortcut for converting from
int[] to List<Integer> as Arrays.asList
does not deal with boxing and will just create a List<int[]>
which is not what you want.
*/
List<Integer> list = Arrays.stream(ropeLength)
.boxed().collect(Collectors.toList());

/*
inherited from AbstractQueue where
it is implemented as a sequence of adds.
So complexity of this operation is O(nlogn)
*/

int totalLength = 0;

while(minHeap.size() > 1){
int len1 = (int)minHeap.remove();
int len2 = (int)minHeap.remove();

totalLength+=(len1 + len2);

}

}
}
```
Test cases
```package test;

import com.company.ConnectRopes;
import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.assertEquals;
/**
* Created by sangar on 23.9.18.
*/
public class ConnectRopeTest {

ConnectRopes tester = new ConnectRopes();

@Test
public void minimumCostTest() {

int[] a = {5,2,3,9};

assertEquals(24, tester.getMinimumCost(a));
}
@Test
public void minimumCostOneRopeTest() {

int[] a = {5};

assertEquals(0, tester.getMinimumCost(a));
}
}
```

The complexity of this implementation is O(nlogn) (to create min heap out of an array in java Priority queue) + O(nlogn) (to fetch two minimum and re-heapify). However, initial complexity to build a heap from the array can be brought down to O(n) by using own implementation of min heap.

Please share if there is something wrong or missing. If you are preparing for interviews and want to receive a daily email with an interview question, please signup here