FastPrep
Problem

Minimum Stick Connection Cost

AmazonFULLTIMEONSITE INTERVIEW
See Amazon hiring insights

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.

Examples
01 · 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.

02 · 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
  • sticks[i] is a positive integer.
More Amazon problems
drafts saved locally
public int minimumStickConnectionCost(int[] sticks) {
  // write your code here
}
sticks[2, 4, 3]
expected14
sign in to submit