DSA problem
Minimum Cost to Connect Sticks
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 i-th 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 stick remaining. Return the minimum cost of connecting all the given sticks into one stick in this way.
This is the classic Huffman-coding construction: at every step we should combine the two smallest sticks, because their lengths will be counted into the cost again with each subsequent merge. Merging long sticks early would force their weight to be added repeatedly during later merges, inflating the total.
A min-heap encodes the "always pick the two smallest" rule with O(log n) operations. Build the heap once in O(n), then perform n - 1 merge rounds: pop the two smallest values, add them to a running cost, and push their sum back onto the heap so it can participate in future merges.
The algorithm runs in O(n log n) time and O(n) space. The greedy choice is provably optimal because every merge step contributes x + y to the cost AND determines what value re-enters the heap; always picking the cheapest two guarantees that each stick's length is summed the minimum possible number of times in the final total.
Examples
sticks = [2,4,3]14sticks = [1,8,3,5]30sticks = [5]0Constraints
- 1 <= sticks.length <= 10^4
- 1 <= sticks[i] <= 10^4
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.