DSA Tracker

Visualize

Minimum Cost to Connect Sticks

Always merge the two shortest sticks first

time O(n log n)space O(n)

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.

Details

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.

Problem:Minimum Cost to Connect SticksMedium

Always merge the two shortest sticks first

step 1 / 8

4

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

Every step in words

Show all 8 steps
  1. Push the first stick, 4. One node, so it is trivially the root.
  2. Push 2. It is smaller than the current root 4, so it sifts up and takes the root spot — heap = [2, 4].
  3. Push 3. 3 is bigger than root 2, so the min-heap property already holds — heap = [2, 4, 3].
  4. Round 1: extract the smallest stick, 2. The last element slides into the root and sifts down, so the heap stays valid — heap = [3, 4].
  5. Extract the next smallest, 3. Connecting 2 and 3 costs 5 — running total is 5. Push 5 back into the heap so it can be combined again later — heap = [4, 5].
  6. Round 2: extract the smallest stick, 4. The last element slides into the root and sifts down, so the heap stays valid — heap = [5].
  7. Extract the last other stick, 5. Connecting 4 and 5 costs 9 — running total is 14. Push 9 back in; only one stick remains, so the process stops.
  8. minCostConnectSticks([2, 4, 3]) = 14 — connect 2 and 3 first (cost 5), then merge that with 4 (cost 9); 5 + 9 = 14, matching the example.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Minimum Cost to Connect Sticks in the editorAll Heap problemsBack to roadmap