Minimum Cost to Connect Sticks
Medium · Heap & Counting · Array · Greedy · Heap (Priority Queue)
Problem
You have sticks with positive integer lengths given in sticks. You can join any two sticks of lengths x and y into one stick of length x + y, paying x + y.
Keep joining until a single stick remains. Return the minimum total cost.
Examples
Input: sticks = [5,1,2] Output: 11
Join 1 and 2 for 3, then 3 and 5 for 8: 3 + 8 = 11.
Input: sticks = [1,1,1,1] Output: 8
Join pairs of 1s (2 + 2), then the two 2s (4): 8.
Input: sticks = [7] Output: 0
There is nothing to join, so the cost is 0.
Constraints
- 1 <= sticks.length <= 10^4
- 1 <= sticks[i] <= 10^4
Approaches
- Baseline: scan for the two shortest each time — time O(n²), space O(n)
Follow-up
This is Huffman coding in disguise: the joins form a binary tree, and each original stick is paid once per level of depth. The use cases ask for the total length of a Huffman encoding, and for the version where only neighboring sticks may be joined, where greedy fails and interval dynamic programming is needed.
Related problems
Start free on Cariara · Coding problems · System design studio
