Topics › Heaps › Hard Problems

Minimum Cost to Connect Sticks

Medium TUF ID 755 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You have sticks with positive integer lengths. You may join any two sticks of lengths x and y into one stick of length x + y, and that join costs x + y. Keep joining until a single stick remains. Return the minimum possible total cost. The same problem is often called “Minimum Cost of Ropes”.

Constraints: 1 ≤ sticks.length ≤ 10^4, 1 ≤ sticks[i] ≤ 10^4. The answer can come close to the int limit at these sizes, and it exceeds it in the rope version with larger lengths, so the code returns a long.

Example 1

sticks = [2, 4, 3]
answer = 14              // 2 + 3 = 5 (cost 5), then 5 + 4 = 9 (cost 9)

Example 2

sticks = [1, 8, 3, 5]
answer = 30              // 1 + 3 = 4, 4 + 5 = 9, 9 + 8 = 17; 4 + 9 + 17 = 30

Example 3

sticks = [5]
answer = 0               // already one stick, nothing to pay

Why “always join the two shortest” is right

Write the joins as a tree: the original sticks are leaves, and each join is an internal node. A stick’s length is paid once for every join it takes part in, which is its depth in that tree. So

total cost = sum over original sticks of (length × depth)

To make that small, long sticks should be shallow and short sticks deep. The deepest pair of leaves are siblings, joined in the very first step, so the cheapest plan joins the two shortest sticks first. The exchange argument behind this: if a longer stick sat deeper than a shorter one, swapping them would not increase the sum, so some optimal tree has the two shortest sticks as deepest siblings. After that first join, the new stick is just another stick, and the same argument applies to the smaller problem.

This is exactly Huffman coding, with stick lengths in place of character frequencies. Plausible alternatives lose. Joining left to right on [1, 8, 3, 5] costs 9 + 12 + 17 = 38, because the 8 gets dragged through every join.

All three approaches apply the same greedy. They differ in how they find the two shortest sticks.

Approach 1: Brute force, scan for the minimum

Intuition. Keep the sticks in a list. Each round, scan the list twice to remove the two smallest values, add their sum to the cost, and put the joined stick back.

Algorithm.

1. Copy the lengths into a list of Long.
2. While more than one stick remains: remove the minimum (a), remove the minimum again (b), add a + b to cost, and append a + b.
3. Return cost.

static long bruteForce(int[] sticks) {
    List<Long> pile = new ArrayList<>();
    for (int s : sticks) pile.add((long) s);
    long cost = 0;
    while (pile.size() > 1) {
        long a = removeMin(pile), b = removeMin(pile);
        cost += a + b;
        pile.add(a + b);
    }
    return cost;
}

static long removeMin(List<Long> pile) {
    int best = 0;
    for (int i = 1; i < pile.size(); i++) {
        if (pile.get(i) < pile.get(best)) best = i;
    }
    return pile.remove(best);                // remove(int index) returns the removed Long
}

Complexity. Time O(n^2): there are n - 1 rounds, and each scans and shifts a list of up to n items. Space O(n).

For 10^4 sticks that is around 10^8 element visits. It might pass, but the scan is doing far more work than needed to find two minimums.

Approach 2: Optimal, min-heap

Intuition. “Repeatedly remove the two smallest and insert one new value” is exactly what a min-heap does well. poll gives the smallest in O(log n), and add inserts in O(log n).

Algorithm.

1. Push every length into a min-heap of Long.
2. While the heap has at least two elements: poll a, poll b, add a + b to cost, push a + b.
3. Return cost.

static long minHeap(int[] sticks) {
    PriorityQueue<Long> pq = new PriorityQueue<>();
    for (int s : sticks) pq.add((long) s);
    long cost = 0;
    while (pq.size() > 1) {
        long a = pq.poll(), b = pq.poll();
        cost += a + b;
        pq.add(a + b);
    }
    return cost;
}

Dry run on [1, 8, 3, 5]:

One stick of length 17 remains, and the answer is 30.

Complexity. Time O(n log n): n - 1 rounds of three heap operations each, plus building the heap. Space O(n).

This is the standard answer, and it is what to write in an interview.

Approach 3: Optimal alternative, sort once and merge two queues

Intuition. There is a neat fact about this greedy: the joined sticks are created in non-decreasing order of length. Suppose one round joins x ≤ y, the two shortest sticks at that moment. Every stick left over is at least y, and the new stick x + y is also at least y (lengths are positive). So the next round joins two sticks that are each at least y, and their sum is at least y + y ≥ x + y.

That means we never need a heap. Keep two queues, both sorted:

• a: the original sticks, sorted once at the start.
• merged: the joined sticks, in creation order, which is already sorted.

The shortest available stick is at the front of one of these two queues, so each pick is one comparison, like the merge step of merge sort. Both queues are plain arrays with moving indices.

Algorithm.

1. Sort a copy a of the lengths. Create merged of size n, with head = tail = 0, and an index i = 0 into a.
2. Repeat n - 1 times: take two sticks, each time from a[i] if merged is empty or a[i] <= merged[head], otherwise from merged[head]. Add their sum to cost and append it at merged[tail++].
3. Return cost.

static long twoQueues(int[] sticks) {
    int n = sticks.length;
    int[] a = sticks.clone();
    Arrays.sort(a);
    long[] merged = new long[n];             // joined sticks; created in non-decreasing order
    int i = 0, head = 0, tail = 0;           // a[i..] unused originals, merged[head..tail) unused joins
    long cost = 0;
    for (int step = 1; step < n; step++) {
        long sum = 0;
        for (int pick = 0; pick < 2; pick++) {
            if (head == tail || (i < n && a[i] <= merged[head])) sum += a[i++];
            else sum += merged[head++];
        }
        cost += sum;
        merged[tail++] = sum;
    }
    return cost;
}

Dry run on [1, 8, 3, 5], so a = [1, 3, 5, 8]:

The cost is 4 + 9 + 17 = 30, the same as the heap.

Complexity. Time O(n log n) for the sort, then O(n) for all the joins. If the input is already sorted, or is sorted with counting sort (lengths are at most 10^4), the whole thing is linear. Space O(n).

Edge cases and pitfalls

• One stick or none. No join happens, so the cost is 0. All three loops run zero times.
• Overflow. Four sticks of length 10^9 cost 2·10^9 + 2·10^9 + 4·10^9 = 8·10^9, which does not fit in an int. The heap and list store Long, and the costs are summed in a long. The Java tests include exactly this case.
• Pushing the joined stick back. The joined stick is a real stick that must be joined again later. Forgetting to re-insert it gives the sum of only the first-level joins.
• Sorting once is not enough without the second queue. After sorting, “join neighbours left to right” is wrong: [3, 3, 3, 3] left to right costs 6 + 9 + 12 = 27, but joining in pairs costs 6 + 6 + 12 = 24.
• Ties between equal lengths can be broken either way. In the two-queue method, preferring the original stick on a tie is only a convention.
• List.remove on a List<Long> removes by index when given an int, which is what removeMin wants. With a List<Integer> the same call would be easy to misread as removing a value.

Related problems

• Shortest Job First uses the same “small items are counted many times, so handle them first” argument.
• Kth smallest element in an array is a simpler warm-up for a heap that serves the smallest items.
• Implement Min Heap explains the poll and add operations this solution leans on.
• Merge K sorted Lists uses the same “smallest of the fronts” step as the two-queue method.
• Task Scheduler is another greedy that a heap drives.