Min Cost to Connect Ropes: Always Join the Two Shortest

Problem

You have ropes of given positive lengths. You may join any two ropes into one; doing so costs the sum of their two lengths, and the new rope’s length is that sum. Keep joining until one rope remains. Return the smallest possible total cost. This is GeeksforGeeks: Min Cost to Connect Ropes (also known as LeetCode 1167, which is subscription-only).

Examples

[4, 3, 2, 6]   ->  29   (2+3=5, 4+5=9, 6+9=15; 5 + 9 + 15)
[1, 1, 1, 1]   ->  8    (1+1, 1+1, 2+2)
[7]            ->  0    (nothing to join)
[5, 5]         ->  10

Approach 1: brute force (try every order)

Recursively try every pair to join next and keep the cheapest total. This is only useful to check the greedy on small inputs.

from functools import lru_cache

def min_cost_brute(ropes):
    @lru_cache(maxsize=None)
    def solve(state):
        if len(state) <= 1:
            return 0
        best = None
        items = list(state)
        for i in range(len(items)):
            for j in range(i + 1, len(items)):
                joined = items[i] + items[j]
                rest = items[:i] + items[i + 1:j] + items[j + 1:] + [joined]
                cost = joined + solve(tuple(sorted(rest)))
                if best is None or cost < best:
                    best = cost
        return best

    return solve(tuple(sorted(ropes)))

Complexity: exponential; memoising on the sorted multiset helps but does not change that.

Approach 2: optimal (greedy with a min-heap)

Every rope’s length is paid once for each join it takes part in, directly or as part of a bigger rope. So the total is the sum of each original length times its depth in the “join tree”. To keep the total low, the shortest ropes should be the deepest, which means joining the two shortest ropes first, then repeating on the new set. A min-heap gives the two shortest in O(log n) each time.

import heapq

def min_cost(ropes):
    heap = list(ropes)
    heapq.heapify(heap)
    total = 0
    while len(heap) > 1:
        a = heapq.heappop(heap)
        b = heapq.heappop(heap)
        total += a + b
        heapq.heappush(heap, a + b)
    return total

Why it is correct: take any optimal join tree and a pair of sibling ropes at its deepest level. Swapping the two shortest ropes into those two positions moves shorter lengths deeper and longer lengths shallower, which cannot increase the total, so some optimal tree joins the two shortest ropes first. Treating that joined rope as one new rope leaves a smaller problem of the same kind, and induction finishes the proof. It is the exchange argument behind Huffman coding.

Complexity: O(n log n) time (n − 1 joins, each a few heap operations), O(n) space.

Tests

import random

for f in (min_cost, min_cost_brute):
    assert f([4, 3, 2, 6]) == 29
    assert f([1, 1, 1, 1]) == 8
    assert f([7]) == 0
    assert f([]) == 0
    assert f([5, 5]) == 10
    assert f([1, 2, 3, 4, 5]) == 33

random.seed(2)
for _ in range(200):
    rs = [random.randint(1, 20) for _ in range(random.randint(0, 6))]
    assert min_cost(rs) == min_cost_brute(rs)

ropes = [3, 1, 2]
min_cost(ropes)
assert ropes == [3, 1, 2]   # input not mutated
print("ok")

Edge cases and pitfalls

• Copy the list before heapify if the caller still needs it; heapify rearranges in place.
• Joining in the given order, or always adding the next rope to one growing rope, is not optimal: [4, 3, 2, 6] in order costs 7 + 9 + 15 = 31, against 29 for the greedy.
• Totals can exceed 32-bit integers in languages with fixed-width ints; Python is safe, but say so in a Java or C++ answer.
• Zero or one rope costs nothing.

Where this shows up in data engineering

This is the cost model of merging sorted runs or small files: merging two files costs roughly the bytes read and written, and merged output is merged again later. Compaction planners therefore merge the smallest files first, which is the same greedy. It is also why a k-way merge of many runs at once beats a chain of pairwise merges, a point worth raising when the interviewer asks about external sorting.