Coding · Heaps
Minimum Cost to Connect Ropes
- Reported once
- Medium
- SDE-1
- 1 source
One candidate write-up. Treat it as a single data point.
Solve it in the playground, with tests
You have a list of rope lengths and keep joining two ropes at a time until one rope remains, where a join costs the sum of the two lengths and leaves one rope of that combined length. Return the smallest possible total cost, or 0 when there are fewer than two ropes. For [4,3,2,6] the answer is 29: join 2 and 3 for 5, then 4 and 5 for 9, then 6 and 9 for 15. The list can have 100,000 ropes with lengths up to 10,000.
Restated in our own words, not a quote from Ola or any page. The answer below is written for this site.
Clarify first
Pin down the input before you touch the keyboard.
I would ask: does a join cost exactly the sum of the two lengths, and can the new rope be joined again at once? Are lengths positive integers? Can I pick any two ropes or only neighbors? What do I return for no rope or one rope? How many ropes can there be, and does the total cost fit in a normal number?
I would assume any two ropes may be chosen, lengths are positive, zero or one rope costs 0, and the total, under 2×10^10 for 100,000 ropes of length 10,000, fits a double exactly. I would also leave the caller's array untouched.
Brute force
Say the obvious answer and why it is too slow.
Try every order: pick any pair, join it, recurse on the shorter list, and keep the cheapest result. The number of choices multiplies down from n(n-1)/2, so the search grows faster than exponentially and is hopeless past a dozen ropes.
A cheaper idea is also correct: sort, join the two smallest, put the result back, and sort again. But a general re-sort costs O(n log n) per round, and there are n-1 rounds, so the bound is O(n² log n); a sort that detects existing runs may do better on nearly sorted data, but I would not rely on it. Taking the two smallest off the front and inserting the sum by binary search still shifts elements, O(n) per round and O(n²) overall, about ten billion moves at 100,000 ropes. So we need a structure that hands back the smallest items and accepts new ones cheaply.
The insight
The one idea that makes it fast, and why it is correct.
- Brute force
- O(n² log n)
- Time
- O(n log n)
- Space
- O(n)
The pattern is greedy with a min-heap, the same idea as building a Huffman code. Think of the joins as a tree: the original ropes are leaves, each join is an inner node, and a rope's length is paid once for every join on its way to the root. The total cost is therefore the sum of each rope's length times its depth. To keep the total low, long ropes should sit near the root (few joins) and short ropes deep (many joins).
That says to join the two shortest ropes first. The exchange argument: in any optimal plan, take a deepest pair of sibling ropes. If a shorter rope sits higher than a longer one, swapping their places lowers the cost or leaves it equal, so the two shortest ropes can be assumed to be those deepest siblings. Join them, and the problem becomes the same problem with one fewer rope, so repeat.
A min-heap does exactly what is needed: pop the two smallest in O(log n), push their sum back in O(log n), and repeat n-1 times. JavaScript has no built-in heap, so I would write a small one, or state that I would use one. Add each joined length to a running total. I would say it aloud as: always glue the two lightest ropes, because their lengths will be paid for again and again.
Walk it through
A dry run on the example, step by step.
| Round | Pop two | Join cost | Heap after | Total |
|---|---|---|---|---|
| start | - | - | 2, 3, 4, 6 | 0 |
| 1 | 2 and 3 | 5 | 4, 5, 6 | 5 |
| 2 | 4 and 5 | 9 | 6, 9 | 14 |
| 3 | 6 and 9 | 15 | 15 | 29 |
Use [4,3,2,6]. The heap holds 2, 3, 4, 6 at the start, and the trace table lists each round.
Round 1: pop 2 and 3, the two smallest. The join costs 5, the running total is 5, and 5 goes back in, so the heap holds 4, 5, 6. Round 2: pop 4 and 5, cost 9, total 14, push 9, so the heap holds 6 and 9. Round 3: pop 6 and 9, cost 15, total 29, push 15. One rope is left, so the loop stops and the answer is 29. Joining in the given order, 4+3, then 7+2, then 9+6, would cost 7+9+15 = 31, which shows why order matters.
The code
Runnable JavaScript, checked against test cases.
function minCostToConnectRopes(ropes) {
const heap = [];
const push = (value) => {
heap.push(value);
let i = heap.length - 1;
while (i > 0 && heap[i] < heap[(i - 1) >> 1]) {
const parent = (i - 1) >> 1;
[heap[i], heap[parent]] = [heap[parent], heap[i]];
i = parent;
}
};
const pop = () => {
const smallest = heap[0];
const last = heap.pop();
if (heap.length === 0) return smallest;
heap[0] = last;
let i = 0;
for (;;) {
let least = i;
if (2 * i + 1 < heap.length && heap[2 * i + 1] < heap[least]) least = 2 * i + 1;
if (2 * i + 2 < heap.length && heap[2 * i + 2] < heap[least]) least = 2 * i + 2;
if (least === i) return smallest;
[heap[i], heap[least]] = [heap[least], heap[i]];
i = least;
}
};
ropes.forEach(push);
let totalCost = 0;
while (heap.length > 1) {
const joined = pop() + pop();
totalCost += joined;
push(joined);
}
return totalCost;
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Edge cases
What to test before you say you are done.
An empty list or a single rope never enters the loop, so the answer is 0. Two ropes cost exactly their sum after one round. Equal lengths such as [5,5,5,5] are fine: the heap simply pops two equal values each time, giving 10 + 10 + 20 = 40.
One very long rope with many tiny ones works naturally, since the long rope stays in the heap until the end. If lengths could be zero, the code still works, because joining a zero adds nothing. The input is copied into a separate heap, so the caller's array is never changed. For 100,000 ropes of length up to 10,000, the total stays well below 2^53, so plain numbers are exact.
Follow-ups to expect
Where the interviewer pushes next.
- How does this relate to Huffman coding, and how would you build the code tree itself?
- What changes if the cost of a join is the longer of the two ropes instead of the sum?
- If the ropes arrive already sorted, can you avoid the heap with two queues, and what is the time?
- How would you recover the actual sequence of joins, not only the total?
- How would you prove that always joining the two shortest ropes is optimal?
Where candidates slip
The mistakes this problem punishes.
The most frequent slip is joining in the order given, or sorting once and joining neighbors in a single pass without feeding each joined rope back in. A merged rope can be shorter than the next unused rope, so it has to go back among the candidates.
Other mistakes: forgetting to push the joined rope back; adding the two lengths separately to the total instead of the joined length; using a max-heap by accident; and calling the default sort() on numbers, which compares them as text, so 10 sorts before 9. Re-sorting inside the loop passes small tests but is far too slow at 100,000 ropes. Finally, some implementations mutate the caller's array while popping.
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.