Q72: Minimum Cost to Connect Sticks. - DSA Patterns (Multi-Lang)

In Simple Words: Huffman Coding greedy pattern: Min-Heap of stick lengths. Repeatedly extract the two shortest sticks, sum them, add to total cost, and push sum back into heap.

Time: $O(N \log N)$ | Space: $O(N)$

Multi-Language SolutionsPython 3 • JavaScript • TypeScript • Java • C++

Switch tabs or choose All

import heapq

def connectSticks(sticks: list[int]) -> int:
    heapq.heapify(sticks)
    total_cost = 0
    while len(sticks) > 1:
        cost = heapq.heappop(sticks) + heapq.heappop(sticks)
        total_cost += cost
        heapq.heappush(sticks, cost)
    return total_cost