Connect n ropes with minimum cost
Problem
Connecting two ropes of lengths a and b costs a + b and produces a rope of length a + b. Return the minimum total cost to connect all the ropes into one.
Example 1
Input: [4, 3, 2, 6] Output: 29
2+3=5, 4+5=9, 6+9=15 → 5 + 9 + 15.
Also asked as: Connect “n” ropes with minimum cost
Test cases
Case 1
Input: [4,3,2,6] Expected: 29
Case 2
Input: [1,2,3,4,5] Expected: 33
Case 3
Input: [2,2] Expected: 4
Case 4
Input: [5] Expected: 0
View solutionHide solution1 approach
1. Min-heap greedy (Huffman-style)
Time O(n log n)Space O(n)
Always join the two shortest ropes; add the combined length to the cost and back to the heap.
function connectRopes(lengths) { const heap = [...lengths].sort((a, b) => a - b); let cost = 0; while (heap.length > 1) { const a = heap.shift(), b = heap.shift(); const sum = a + b; cost += sum; let i = heap.findIndex((v) => v > sum); i === -1 ? heap.push(sum) : heap.splice(i, 0, sum); } return cost;}