Minimum Cost of ropes

JavaView on GFG

Intuition

Greedy: always merge two smallest ropes. Use a min-heap. Total cost = sum of all intermediate merge costs.

Algorithm

1Add all lengths to min-heap.
2While heap size > 1: pop two smallest, merge cost = sum, push back. Add cost to total.

Common Pitfalls

•Same as Huffman encoding / minimum cost to combine. Greedy with min-heap gives optimal solution.

Minimum Cost of ropes.java

Java

// Approach: Greedy with min-heap. Always combine two smallest ropes. Total cost = sum of all intermediate sums.
// Time: O(n log n) Space: O(n)
import java.util.*;

class Solution {
    // Function to return the minimum cost of connecting the ropes.
    public long minCost(long[] arr) {
        PriorityQueue<Long> pq = new PriorityQueue<>();

        for (long val : arr)
            pq.add(val);

        long totalCost = 0;

        while (pq.size() > 1) {
            long first = pq.poll();
            long second = pq.poll();

            long cost = first + second;
            totalCost += cost;

            pq.add(cost);
        }

        return totalCost;
    }
}

// Version 2
class Solution1 {
    // Function to return the minimum cost of connecting the ropes.
    public long minCost(int[] arr) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        for (int val : arr)
            pq.add(val);

        long totalCost = 0;

        while (pq.size() > 1) {
            int first = pq.poll();
            int second = pq.poll();

            int cost = first + second;
            totalCost += cost;

            pq.add(cost);
        }

        return totalCost;
    }
}

Was this solution helpful?