Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Minimum Cost Rope Connection

MEDIUMProblemSolveExternal Links

Description

You are given an array arr[] where each element represents the length of a rope. Your task is to connect all the ropes into a single rope with the minimum total cost.

The rule is simple: to connect any two ropes, you must pay a cost equal to the sum of their lengths. The connected ropes form a new, longer rope whose length equals that sum. You keep connecting ropes until only one rope remains.

The order in which you choose to connect ropes matters — different connection orders lead to different total costs. Your goal is to find the connection order that minimizes the total cost.

If the array contains only one rope, no connections are needed, so the cost is 0.

Examples

Example 1

Input: arr = [4, 3, 2, 6]

Output: 29

Explanation: We want to minimize the total cost of connecting all four ropes into one.

  • First, connect ropes of length 2 and 3 → new rope of length 5, cost = 5. Remaining: [4, 5, 6]
  • Next, connect ropes of length 4 and 5 → new rope of length 9, cost = 9. Remaining: [9, 6]
  • Finally, connect ropes of length 6 and 9 → new rope of length 15, cost = 15. Remaining: [15]

Total cost = 5 + 9 + 15 = 29. This is the minimum possible cost. Notice that we always connected the two shortest ropes at each step.

Example 2

Input: arr = [4, 2, 7, 6, 9]

Output: 62

Explanation: Connecting in order of smallest pairs:

  • Connect 2 and 4 → 6, cost = 6. Remaining: [6, 7, 6, 9]
  • Connect 6 and 6 → 12, cost = 12. Remaining: [7, 12, 9]
  • Connect 7 and 9 → 16, cost = 16. Remaining: [12, 16]
  • Connect 12 and 16 → 28, cost = 28. Remaining: [28]

Total cost = 6 + 12 + 16 + 28 = 62.

Example 3

Input: arr = [10]

Output: 0

Explanation: There is only one rope. No connections are needed, so the total cost is 0.

Constraints

  • 1 ≤ arr.size() ≤ 10^5
  • 1 ≤ arr[i] ≤ 10^4

Editorial

Brute Force

Intuition

The simplest strategy that comes to mind is a greedy one: always connect the two shortest ropes. But how do we find the two shortest ropes efficiently in a brute force manner?

The most straightforward approach is to sort the array at every step. After sorting, the two smallest ropes are at the beginning. We connect them (pay the cost equal to their sum), remove both from the array, and insert the newly formed rope back. Then we repeat — sort again, pick the two smallest, connect, and so on — until only one rope remains.

This works correctly because sorting guarantees we always find the actual minimum pair. However, re-sorting the entire array after every single connection is extremely wasteful. If we have n ropes, we perform n-1 connections, and each connection requires a full sort. This makes the approach slow for large inputs.

Step-by-Step Explanation

Let's trace through with arr = [4, 3, 2, 6]:

Step 1: Sort the array: [2, 3, 4, 6]. The two smallest ropes are 2 and 3.

Step 2: Connect ropes 2 and 3. Cost = 2 + 3 = 5. Remove both from the array and insert the new rope of length 5. Array becomes [4, 5, 6]. Total cost so far: 5.

Step 3: Sort the array again: [4, 5, 6]. The two smallest are 4 and 5.

Step 4: Connect ropes 4 and 5. Cost = 4 + 5 = 9. Array becomes [6, 9]. Total cost so far: 5 + 9 = 14.

Step 5: Sort the array: [6, 9]. The two smallest (and only) ropes are 6 and 9.

Step 6: Connect ropes 6 and 9. Cost = 6 + 9 = 15. Array becomes [15]. Total cost: 5 + 9 + 15 = 29.

Result: The minimum cost to connect all ropes is 29.

Brute Force — Sort and Connect Two Smallest Ropes — Watch how we repeatedly sort the array, pick the two smallest ropes, connect them, and insert the result back until only one rope remains.

Algorithm

  1. Initialize total_cost = 0.
  2. While the array has more than one rope:
    a. Sort the array in ascending order.
    b. Take the two smallest elements (index 0 and 1).
    c. Compute their sum. Add this sum to total_cost.
    d. Remove both elements from the array.
    e. Insert the sum back into the array.
  3. Return total_cost.

