Show problems as
Classic problem #1167MediumArrayGreedyHeap (Priority Queue)

Minimum Cost to Connect Sticks

Real-world version: Joining Every Rod Into One
Tracked in this browser only
Read Minimum Cost to Connect Sticks on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A pile of rods has the lengths rods. Joining two rods costs their two lengths added together and leaves a single rod of that length in their place.

Join rods until only one remains. Return the smallest total cost.

Examples

Example 1

Input
rods = [1, 2, 3, 4]
Output
19

Joining 1 and 2 costs three, joining that with 3 costs six, and joining that with 4 costs ten, nineteen in all. Any other order charges the short rods more times over.

Example 2

Input
rods = [1, 1]
Output
2

One join of the two rods, charging their two lengths.

Example 3

Input
rods = [1, 2, 4, 8, 16]
Output
56

Each join takes the two shortest rods left, so the four joins cost three, seven, fifteen and thirty-one.

Constraints

  • 1 <= rods.length <= 10^4
  • 1 <= rods[i] <= 10^4

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def connect_sticks(rods: list[int]) -> int:
Java
public int connectSticks(int[] rods)

More on the same topics