We use analytics and advertising cookies to understand how the site is used and whether our ads on Facebook and Instagram work. They are set only if you accept. See our Privacy Policy for details.
You have some sticks with positive integer lengths, 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 of length x + y at a cost of x + y. You must keep connecting until exactly one stick remains.
Return the minimum total cost of connecting all the sticks into one stick. If there are fewer than two sticks, the cost is 0.
A medium heap / priority queue problem, graded against 7 test cases (4 of them hidden).
A priority queue for "top k" and streaming-median questions.
Reach for it when you see: "Top/smallest k", a running median, or repeatedly needing the current minimum.
More Heap / Priority Queue problems →Every connection's cost is the sum of the two pieces, so a stick connected early gets its length counted in every later merge that contains it. To minimize total cost, always merge the two shortest sticks first - the same greedy argument as Huffman coding, and an exchange argument proves it optimal.
A min-heap supports the loop efficiently: pop the two smallest, add their sum to the total, push the sum back, until one stick remains. The reference solution hand-rolls a small array-based binary min-heap, so it needs no imports or libraries in either language.
The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.
Read off this problem's own test suite, so these are the cases a submission actually has to survive.
These apply to the pattern as a whole, not just this problem.