Minimum Cost to Connect Sticks

Problem

Connecting two sticks of lengths x and y costs x+y. Return minimum total cost to connect all sticks into one.

Key insight (Greedy): Huffman coding pattern. Always merge the two shortest sticks. Use min-heap.

Solutions

// C — min-heap

// C++
int connectSticks(vector<int>& sticks) {
    priority_queue<int, vector<int>, greater<int>> minH(sticks.begin(), sticks.end());
    int cost = 0;
    while (minH.size() > 1) {
        int a = minH.top(); minH.pop();
        int b = minH.top(); minH.pop();
        cost += a + b;
        minH.push(a + b);
    }
    return cost;
}

// Java
public int connectSticks(int[] sticks) {
    PriorityQueue<Integer> minH = new PriorityQueue<>();
    for (int s : sticks) minH.offer(s);
    int cost = 0;
    while (minH.size() > 1) {
        int a = minH.poll(), b = minH.poll();
        cost += a + b;
        minH.offer(a + b);
    }
    return cost;
}

// JavaScript
function connectSticks(sticks) {
    sticks.sort((a, b) => a - b);
    let cost = 0;
    while (sticks.length > 1) {
        const a = sticks.shift(), b = sticks.shift();
        const merged = a + b;
        cost += merged;
        let pos = sticks.findIndex(x => x >= merged);
        if (pos === -1) sticks.push(merged);
        else sticks.splice(pos, 0, merged);
    }
    return cost;
}

# Python
import heapq

def connectSticks(sticks):
    heapq.heapify(sticks)
    cost = 0
    while len(sticks) > 1:
        a = heapq.heappop(sticks)
        b = heapq.heappop(sticks)
        cost += a + b
        heapq.heappush(sticks, a + b)
    return cost

Complexity

Time: O(n log n)
Space: O(n)

Key Insight

This is Huffman coding / optimal merge pattern. Each stick's length contributes to cost once for each merge it participates in. Merging shortest first minimizes total contributions.