Minimum Cost to Connect Sticks
MediumAlways join the two shortest
Problem
Repeatedly connect two sticks at a cost equal to their combined length. Return the minimum total cost to connect all sticks into one.
Always fuse the two shortest sticks first (min-heap) so big lengths get added the fewest times.
The idea
Every join's cost is added again by each later join that includes it, so the shortest sticks must be combined earliest to be counted the most times. A min-heap gives the two smallest each round in O(n log n).
The trick
- Pop two, push their sum, add it to the total, repeat until one stick remains.
- The same greedy underlies Huffman coding.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — [2,4,3] Values: 2, 4, 3.
1min-heap of lengths2while size>1: a=pop; b=pop; cost+=a+b; push a+b3return costInput
- array
- [2, 4, 3]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- sticks = [2, 4, 3]
- Output:
- 14
- Explanation:
- Join 2+3=5, then 5+4=9 → cost 14.
Example 2
- Input:
- sticks = [1, 8, 3, 5]
- Output:
- 30
- Explanation:
- Greedy smallest-first joins → 30.
Example 3
- Input:
- sticks = [5]
- Output:
- 0
- Explanation:
- One stick → no cost.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.