Minimum Cost to Connect Sticks
Understanding the Problem
We have a collection of sticks and we need to keep combining two at a time until only one remains. Every time we combine two sticks of lengths x and y, we pay x + y. The question is: in what order should we combine them to minimize the total cost?
When two sticks are combined early, their length gets absorbed into the merged stick, and that merged stick participates in future combinations. A stick merged early contributes its length to many subsequent costs, while a stick merged late contributes to only a few. So the shortest sticks should be merged first, because whatever is merged first is counted the most times in the running total, and we want the small values in that position, not the large ones.
This is the same structure as Huffman coding, which always merges the two least-frequent nodes first to build an optimal prefix-free code. Here we always merge the two shortest sticks first to minimize total cost.
Key Constraints:
1 <= sticks.length <= 10^4: With n up to 10,000, an O(n^2 log n) solution that re-sorts after every merge is borderline, while an O(n log n) heap-based solution is comfortable.1 <= sticks[i] <= 10^4: The maximum total cost stays under 2^31, so a 32-bit signed integer holds the answer without overflow. With at most 10^4 sticks of length 10^4, every intermediate merged value is also well withinintrange.
Approach 1: Sort and Merge Repeatedly
Intuition
To always pick the two smallest sticks, sort the array, take the first two elements, merge them, put the result back, and sort again. This combines the two shortest sticks at every step, which is the greedy choice that minimizes total cost.
A small example shows why picking the two smallest is correct. Take sticks [1, 2, 5]. Merging 1 and 2 first (cost 3) gives [3, 5], then merging those (cost 8) totals 11. Merging 2 and 5 first (cost 7) gives [1, 7], then merging those (cost 8) totals 15. The shorter sticks participate in more merges, so merging them first keeps the running total lower.
Algorithm
- Sort the sticks array in ascending order.
- While more than one stick remains, take the two smallest sticks (the first two elements after sorting), compute their combined length, add the cost to the total, and put the combined stick back into the array.
- Re-sort the array after each insertion.
- Return the total cost.
Visualization and Code
Loading animation...
- Time Complexity: O(n^2 log n). We perform n-1 merge operations. Each merge involves sorting the remaining sticks, which costs O(k log k) where k is the current number of sticks.
- Space Complexity: O(n). We use a list to store the sticks.
This approach is correct but re-sorts the entire array after every merge, even though only one element changed. The next approach replaces the repeated full sort with a data structure that maintains order incrementally: a min-heap, which extracts the minimum and inserts a new element in O(log n) each.
Approach 2: Min-Heap (Optimal)
Intuition
Instead of re-sorting after every merge, we use a min-heap (priority queue). A min-heap keeps the smallest element at the top and supports both extraction and insertion in O(log n) time. The operation we repeat maps onto it directly: take the two smallest sticks (two extract-min operations), merge them, and put the result back (one insert operation).
The greedy logic stays the same. We always merge the two shortest sticks; the heap makes the "find and remove the two shortest" step efficient.
The merges form a binary tree: the original sticks are leaves, each merge is an internal node, and the final stick is the root. The total cost equals the sum over all original sticks of each stick's length times its depth in this tree, because a stick at depth d is folded into d separate merge costs as its value bubbles up to the root.
Minimizing total cost is therefore the same problem as building a Huffman tree. To make the weighted sum of depths smallest, the largest values must sit closest to the root (smallest depth). Merging the two smallest sticks at each step places the smallest values deepest and pushes larger values toward the root, which is the Huffman construction and is provably optimal.
Algorithm
- Build a min-heap from all stick lengths.
- Initialize
totalCost = 0. - While the heap has more than one element, extract the two smallest values, compute their sum, add it to
totalCost, and insert the sum back into the heap. - Return
totalCost.
Visualization and Code
Loading animation...
- Time Complexity: O(n log n). Building the heap takes O(n). We perform n-1 merge operations, each involving two extract-min operations and one insert, each costing O(log n). Total: O(n) + O(n log n) = O(n log n).
- Space Complexity: O(n). The heap stores all n stick lengths.