FastPrep
Problem · Heap

Connect N Ropes With Minimum Cost

Learn this problem
● MediumInMobi logoInMobiNEW GRADOA

Problem statement

You are given an integer array ropes, where ropes[i] is the length of one rope.

In one operation, choose any two ropes, connect them into one rope, and pay a cost equal to the sum of their lengths. The new rope has that same combined length.

Return the minimum total cost required to connect all ropes into one rope. If there is only one rope, return 0.

Function

minimumRopeConnectionCost(ropes: int[]) → long

Examples

Example 1

ropes = [4,3,2,6]return = 29

Connect lengths 2 and 3 for cost 5, then 4 and 5 for cost 9, and finally 6 and 9 for cost 15. The total is 5 + 9 + 15 = 29.

Example 2

ropes = [4,2,7,6,9]return = 62

One optimal sequence has merge costs 6, 12, 16, and 28, for a total of 62.

Example 3

ropes = [10]return = 0

Only one rope is present, so no connection operation is needed.

Constraints

  • 1 <= ropes.length <= 10^5
  • 1 <= ropes[i] <= 10^4
  • The result fits in a signed 64-bit integer.

More InMobi problems

drafts saved locally
public long minimumRopeConnectionCost(int[] ropes) {
  // write your code here.
}
ropes[4,3,2,6]
expected29
checking account