Code

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int minCost(vector<int>& arr) {
        int totalCost = 0;
        
        while (arr.size() > 1) {
            // Sort to find two smallest ropes
            sort(arr.begin(), arr.end());
            
            int first = arr[0];
            int second = arr[1];
            
            // Remove the two smallest
            arr.erase(arr.begin());
            arr.erase(arr.begin());
            
            // Connect them and add new rope back
            int cost = first + second;
            totalCost += cost;
            arr.push_back(cost);
        }
        
        return totalCost;
    }
};
class Solution:
    def minCost(self, arr: list[int]) -> int:
        total_cost = 0
        
        while len(arr) > 1:
            # Sort to find two smallest ropes
            arr.sort()
            
            first = arr[0]
            second = arr[1]
            
            # Remove two smallest and insert new rope
            arr = arr[2:]
            cost = first + second
            total_cost += cost
            arr.append(cost)
        
        return total_cost
import java.util.*;

class Solution {
    public int minCost(int[] arr) {
        List<Integer> ropes = new ArrayList<>();
        for (int r : arr) ropes.add(r);
        
        int totalCost = 0;
        
        while (ropes.size() > 1) {
            // Sort to find two smallest ropes
            Collections.sort(ropes);
            
            int first = ropes.get(0);
            int second = ropes.get(1);
            
            // Remove two smallest
            ropes.remove(0);
            ropes.remove(0);
            
            // Connect and insert new rope
            int cost = first + second;
            totalCost += cost;
            ropes.add(cost);
        }
        
        return totalCost;
    }
}

Complexity Analysis

Time Complexity: O(n² log n)

We perform n-1 connection operations. Before each connection, we sort the remaining array. In the worst case, the array starts with n elements and shrinks by one each iteration. Sorting costs O(k log k) for an array of size k. The total work is approximately O(n log n) + O((n-1) log(n-1)) + ... + O(2 log 2), which sums to O(n² log n).

Space Complexity: O(n)

We store all ropes in an array that shrinks by one element per step. The maximum size is n, so we use O(n) additional space (or O(1) extra if we modify the input in place, depending on implementation).

Why This Approach Is Not Efficient

The brute force re-sorts the entire array before every single connection. With n up to 10^5, we perform roughly 10^5 sort operations, each costing up to O(n log n). This results in approximately 10^5 × 10^5 × 17 ≈ 10^{11.2} operations — far beyond what can run within a typical 1-2 second time limit.

The fundamental problem is that sorting from scratch throws away all the ordering information from the previous step. After one connection, only one element changed (two removed, one inserted). A full re-sort is overkill for maintaining order after a single insertion.

Key insight: We need a data structure that can efficiently:

  1. Find and remove the two smallest elements — in O(log n) time.
  2. Insert the new combined rope — in O(log n) time.

A min-heap (priority queue) does exactly this. Building the heap costs O(n) once, and each extract-min and insert operation costs O(log n). Since we perform n-1 connections with 3 heap operations each, the total work becomes O(n log n) — a massive improvement.

Optimal Approach - Min-Heap (Priority Queue)

Intuition

Think about why connecting the two shortest ropes first is optimal. When you connect two ropes, the resulting rope participates in all future connections. A longer rope that is created early will have its length added to the total cost multiple times as it gets combined with other ropes in subsequent steps.

Imagine you are stacking coins. If you pick up a heavy pile early and keep moving it around, you do extra work every time. But if you combine the lightest piles first, the heavy piles only get moved at the very end — just once or twice.

This is the exact same logic as Huffman coding: elements that appear most frequently get the shortest codes (fewest operations), while rare elements get longer codes. Here, the shortest ropes get combined first and their cost propagates through the most subsequent connections.

To always access the two shortest ropes efficiently, we use a min-heap. A min-heap keeps the smallest element at the top, and extracting it or inserting a new element both take O(log n) time. This is exactly the data structure we need:

  1. Build a min-heap from all rope lengths — O(n).
  2. Extract the two smallest ropes — two O(log n) operations.
  3. Connect them, add the cost to the total, and insert the new rope back — one O(log n) operation.
  4. Repeat until one rope remains.

Step-by-Step Explanation

Let's trace through with arr = [4, 3, 2, 6]:

Step 1: Build a min-heap from the array. After heapification: the heap contains {2, 3, 4, 6} with 2 at the top (smallest element). Total cost = 0.

Step 2: Extract the minimum: 2. Extract the next minimum: 3. These are the two shortest ropes.

