Minimum Cost to Connect Sticks — Huffman Greedy with Min-Heap

Problem Statement#

You have sticks with positive integer lengths given in array sticks. You can connect any two sticks of lengths x and y into one stick by paying a cost of x + y. Return the minimum cost of connecting all sticks into one.

Constraints:

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

Input:  sticks = [2, 4, 3]
Output: 14
Explanation: Connect 2+3=5 (cost 5). Connect 4+5=9 (cost 9). Total=14.

Input:  sticks = [1, 8, 3, 5]
Output: 30
Explanation: Connect 1+3=4 (cost 4). Connect 4+5=9 (cost 9). Connect 8+9=17 (cost 17). Total=30.

Why This Problem Matters#

This problem is a direct application of Huffman coding, one of the most famous algorithms in information theory and data compression. The connection is exact: in Huffman coding, you always merge the two least-frequent symbols first. Here, you always merge the two shortest sticks first. Both minimize the total weighted cost.

Amazon frequently asks this problem because it models logistics and package merging scenarios. Google uses it to test whether candidates recognize the Huffman pattern and implement it efficiently with a priority queue. The exchange argument proving the greedy correct is also a common interviewer follow-up.

The key property: merging cheaper elements first keeps them out of future (more expensive) merges, reducing the total accumulation of re-merged values.

The Core Insight#

The cost of merging sticks is amplified by future merges. A stick created early will be merged again, so its value is counted multiple times. The optimal strategy minimizes this amplification by always combining the two cheapest sticks.

Exchange argument: Suppose an optimal solution first merges sticks A and B (not the smallest pair), where C and D are the two smallest. Swapping to merge C+D first, then A+B: intermediate merged sticks are smaller, reducing all future merge costs. This proves the greedy is globally optimal.

Algorithm: Use a min-heap. Repeatedly extract the two smallest sticks, merge them (pay their sum), push the merged stick back. Continue until one stick remains.

Visual Dry Run#

sticks = [2, 4, 3] → heapified: [2, 3, 4]

Total = 14. Compare: merging 2+4=6 first gives 6+9=15 — worse.

sticks = [1, 8, 3, 5] → heapified: [1, 3, 5, 8]

Total = 30.

Solution (Optimal)#

import heapq
 
class Solution:
    def connectSticks(self, sticks: list[int]) -> int:
        heapq.heapify(sticks)
        total_cost = 0
 
        while len(sticks) > 1:
            first = heapq.heappop(sticks)
            second = heapq.heappop(sticks)
            merged = first + second
            total_cost += merged
            heapq.heappush(sticks, merged)
 
        return total_cost

var connectSticks = function(sticks) {
    class MinHeap {
        constructor(arr) {
            this.heap = [...arr];
            for (let i = Math.floor(this.heap.length / 2) - 1; i >= 0; i--) {
                this._siftDown(i);
            }
        }
        _siftDown(i) {
            const n = this.heap.length;
            while (true) {
                let smallest = i;
                const l = 2 * i + 1, r = 2 * i + 2;
                if (l < n && this.heap[l] < this.heap[smallest]) smallest = l;
                if (r < n && this.heap[r] < this.heap[smallest]) smallest = r;
                if (smallest === i) break;
                [this.heap[i], this.heap[smallest]] = [this.heap[smallest], this.heap[i]];
                i = smallest;
            }
        }
        _siftUp(i) {
            while (i > 0) {
                const p = Math.floor((i - 1) / 2);
                if (this.heap[p] <= this.heap[i]) break;
                [this.heap[i], this.heap[p]] = [this.heap[p], this.heap[i]];
                i = p;
            }
        }
        pop() {
            const min = this.heap[0];
            const last = this.heap.pop();
            if (this.heap.length > 0) { this.heap[0] = last; this._siftDown(0); }
            return min;
        }
        push(val) { this.heap.push(val); this._siftUp(this.heap.length - 1); }
        size() { return this.heap.length; }
    }
 
    const heap = new MinHeap(sticks);
    let totalCost = 0;
 
    while (heap.size() > 1) {
        const merged = heap.pop() + heap.pop();
        totalCost += merged;
        heap.push(merged);
    }
 
    return totalCost;
};

Time: O(n log n) — n-1 merges, each involving two O(log n) heap operations Space: O(n) — heap stores all sticks

Common Mistakes#

• Sorting once and iterating without a heap — after each merge, the new stick may belong anywhere in the sorted order; a heap maintains dynamic order
• Not pushing the merged stick back — the new stick must re-enter the pool for future merges; omitting this gives a wrong answer
• Accumulating the merge cost incorrectly — cost of each merge is the sum of both sticks merged, not just one
• Using a max-heap instead of min-heap — Python's heapq is a min-heap; to make a max-heap, negate values; using max-heap here gives the maximum cost, not minimum

Interview Tips#

• Lead with the Huffman connection: "This is the Huffman coding greedy — always merge the two cheapest elements first. I can prove this is optimal with an exchange argument: if we don't merge the two cheapest first, swapping those merges cannot increase the total cost."
• Prove the greedy when asked: "Merging smaller values first keeps them out of future merges. Larger values merged later appear in fewer total merges, reducing their overall contribution to the sum."
• Mention the two-queue O(n log n) alternative: sort once, then use two queues (one for original sticks, one for merged results). The front of the smaller queue is always the next smallest element without re-sorting.

Follow-up Questions#

• How does this relate to Huffman coding? Identical algorithm. In Huffman coding, each merge combines two character nodes with cost = sum of frequencies. Optimal prefix codes are built by always merging the two lowest-frequency nodes first.
• Is the greedy provably optimal? Yes — by exchange argument. Suppose optimal does not merge the two smallest first. Swapping to merge them first cannot increase cost (smaller intermediate values reduce all future merge costs). By induction, greedy is optimal.
• What if there is a fixed cost added to every merge regardless of stick length? Total additional cost is (n-1) * fixed_cost (always n-1 merges). Add this to the greedy result for the variable part.
• Can you solve this without a heap in O(n log n)? Yes: sort once, then maintain two queues (one for sorted original sticks, one for merged sticks in FIFO order). The minimum is always the front of the smaller queue.

Key Takeaways#

• Always merge the two cheapest sticks first — this is the Huffman greedy and is provably optimal by exchange argument.
• Use a min-heap to dynamically maintain the smallest available stick after each merge.
• There are always exactly n-1 merges to go from n sticks to 1 — total operations are O(n log n).
• The cost of each merge is the sum of both sticks merged; accumulate this across all n-1 merges.
• This pattern generalizes to any "repeatedly merge the two smallest elements" problem — also see Last Stone Weight (LC 1046, max-heap variant).
• The two-queue technique achieves the same O(n log n) time with a simpler structure when the input is already sorted.
• JavaScript has no built-in min-heap — either implement one or explain the PriorityQueue equivalent to the interviewer.