Minimum Cost to Connect Sticks

Find the minimum cost to combine all sticks using a priority queue.

heap priority queue greedy optimization

You are given a list of positive integers `sticks` representing the lengths of sticks. You can connect any two sticks at a time, paying a cost equal to the sum of their lengths. After connecting, you get a new stick with that length. The process continues until there is exactly one stick. Return the minimum total cost to connect all sticks into one stick.

Implement the function `minimum_cost_to_connect_sticks(sticks: list[int]) -> int`.

- You must repeatedly combine two sticks with the smallest current lengths to achieve the minimum total cost.
- If `sticks` is empty or contains one stick, the cost is `0`.

**Constraints:**
- `0 <= len(sticks) <= 10^4`
- `1 <= sticks[i] <= 10^4`
- The total cost will fit within a 32-bit integer.

Constraints

0 ≤ len(sticks) ≤ 10^4; 1 ≤ sticks[i] ≤ 10^4. Total cost fits in 32-bit int. Aim for O(n log n) time.

Example

>>> minimum_cost_to_connect_sticks([2, 4, 3])
14
>>> minimum_cost_to_connect_sticks([1, 2, 3, 4])
19
>>> minimum_cost_to_connect_sticks([])
0
>>> minimum_cost_to_connect_sticks([5])
0

25 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Why is it always optimal to combine the two smallest sticks? Think about how the cost accumulates.

Use a min-heap to repeatedly extract the two smallest sticks and insert their sum back.

The total cost is the sum of each stick's length multiplied by how many times it is merged; the two smallest should be merged earliest.

Handle empty and single-element lists by returning 0 immediately.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.