Minimum Cost Of Ropes

Given an array arr containing the lengths of the different ropes, we need to connect these ropes to form 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.  

Examples:

Input: 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 gettwo rope of 13 and 2). Finally we connect 13 and 2. Total cost in this way is 10 + 13 + 15 = 38.

Input: arr[] = [4, 2, 7, 6, 9]
Output: 62 
Explanation: First, connect ropes 4 and 2, which makes the array [6, 7, 6, 9]. Cost of this operation 4 + 2 = 6. 
Next, add ropes 6 and 6, which results in [12, 7, 9]. Cost of this operation 6 + 6 = 12.
Then, add 7 and 9, which makes the array [12,16]. Cost of this operation 7 + 9 = 16. And
finally, add these two which gives [28]. Hence, the total cost is 6 + 12 + 16 + 28 = 62.

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

Constraints:
1 ≤ arr.size() ≤ 20⁵
1 ≤ arr[i] ≤ 10⁶

Approach 01:

#include <vector>
#include <queue>

class Solution {
public:
    long long minCost(std::vector<long long>& costs) {
        // Create a min-heap (priority queue) using the input vector
        std::priority_queue<long long, std::vector<long long>, std::greater<long long>> minHeap(costs.begin(), costs.end());
        long long totalCost = 0;

        // While there is more than one element in the heap
        while (minHeap.size() > 1) {
            // Extract the two smallest elements
            long long firstSmallest = minHeap.top();
            minHeap.pop();
            long long secondSmallest = minHeap.top();
            minHeap.pop();

            // Calculate the sum of the two smallest elements
            long long currentCost = firstSmallest + secondSmallest;

            // Add the current cost to the total cost
            totalCost += currentCost;

            // Add the sum back to the heap
            minHeap.push(currentCost);
        }

        return totalCost;
    }
};

import heapq

class Solution:
    def minCost(self, costs):
        # Convert the input list into a min-heap
        heapq.heapify(costs)
        totalCost = 0

        # While there is more than one element in the heap
        while len(costs) > 1:
            # Extract the two smallest elements
            firstSmallest = heapq.heappop(costs)
            secondSmallest = heapq.heappop(costs)

            # Calculate the sum of the two smallest elements
            currentCost = firstSmallest + secondSmallest

            # Add the current cost to the total cost
            totalCost += currentCost

            # Add the sum back to the heap
            heapq.heappush(costs, currentCost)
        
        return totalCost

Time Complexity

• Building the Min-Heap:

  Creating a min-heap (priority queue) from the input vector takes \(O(n)\), where n is the number of elements in the input vector costs.

• Extracting Two Smallest Elements:

  Each extraction operation from the min-heap takes \(O(\log n)\) time. Since there are \(n – 1\) iterations (merging until one element remains), this contributes \(O((n – 1) \cdot \log n)\) to the time complexity.

• Inserting Sum Back into the Min-Heap:

  Each insertion of the sum back into the heap takes \(O(\log n)\). This operation is also performed \(n – 1\) times, leading to an additional \(O((n – 1) \cdot \log n)\) time complexity.

• Overall Time Complexity:

  The overall time complexity is \(O(n) + O((n – 1) \cdot \log n) + O((n – 1) \cdot \log n) = O(n \log n)\).

Space Complexity

• Space for the Min-Heap:

  The min-heap stores up to n elements at any given time, resulting in a space complexity of \(O(n)\).

• Space for Variables:

  Extra space is used for a few local variables such as totalCost, firstSmallest, secondSmallest, and currentCost, which requires \(O(1)\) space.

• Overall Space Complexity:

  The overall space complexity is \(O(n)\) due to the space used by the min-heap.