Minimum Cost of ropes

The problem, simply

You get n ropes with different lengths. You can tie two ropes into one. Tying costs the sum of their lengths: tying a 2 and a 3 costs 5 and makes a rope of 5. Keep tying until one rope is left.

Give back the smallest total cost.

A story to remember it

Picture it

Examples

Way 1: the simple way

Do the same greedy steps, but find the two shortest ropes by looking at every rope each time.

1. Keep the ropes in a list.
2. While more than one rope is left: scan the list for the shortest and the second shortest, remove them, add their sum to the cost, and put the joined rope back.

import java.util.*;

class Solution {
    public long minCost(int[] ropes) {
        List<Long> left = new ArrayList<>();
        for (int r : ropes) left.add((long) r);
        long cost = 0;
        while (left.size() > 1) {
            int a = 0, b = 1;                        // a: shortest, b: second shortest
            if (left.get(b) < left.get(a)) { a = 1; b = 0; }
            for (int i = 2; i < left.size(); i++) {
                if (left.get(i) < left.get(a)) { b = a; a = i; }
                else if (left.get(i) < left.get(b)) b = i;
            }
            long joined = left.get(a) + left.get(b);
            cost += joined;
            left.remove(Math.max(a, b));             // remove the later index first
            left.remove(Math.min(a, b));
            left.add(joined);
        }
        return cost;
    }
}

How long it takes: n - 1 knots, and each one scans the list, so O(n^2). Extra room: the list, O(n).

Way 2: the clever way

Keep the ropes in a min-heap: a small tree where every parent is no longer than its children, stored in an array. The shortest rope is always on top. Taking the top or adding a rope only moves things along one branch, which is log n steps.

1. Put every rope into the min-heap.
2. While the heap has more than one rope: take the top two, add their sum to the cost, and push the joined rope back.
3. The cost is the answer.

Why the shortest first? Draw the knots as a tree. Each rope is counted once for every knot above it, so a rope deep in the tree is paid for many times. The two shortest ropes should be the deepest, and tying them first puts them there.

import java.util.PriorityQueue;

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

How long it takes: n pushes to start, then n - 1 rounds of two pops and one push, each O(log n). Total O(n log n). Extra room: the heap, O(n).

Watch out for

• Use long. With 100,000 ropes of length a million, the total cost is far past the int limit.
• One rope costs 0, and zero ropes cost 0. The loop handles both.
• PriorityQueue in Java is a min-heap by default. For a max-heap you would pass Collections.reverseOrder(), which is wrong here.

What interviewers ask next

• Why is it optimal? This is the same as building a Huffman code: the cost is each length times its depth in the knot tree, and an exchange argument shows the two smallest should be siblings at the bottom.
• Can you beat O(n log n)? If the ropes come sorted, use two queues: one for the original ropes and one for joined ropes. Joined ropes come out in growing order, so the two smallest are always at the front of one of the queues. That is O(n).
• What if you may tie three ropes at a time? Take the three shortest each time. If (n - 1) is not a multiple of 2, add ropes of length 0 first so the last knot is full.
• Merging sorted files: merging two files costs their total size. The cheapest order to merge many files is the same problem.

Remember this

Grown-up words: the pile with the shortest on top is a min-heap or priority queue, the knot tree is a Huffman tree, and paying for a rope once per knot above it is the weighted path length.