Minimum Cost to Connect Sticks — Min-Heap Greedy

Problem

Connecting two sticks costs their sum. Find minimum total cost to connect all sticks into one.

Approach — Min-Heap (Huffman)

Always merge the two cheapest sticks. The cost is their sum; push merged stick back.

Time: O(n log n) | Space: O(n)

Solutions

Python

import heapq
class Solution:
    def connectSticks(self, sticks: list[int]) -> int:
        heapq.heapify(sticks); total=0
        while len(sticks)>1:
            a,b=heapq.heappop(sticks),heapq.heappop(sticks)
            total+=a+b; heapq.heappush(sticks,a+b)
        return total

Complexity

• Time: O(n log n) | Space: O(n)