Approach Summary
Min-heap: always combine the two cheapest sticks. The combined cost is the total cost. Greedy proof: merging smaller first is always optimal.
How to Recognize This Pattern
- "Minimum cost to combine all elements pairwise"
- Huffman coding pattern — always merge two smallest
Complexity Analysis
Time Complexity
O(n log n)
Space Complexity
O(n)
Tags
Array Greedy Heap