Pattern visualizer

Minimum Cost to Connect Sticks

Every stick's length gets added to the running cost once for every merge it takes part in AFTER it is created. A stick combined early sits inside the pile through more later merges, so it must be a SHORT one — the two shortest sticks available should always be connected next. A min-heap keeps the two shortest on top with no scanning: pop twice, connect, push the sum back in, repeat. Animated on: Sticks = [2, 4, 3]. Repeatedly connect any two sticks for a cost equal to their summed length, until one stick remains. Return the minimum total cost..

Always merge the two shortest sticks first

time O(n log n)space O(n)step 1 / 8

line 2

Push the first stick, 4. One node, so it is trivially the root.

Pseudocode

1FUNCTION minCostConnectSticks(sticks):
2  heap <- BUILD MIN-HEAP FROM sticks
3  cost <- 0
4  WHILE LENGTH(heap) > 1
5    a <- EXTRACT-MIN(heap)
6    b <- EXTRACT-MIN(heap)
7    cost <- cost + a + b
8    INSERT (a + b) INTO heap
9  RETURN cost

← / → step · space play · Home restart

Where to practice Heap

Practice Heap problems All Heap problems Back to roadmap