Watch 10 video solutions for Minimum Cost to Connect Sticks, a medium level problem involving Array, Greedy, Heap (Priority Queue). This walkthrough by Kevin Naughton Jr. has 23,053 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |