How do you approach Minimum Cost to Connect Sticks?

A stick's length gets re-paid every time the combined stick it belongs to is connected again - which sticks should be combined earliest?

What is the time complexity of Minimum Cost to Connect Sticks?

Time complexity: O(n log n). Space complexity: O(n) for the heap.

What are common mistakes on Minimum Cost to Connect Sticks?

Using a max-heap for a k-largest question. The size-k min-heap is what turns O(n log n) into O(n log k). An inverted comparator, which is silent: the code runs and returns confidently wrong answers. Re-heapifying inside the loop instead of once up front.

gitGood.dev

← Back to problems

Minimum Cost to Connect Sticks

MediumData Structures

Description

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`.

Example 1

Input: sticks = [2,4,3]

Output: 14

Explanation: Connect 2 and 3 for a cost of 5 (sticks = [5,4]), then 5 and 4 for a cost of 9. Total = 14.

Example 2

Input: sticks = [1,8,3,5]

Output: 30

Explanation: 1+3=4, 4+5=9, 9+8=17. Total = 4 + 9 + 17 = 30.

Example 3

Input: sticks = [5]

Output: 0

Explanation: There is only one stick, so no connections are needed.

Constraints

- 0 <= sticks.length <= 10^4 - 1 <= sticks[i] <= 10^4

Minimum Cost to Connect Sticks: approach, complexity and pitfalls

A medium heap / priority queue problem, graded against 7 test cases (4 of them hidden).

The pattern: Heap / Priority Queue

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 Queueproblems →

If you are stuck

Show the 3-step hint ladder

A stick's length gets re-paid every time the combined stick it belongs to is connected again - which sticks should be combined earliest?
Greedy: always connect the two shortest sticks first, so the smallest lengths are the ones counted most often. This is exactly Huffman coding's merge step.
A min-heap gives you the two smallest in O(log n): pop two, add their sum to the cost, push the sum back. Repeat until one stick remains.

The optimal approach

Show the approach: Greedy + Min-Heap (Huffman Merging)

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.

Time: O(n log n)
Space: O(n) for the heap

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Empty input. At least one case passes an empty collection. Make sure your loop bounds and any "first element" read survive a length of zero.
Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.

Common Heap / Priority Queue mistakes

These apply to the pattern as a whole, not just this problem.

Using a max-heap for a k-largest question. The size-k min-heap is what turns O(n log n) into O(n log k).
An inverted comparator, which is silent: the code runs and returns confidently wrong answers.
Re-heapifying inside the loop instead of once up front.