Minimum Cost to Connect Sticks — Huffman Coding with a Min-Heap

Problem Statement#

You have some number of sticks with positive integer lengths. These lengths are given as an array sticks, where sticks[i] is the length of the ith stick.

You can connect any two sticks of lengths x and y into one stick by paying a cost of x + y. You must connect all the sticks until there is only one remaining.

Return the minimum cost of connecting all the given sticks into one stick in this way.

Constraints:

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

Examples:

Input:  sticks = [2, 4, 3]
Output: 14
 
Explanation:
  Connect 2 and 3 → cost 5, sticks = [4, 5]
  Connect 4 and 5 → cost 9, sticks = [9]
  Total cost = 5 + 9 = 14

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

Input:  sticks = [5]
Output: 0
Explanation: Only one stick, nothing to connect.

Why This Problem Matters#

This problem is a direct implementation of the Huffman coding algorithm — one of the most important algorithms in information theory, used in PNG, ZIP, and MP3 compression. Amazon asks it frequently because it perfectly tests greedy algorithm reasoning: can you prove that always merging the two smallest elements yields the minimum total cost?

The greedy proof is elegant: consider any merge order. If two of the largest elements are merged first, their combined length contributes to every subsequent merge. By instead merging small elements first, you ensure that large values are added fewer times to the running cost. Formally, each element's contribution to total cost equals its value times the number of merges it participates in. Merging smallest first minimizes the number of times each large element is used.

This problem also illustrates the "optimal substructure" property: if you make the optimal first choice (merge the two smallest), the remaining problem is identical in structure. This recursive property is what makes greedy algorithms correct for this class of problems.

Beyond the algorithm itself, the clean one-pass min-heap implementation is a model of concise, correct code that interviewers love to see. It takes exactly 5-6 lines in Python and perfectly separates concerns: extract minimum twice, pay cost, push merged result.

The Core Insight#

Greedy choice: Always merge the two shortest sticks first.

Why this is optimal: Each merge operation adds its cost (a + b) to the total. The merged stick (a + b) will then participate in all future merges — adding (a + b) again to costs of those merges, and so on. Equivalently, each original stick contributes its length multiplied by the number of merges it is involved in (its depth in the merge tree). To minimize total cost, assign the deepest positions to the smallest values — exactly what Huffman coding does.

Implementation: Build a min-heap from all sticks. Repeat until one stick remains:

1. Pop the two smallest sticks a and b.
2. Pay cost a + b.
3. Push the merged stick a + b back into the heap.

sticks = [2, 4, 3]
Heap: [2, 3, 4]
 
Round 1: pop 2, pop 3 → cost += 5 → push 5 → heap=[4,5]
Round 2: pop 4, pop 5 → cost += 9 → push 9 → heap=[9]
 
Total cost = 14

Comparison with suboptimal order:

sticks = [2, 4, 3], merge largest first:
  pop 4, pop 3 → cost 7 → heap=[2,7]
  pop 2, pop 7 → cost 9 → heap=[9]
  Total = 7 + 9 = 16 > 14  (worse!)

Visual Dry Run#

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

Initial heap (min-heap): [1, 3, 5, 8]

Answer: 30

Note: The contribution of each original stick to the total:

• 1: participates in rounds 1,2,3 → contributes 1 * 3 = 3
• 3: participates in rounds 1,2,3 → contributes 3 * 3 = 9
• 5: participates in rounds 2,3 → contributes 5 * 2 = 10
• 8: participates in round 3 → contributes 8 * 1 = 8
• Total = 3 + 9 + 10 + 8 = 30 ✓

Smallest sticks (1 and 3) participate in more rounds but at lower cost — optimal.

Solution (Optimal)#

import heapq
 
def connectSticks(sticks: list[int]) -> int:
    if len(sticks) <= 1:
        return 0
 
    heapq.heapify(sticks)   # O(n) in-place heapification
    total_cost = 0
 
    while len(sticks) > 1:
        a = heapq.heappop(sticks)   # smallest stick
        b = heapq.heappop(sticks)   # second smallest stick
        merged = a + b
        total_cost += merged
        heapq.heappush(sticks, merged)
 
    return total_cost

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

Complexity Analysis:

Building the heap is O(n) using heapify. Each of the n-1 merge rounds does 2 pops and 1 push, each O(log n). Total: O(n) + O(n log n) = O(n log n).

Common Mistakes#

• Not returning 0 for a single stick. If len(sticks) == 1, there is nothing to connect and the cost is 0. The while loop condition len > 1 handles this naturally, but be explicit about the edge case.
• Adding the merged stick length instead of the cost. The cost is a + b (the operation cost), and you push a + b back. Both happen to be the same value, but conceptually separate "what you pay" from "what you create."
• Using a max-heap instead of min-heap. Merging the largest sticks first gives a higher total cost. Always use a min-heap.
• Calling heapify on sticks after each merge. heapq.heappush maintains the heap property after each insertion — no need to re-heapify.
• Integer overflow. With up to 10^4 sticks each up to 10^4, the merged stick can grow very large over many rounds. Python handles this automatically; in Java/C++, use long for total_cost.

Follow-up Questions#

• Why is the greedy proof correct? Each stick's contribution to total cost equals its length multiplied by the number of merge rounds it participates in (its depth in the merge tree). To minimize total cost, smaller sticks should be deeper (participate in more rounds). Huffman's greedy algorithm achieves this optimally.
• What if there are more than two sticks to merge at once? If you can merge m sticks simultaneously at cost equal to their total length, the greedy still works: always merge the m smallest. Use a min-heap, pop m elements, push their sum.
• What is the connection to Huffman coding? In Huffman coding, character frequencies are the "stick lengths," and the merge cost corresponds to the encoded file size. Minimum merge cost = minimum encoded file size = optimal prefix-free encoding.
• Can you solve this in O(n)? Only if the input is already sorted. Sort the sticks first, then use two queues (original elements and merged results) — each always processed in order, giving O(n) merges without a heap.
• What if some sticks have the same length? No issue — the algorithm handles duplicates naturally. Ties in the heap are resolved arbitrarily, and all valid orderings produce the same minimum cost.

Key Takeaways#

• Always merging the two shortest sticks first is provably optimal: each stick's contribution to total cost equals its length times its depth in the merge tree.
• Build a min-heap in O(n) using heapq.heapify; then run n-1 merge rounds each taking O(log n) — total O(n log n).
• This is Huffman coding: the same algorithm that compresses data in ZIP, PNG, and MP3 files.
• The min-heap size stays at most n throughout; space is O(n).
• With a pre-sorted input, two-queue trick achieves O(n) — a strong follow-up to mention in interviews.
• Amazon uses this problem to test greedy correctness reasoning, not just implementation — always explain the proof.
• Merging largest sticks first always yields a strictly worse result; exchange argument formalizes this.

Key Takeaways#

• Always merge the two smallest sticks first — this is the Huffman coding greedy, proven optimal
• Use a min-heap: pop the two smallest, push their sum, accumulate the cost; repeat until one stick remains
• Each element's contribution to total cost = its length * (number of merge rounds it participates in); smallest elements should participate in the most rounds
• Use heapify for O(n) initial heap construction, then O(log n) per push/pop
• Return 0 immediately if there is only one stick — no merges needed
• Time O(n log n), space O(n) — n-1 merge rounds, each with O(log n) heap operations
• This "pop two smallest, push merged, accumulate cost" pattern applies to any optimal binary merge problem