Cable Splicing Cost
Problem
A technician has several pieces of cable with the given lengths and must splice them into a single cable. Splicing two pieces of lengths a and b produces one piece of length a + b and costs a + b.
Pieces can be spliced in any order. Return the minimum total cost to end up with one cable. A single piece needs no splicing and costs 0.
Example 1
- Input:
- lengths = [4, 3, 2, 6]
- Output:
- 29
2 + 3 = 5 (cost 5); 4 + 5 = 9 (cost 9); 6 + 9 = 15 (cost 15). Total 29.
Example 2
- Input:
- lengths = [7]
- Output:
- 0
Example 3
- Input:
- lengths = [5, 5]
- Output:
- 10
Constraints
- 1 ≤ lengths.length ≤ 10^4
- 1 ≤ lengths[i] ≤ 10^4
Hint
Show the first hint
A piece that is spliced early gets paid for again in every later splice it takes part in.
Walkthrough
How to approach it
01Clarify before coding
- Is the cost of a splice the length of the result? Yes, a + b.
- Can any two pieces be spliced, not just neighbours? Yes, order is free.
- Can the answer overflow 32 bits? With 10^4 pieces of 10^4 it stays below about 2·10^12 in the worst case, which is fine for Python and for JavaScript numbers.
02Brute force
Try every possible pair to splice at every step and recurse, keeping the cheapest total.
Cost: Exponential: roughly n!·(n-1)!/2^(n-1) splice orders. Even sorting the list and re-sorting after each splice (the greedy without a heap) costs O(n² log n).
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.