Minimum Cost to Connect Sticks — Medium Problem & Solution

Problem statement

You have sticks of the given lengths. You may connect any two of them into one stick of the combined length, at a cost equal to that combined length.

Return the minimum total cost of connecting all the sticks into a single one.

Example 1

Input: sticks = [2,4,3]
Output: 14
Explanation: Join 2 and 3 for 5, then 5 and 4 for 9 — total 14.

Example 2

Input: sticks = [1,8,3,5]
Output: 30

Example 3

Input: sticks = [5]
Output: 0
Explanation: Nothing to connect.

Constraints

• 1 <= sticks.length <= 5000
• 1 <= sticks[i] <= 10^4

How to solve Minimum Cost to Connect Sticks

This is Huffman's construction. Each stick's length ends up multiplied by how many joins it is carried through, so the cheapest plan joins the two shortest sticks at every step.

Approach

1. Build a min-heap of the stick lengths.
2. While more than one stick remains, pop the two smallest, add their sum to the total, and push the sum back.
3. Return the accumulated total.

Why it works

The greedy choice is optimal by the usual exchange argument: in any optimal plan the two deepest sticks can be swapped for the two shortest without increasing the cost, so joining the shortest pair first is never wrong. A single stick costs nothing, which is why the loop condition is length > 1 rather than > 0.

Complexity

• Time — O(n log n)
• Space — O(n)

Pitfalls

• Sorting once and joining left to right is wrong — each new stick must re-enter the ordering.
• A single stick answers 0.
• The cost of a join is the combined length, counted again at every later join it feeds into.

Reference solution

Python

from typing import List
import heapq

def connectSticks(sticks: List[int]) -> int:
    heap = sticks[:]
    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

JavaScript

var connectSticks = function(sticks) {
    var heap = sticks.slice();
    var sift = function(j) {
        for (;;) {
            var l = 2 * j + 1, r = l + 1, s = j;
            if (l < heap.length && heap[l] < heap[s]) s = l;
            if (r < heap.length && heap[r] < heap[s]) s = r;
            if (s === j) break;
            var t = heap[s]; heap[s] = heap[j]; heap[j] = t;
            j = s;
        }
    };
    var push = function(v) {
        heap.push(v);
        var i = heap.length - 1;
        while (i > 0) {
            var p = (i - 1) >> 1;
            if (heap[p] <= heap[i]) break;
            var t = heap[p]; heap[p] = heap[i]; heap[i] = t;
            i = p;
        }
    };
    var pop = function() {
        var top = heap[0];
        var last = heap.pop();
        if (heap.length > 0) { heap[0] = last; sift(0); }
        return top;
    };
    for (var i = Math.floor(heap.length / 2) - 1; i >= 0; i--) sift(i);
    var total = 0;
    while (heap.length > 1) {
        var a = pop(), b = pop();
        total += a + b;
        push(a + b);
    }
    return total;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Minimum Number of Increments on Subarrays to Form a Target Array Medium
• Find the Winner of an Array Game Medium
• Queries on a Permutation With Key Medium
• Corporate Flight Bookings Medium
• Find the Winner of the Circular Game Medium
• Longest Subsequence With Limited Sum Medium