Connect n ropes with minimum cost

Easy

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}