174. Minimum Cost to Join Sticks
Minimum Cost to Join Sticks
You are given a list of sticks, where each stick has a positive integer length.
You may repeatedly choose any two sticks and join them into one new stick. If the chosen sticks have lengths x and y, then the new stick has length x + y, and the cost paid for this operation is also x + y.
You must continue joining sticks until exactly one stick remains.
Your task is to return the minimum total cost required to join all sticks into one stick.
Method Signature
Minimum Cost
int joinSticks(List<Integer> sticks)
sticks contains the lengths of all sticks.- Each value in
sticks is a positive integer.
- The method returns the minimum total cost needed to combine all sticks into one stick.
Input Format
sticks: A List<Integer> containing stick lengths.
Output Format
- Return an integer representing the minimum total cost to join all sticks.
Constraints
1 ≤ sticks.size() ≤ 1041 ≤ sticks.get(i) ≤ 104
Examples
Example 1
Method call: joinSticks(sticks = [5, 2, 4])
Output: 17
Explanation: Connect sticks of lengths 2 and 4, paying 6. The sticks become [5, 6]. Then join 5 and 6, paying 11. The total cost is 6 + 11 = 17.
Example 2
Method call: joinSticks(sticks = [6, 1, 2, 7])
Output: 28
Explanation: Connect sticks of lengths 1 and 2, paying 3. The sticks become [3, 6, 7]. Then join 3 and 6, paying 9. The sticks become [7, 9]. Finally join 7 and 9, paying 16. The total cost is 3 + 9 + 16 = 28.
Example 3
Method call: joinSticks(sticks = [10])
Output: 0
Explanation: There is already only one stick, so no join operation is needed.