604. Minimum Cost to Connect Sticks
You have a pile of sticks, described by an array sticks where sticks[i] is the length of the i-th stick. You want to weld them all into one single stick.
Welding works on exactly two sticks at a time: pick any two, pay a cost equal to the sum of their lengths, and they fuse into one new stick of that combined length (which goes back into the pile and can be welded again).
Given sticks, return the minimum total cost to end up with one stick. If the pile already contains just one stick, no welding is needed and the cost is 0.
Example 1:
Input: sticks = [2, 4, 3]
Output: 14
Explanation: Weld 2 and 3 first (cost 5, pile becomes [5, 4]), then weld 5 and 4 (cost 9). Total 5 + 9 = 14. Starting with 2 + 4 = 6 instead leads to 6 + 9 = 15, which is worse.
Example 2:
Input: sticks = [1, 8, 3, 5]
Output: 30
Explanation: Weld 1 + 3 = 4 (pile [4, 5, 8]), then 4 + 5 = 9 (pile [9, 8]), then 9 + 8 = 17. Total 4 + 9 + 17 = 30, and no other order does better.
Constraints:
- 1 ≤ sticks.length ≤ 10⁴
- 1 ≤ sticks[i] ≤ 10⁴
Hints:
Every weld's cost gets carried forward: a stick welded early is part of every later sum it participates in. So short sticks should be merged early (they get re-counted often) and long sticks late.
Greedy: always weld the two currently shortest sticks. This is exactly how Huffman coding builds its tree.
A min-heap gives you the two smallest in O(log n) per weld: pop two, push their sum, add the sum to the total, repeat until one stick remains.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: sticks = [2, 4, 3]
Expected output: 14