Step 3: Connect them: 2 + 3 = 5. Pay cost 5. Total cost = 5. Insert rope 5 back into the heap. Heap now contains {4, 5, 6} — the heap property is maintained automatically.

Step 4: Extract minimum: 4. Extract next minimum: 5. These are the two shortest remaining ropes.

Step 5: Connect them: 4 + 5 = 9. Pay cost 9. Total cost = 5 + 9 = 14. Insert rope 9 back. Heap now contains {6, 9}.

Step 6: Extract minimum: 6. Extract next minimum: 9. The last two ropes.

Step 7: Connect them: 6 + 9 = 15. Pay cost 15. Total cost = 5 + 9 + 15 = 29. Insert rope 15. Heap contains {15} — only one rope remains.

Result: Minimum total cost = 29. We performed 3 connections, each requiring 2 extractions and 1 insertion — all O(log n). No full re-sorting needed.

Min-Heap — Always Extract Two Smallest, Connect, Reinsert — Watch how the min-heap efficiently gives us the two shortest ropes at each step, avoiding the need to re-sort the entire array.

Algorithm

  1. If the array has 0 or 1 elements, return 0 (no connections needed).
  2. Build a min-heap from all rope lengths.
  3. Initialize total_cost = 0.
  4. While the heap contains more than one element:
    a. Extract the minimum element (shortest rope).
    b. Extract the next minimum element (second shortest rope).
    c. Compute their sum — this is the connection cost.
    d. Add the connection cost to total_cost.
    e. Insert the sum (the new combined rope) back into the heap.
  5. Return total_cost.

Code

#include <vector>
#include <queue>
using namespace std;

class Solution {
public:
    int minCost(vector<int>& arr) {
        // Edge case: 0 or 1 ropes
        if (arr.size() <= 1) return 0;
        
        // Build a min-heap from all rope lengths
        priority_queue<int, vector<int>, greater<int>> pq(
            arr.begin(), arr.end()
        );
        
        int totalCost = 0;
        
        // Keep connecting until one rope remains
        while (pq.size() > 1) {
            // Extract two shortest ropes
            int first = pq.top(); pq.pop();
            int second = pq.top(); pq.pop();
            
            // Connect them
            int cost = first + second;
            totalCost += cost;
            
            // Insert combined rope back
            pq.push(cost);
        }
        
        return totalCost;
    }
};
import heapq

class Solution:
    def minCost(self, arr: list[int]) -> int:
        # Edge case: 0 or 1 ropes
        if len(arr) <= 1:
            return 0
        
        # Build a min-heap in-place
        heapq.heapify(arr)
        
        total_cost = 0
        
        # Keep connecting until one rope remains
        while len(arr) > 1:
            # Extract two shortest ropes
            first = heapq.heappop(arr)
            second = heapq.heappop(arr)
            
            # Connect them
            cost = first + second
            total_cost += cost
            
            # Insert combined rope back
            heapq.heappush(arr, cost)
        
        return total_cost
import java.util.PriorityQueue;

class Solution {
    public int minCost(int[] arr) {
        // Edge case: 0 or 1 ropes
        if (arr.length <= 1) return 0;
        
        // Build a min-heap from all rope lengths
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int rope : arr) {
            pq.add(rope);
        }
        
        int totalCost = 0;
        
        // Keep connecting until one rope remains
        while (pq.size() > 1) {
            // Extract two shortest ropes
            int first = pq.poll();
            int second = pq.poll();
            
            // Connect them
            int cost = first + second;
            totalCost += cost;
            
            // Insert combined rope back
            pq.add(cost);
        }
        
        return totalCost;
    }
}

Complexity Analysis

Time Complexity: O(n log n)

Building the min-heap from n elements takes O(n) time. The main loop runs n-1 times (one fewer than the number of ropes). In each iteration, we perform two extract-min operations (each O(log n)) and one insert operation (O(log n)). That gives us (n-1) × 3 × O(log n) = O(n log n) total work. The heap build is dominated by the loop, so the overall time complexity is O(n log n).

Space Complexity: O(n)

The min-heap stores all n rope lengths initially. As ropes are connected, the heap shrinks by one element per iteration. At any point the heap holds at most n elements, so the space usage is O(n). If we build the heap in-place (as in the Python implementation using heapify), no extra array is needed beyond the input.