FastPrep
Problem

Minimum Stick Connection Cost

Learn this problem
Amazon logoAmazonFULLTIMEONSITE INTERVIEW
See Amazon hiring insights

Problem statement

You are given an integer array sticks, where each element is the length of a stick.

You may connect any two sticks with lengths x and y. The new stick has length x + y, and the cost of this operation is also x + y.

Return the minimum total cost required to connect all sticks into one stick.

Function

minimumStickConnectionCost(sticks: int[]) → int

Examples

Example 1

sticks = [2, 4, 3]return = 14

Connect 2 and 3 for cost 5, then connect 5 and 4 for cost 9. The total cost is 14.

Example 2

sticks = [1, 8, 3, 5]return = 30

One optimal sequence is 1 + 3 = 4, then 4 + 5 = 9, then 8 + 9 = 17, for total cost 4 + 9 + 17 = 30.

Constraints

  • 1 <= sticks.length <= 104
  • 1 <= sticks[i] <= 104

More Amazon problems

drafts saved locally
public int minimumStickConnectionCost(int[] sticks) {
  // write your code here
}
sticks[2, 4, 3]
expected14
checking account