You have some number of sticks with positive integer lengths. These lengths are given as an array sticks, where sticks[i] is the length of the ith stick.
You can connect any two sticks of lengths x and y into one stick by paying a cost of x + y. You must connect all the sticks until there is only one stick remaining.
Return the minimum cost of connecting all the given sticks into one stick in this way.
Example 1:
Input: sticks = [2,4,3] Output: 14 Explanation: You start with sticks = [2,4,3]. 1. Combine sticks 2 and 3 for a cost of 2 + 3 = 5. Now you have sticks = [5,4]. 2. Combine sticks 5 and 4 for a cost of 5 + 4 = 9. Now you have sticks = [9]. There is only one stick left, so you are done. The total cost is 5 + 9 = 14.
Example 2:
Input: sticks = [1,8,3,5] Output: 30 Explanation: You start with sticks = [1,8,3,5]. 1. Combine sticks 1 and 3 for a cost of 1 + 3 = 4. Now you have sticks = [4,8,5]. 2. Combine sticks 4 and 5 for a cost of 4 + 5 = 9. Now you have sticks = [9,8]. 3. Combine sticks 9 and 8 for a cost of 9 + 8 = 17. Now you have sticks = [17]. There is only one stick left, so you are done. The total cost is 4 + 9 + 17 = 30.
Example 3:
Input: sticks = [5] Output: 0 Explanation: There is only one stick, so you don't need to do anything. The total cost is 0.
Constraints:
1 <= sticks.length <= 1041 <= sticks[i] <= 104Problem Overview: You are given an array where each value represents the length of a stick. Connecting two sticks costs the sum of their lengths, and the resulting stick can be used again. The goal is to connect all sticks into one while minimizing the total cost.
Approach 1: Repeated Sorting (Greedy Simulation) (Time: O(n2 log n), Space: O(1) or O(n) depending on sorting)
The greedy idea is straightforward: always connect the two smallest sticks first because smaller merges produce lower accumulated cost. A simple implementation repeatedly sorts the array, removes the two smallest values, adds their sum to the total cost, and inserts the merged stick back into the list. This works because the greedy choice is locally optimal, but repeatedly sorting the array is expensive. Each iteration performs a sort, leading to poor performance as the list shrinks.
Approach 2: Greedy + Min Heap (Priority Queue) (Time: O(n log n), Space: O(n))
The optimal approach uses a min heap (priority queue) to efficiently retrieve the two smallest sticks at every step. First push all stick lengths into the heap. Then repeatedly pop the two smallest elements, add their sum to the total cost, and push the merged stick back into the heap. Each pop and push operation takes O(log n), so the entire process runs in O(n log n). This pattern is identical to the classic optimal merge pattern and Huffman-style greedy construction.
The correctness comes from a greedy insight: combining the smallest sticks early prevents large values from being added repeatedly in future merges. A heap guarantees that the smallest elements are always accessible in logarithmic time, which removes the expensive repeated sorting.
The input itself is simply an array of stick lengths, but the real optimization comes from choosing the right data structure to repeatedly access minimum elements.
Recommended for interviews: The Greedy + Min Heap approach is what interviewers expect. It demonstrates recognition of the optimal merge pattern and efficient use of a priority queue. Mentioning the naive repeated-sort method helps show the reasoning process, but implementing the heap-based solution proves strong algorithmic fundamentals.
We can use a greedy approach, each time choosing the shortest two sticks to connect, which ensures the minimum cost of connection.
Therefore, we can use a priority queue (min heap) to maintain the current stick lengths. Each time, we take out two sticks from the priority queue to connect, then put the connected stick back into the priority queue, until there is only one stick left in the priority queue.
The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the length of the array sticks.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Repeated Sorting (Greedy Simulation) | O(n² log n) | O(1)–O(n) | Conceptual understanding of the greedy rule; acceptable only for very small inputs |
| Greedy + Min Heap (Priority Queue) | O(n log n) | O(n) | Optimal approach for production code and coding interviews |
Minimum Cost to Connect Sticks • Kevin Naughton Jr. • 23,053 views views
Watch 9 more video solutions →Practice Minimum Cost to Connect Sticks with our built-in code editor and test cases.
Practice on FleetCode