Connect Ropes with Minimum Cost

Problem Statement

You have n ropes of various lengths. The cost to connect two ropes equals the sum of their lengths (the resulting rope has that combined length). Connect all ropes into one with minimum total cost.

Input

An array of positive rope lengths.

ropes = [4, 3, 2, 6]

Output

The minimum total cost to connect them all.

29
 
// optimal sequence:
// 2 + 3 = 5   (cost 5)
// 4 + 5 = 9   (cost 9)
// 6 + 9 = 15  (cost 15)
// total: 5 + 9 + 15 = 29

Constraints

• 1 ≤ ropes.length ≤ 10⁵
• 1 ≤ ropes[i] ≤ 10⁴

Intuition

This is a Huffman-tree problem in disguise. The greedy rule: at each step, combine the two smallest remaining ropes. Why? Every combination cost propagates into all future combinations — the smaller the rope, the fewer times you want its length re-counted. A min-heap gives us instant access to the two smallest at each step.

Proof sketch: in any optimal merging tree, a leaf contributes its length multiplied by its depth. Smaller values should live deeper (combined first); larger values shallower (combined last). The greedy heap strategy realizes that optimal tree.

heap (min):  [2, 3, 4, 6]
pop 2, pop 3 → combined = 5   total = 5    push → [4, 5, 6]
pop 4, pop 5 → combined = 9   total = 14   push → [6, 9]
pop 6, pop 9 → combined = 15  total = 29   push → [15]
                                              ^ total = 29 ✓

Solution

import heapq
 
def minCostToConnectRopes(ropes: list[int]) -> int:
    heapq.heapify(ropes)                 # O(n)
    total_cost = 0
    while len(ropes) > 1:
        a = heapq.heappop(ropes)
        b = heapq.heappop(ropes)
        combined = a + b
        total_cost += combined
        heapq.heappush(ropes, combined)
    return total_cost

function minCostToConnectRopes(ropes: number[]): number {
  const h = new Heap<number>((a, b) => a - b, ropes);   // heapify in constructor
  let total = 0;
  while (h.size > 1) {
    const a = h.pop()!;
    const b = h.pop()!;
    const combined = a + b;
    total += combined;
    h.push(combined);
  }
  return total;
}

Complexity

Edge Case Thinking