MediumNeetCode150ArrayGreedyHeap (Priority Queue)
Minimum Cost to Connect Sticks
Connect all sticks with minimum cost.
Examples
Input
sticks = [2,4,3]
Output
14
Merge 2+3=5 cost 5, merge 5+4=9 cost 9. Total 14.
Constraints
- •
1 <= sticks.length <= 10^4 - •
1 <= sticks[i] <= 10^4
Approaches
Sort, merge smallest two.
CodeT: O(n^2 log n) | S: O(n) sorted array
Heapify and merge.
CodeT: O(n log n) | S: O(n) heap
import heapq
def connectSticks(sticks):
heapq.heapify(sticks); cost=0
while len(sticks)>1:
a=heapq.heappop(sticks); b=heapq.heappop(sticks)
cost+=a+b; heapq.heappush(sticks,a+b)
return costSame approach.
CodeT: O(n log n) | S: O(n)
Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Sort and Merge | O(n^2 log n) | O(n) sorted array | Sort, merge smallest two. |
| Min Heap | O(n log n) | O(n) heap | Heapify and merge. |
| Min Heap Optimized | O(n log n) | O(n) | Same approach. |
Sort and Merge
T: O(n^2 log n)S: O(n) sorted array
Sort, merge smallest two.
Min Heap
T: O(n log n)S: O(n) heap
Heapify and merge.
Min Heap Optimized
T: O(n log n)S: O(n)
Same approach.
Common Mistakes
Not using heap for efficiency
Wrong cost calculation
Off-by-one