Connect n ropes with minimum cost

The problem, simply

You get n ropes with different lengths. You can tie two ropes into one. Tying costs as much as the length of the new rope, so tying a 2 and a 3 costs 5. Keep tying until one rope is left. Find the smallest total cost.

For ropes [4, 3, 2, 6] the answer is 29.

A story to remember it

Picture it

Examples

Way 1: the simple way

Do the greedy idea with a plain list. Each round, walk the whole list to find the two shortest ropes, tie them, and put the new rope back.

1. While more than one rope is left:
2. Scan the list for the shortest and second shortest rope.
3. Remove both, add their sum to the cost, and add the new rope to the list.

import java.util.ArrayList;
import java.util.List;

class Solution {
    public long minCost(int[] ropes) {
        List<Long> list = new ArrayList<>();
        for (int r : ropes) list.add((long) r);
        long total = 0;
        while (list.size() > 1) {
            long a = removeShortest(list);   // walks the whole list
            long b = removeShortest(list);
            total += a + b;
            list.add(a + b);
        }
        return total;
    }

    private long removeShortest(List<Long> list) {
        int best = 0;
        for (int i = 1; i < list.size(); i++) {
            if (list.get(i) < list.get(best)) best = i;
        }
        long v = list.get(best);
        list.set(best, list.get(list.size() - 1));  // fill the hole with the last one
        list.remove(list.size() - 1);
        return v;
    }
}

How long it takes: there are n - 1 rounds and each scans up to n ropes, so O(n^2). Extra room: the list, O(n).

Way 2: the clever way

Keep the ropes in a min heap, so the shortest rope is always on top and grabbing it takes only log n steps.

1. Put every rope length into a min heap.
2. While the heap holds more than one rope:
   • Poll the shortest, a. Poll the next shortest, b.
   • Add a + b to the total cost.
   • Offer the new rope a + b back into the heap.
3. Return the total.

import java.util.PriorityQueue;

class Solution {
    public long minCost(int[] ropes) {
        PriorityQueue<Long> basket = new PriorityQueue<>();  // min heap
        for (int r : ropes) basket.offer((long) r);
        long total = 0;
        while (basket.size() > 1) {
            long a = basket.poll();          // shortest
            long b = basket.poll();          // next shortest
            total += a + b;                  // pay for the new rope
            basket.offer(a + b);             // the new rope goes back in
        }
        return total;
    }
}

How long it takes: n - 1 rounds, each with two polls and one offer at O(log n), so O(n log n). Extra room: the heap, O(n).

Why shortest first is right

Draw the knots as a tree. Each rope ends up as a leaf, and a rope is paid for once for every knot above it. So the total cost is each rope length times its depth in the tree.

The two shortest ropes should be the deepest leaves. If a longer rope sat deeper than a shorter one, swapping them would lower the cost. Tying the two shortest first puts them deepest, and the same argument repeats on the smaller problem. This is the same proof as Huffman coding.

Watch out for

• One rope or an empty list costs 0. The size() > 1 loop handles both.
• Do not assume the new rope is always tied next. With [5, 5, 6, 6], the two 6s go before the 10.
• Sorting once at the start is not enough. New ropes must be placed back in order, which is what the heap does.
• The cost of the last knot is the sum of all ropes. Do not forget to count it.

What interviewers ask next

• Prove that shortest first is optimal. Use the knot tree: cost is length times depth, so the shortest ropes belong deepest, and swapping can only help. It is Huffman's argument.
• Can you do it faster if the ropes come sorted? Yes, with two queues: one for the original sorted ropes and one for the new ropes, which are created in increasing order. Always take the smaller front. That is O(n) after sorting.
• What if you may tie three ropes at once? Same greedy with the three shortest. If (n - 1) is not divisible by 2, add zero length ropes first so every knot has three.
• Merge files with minimum cost, or Huffman codes? Same problem with different names.

Remember this

Grown-up words: the basket is a min heap (priority queue), always tying the two shortest is a greedy choice, the knot tree is a Huffman tree, and paying once per knot above a rope is the weighted depth of a leaf.