Cheapest way to join ropes into one

Heaps and priority queues Mid-level Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
import heapq
ropes = [4, 3, 2, 6]
heapq.heapify(ropes)
cost = 0
while len(ropes) > 1:
    joined = heapq.heappop(ropes) + heapq.heappop(ropes)
    cost += joined
    heapq.heappush(ropes, joined)
print(cost)

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A 29

Right: 2+3 = 5, then 4+5 = 9, then 6+9 = 15; 5 + 9 + 15 = 29.

Short ropes are counted in every later join, so putting them in first keeps the repeated part small.

Why not the others?
  • B 15. That counts only the last join.
  • C 34. Joining in the given order costs more.

30-second answer

Always join the two shortest ropes. Short ropes then take part in the most joins, which is what keeps the total low (the same argument as Huffman coding). A min-heap gives the two shortest in O(log n): O(n log n) total, with O(n) space for the heap.

Practise saying it · 45 s. No recording, just a timer

Explain the rope-joining greedy.

Say your answer out loud, then check which of these points you covered:

  • Join the two shortest
  • Exchange argument
  • O(n log n)

Deep dive

The exchange argument: swapping a longer rope into an earlier join never lowers the cost.

One rope or none costs 0.

The brute force tries every pairing, which grows faster than factorially.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
from heapq import heapify, heappop, heappush


def join_cost(ropes: list[int]) -> int:
    pile = list(ropes)
    heapify(pile)
    total = 0
    while len(pile) > 1:
        joined = heappop(pile) + heappop(pile)  # the two shortest
        total += joined
        heappush(pile, joined)
    return total

Common mistakes

  • Joining in the given order.
  • Sorting once and joining left to right, which ignores that the new rope may not be the shortest.

Senior take & follow-ups

Name the exchange argument; it is how you prove a greedy choice.

Follow-up questions

Think of your answer first, then open the hint.

  1. Where else does this greedy appear?

    Show hint

    Huffman coding, and merging sorted files with the fewest total moves.

  2. Why not sort once?

    Show hint

    Each join creates a new length that must be placed among the rest; a heap does that in O(log n).

What each operation costs: Min Heap · Max Heap · Heap Operations · Priority Queue

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.