Connect N Ropes with Minimum Cost

 Given are N ropes of different lengths, the task is to connect these ropes into one rope with minimum cost, such that the cost to connect two ropes is equal to the sum of their lengths.

Input: arr[] = {4,3,2,6} , N = 4

Output: 29

Explanation:

First, connect ropes of lengths 2 and 3. Now we have three ropes of lengths 4, 6, and 5.

Now connect ropes of lengths 4 and 5. Now we have two ropes of lengths 6 and 9.

Finally connect the two ropes and all ropes have connected.

Input: arr[] = {1, 2, 3} , N = 3

Output: 9

Constraints:

N == arr.length

0 <= N <= 10^4

1 <= arr[i].length <= 10^4

🔄 Step-by-step Dry Run:

Initial ropes: [4, 3, 2, 6]

1. Pick 2 smallest ropes → 2 + 3 = 5 → cost = 5 → add back → [4, 5, 6]

2. Pick 2 smallest → 4 + 5 = 9 → cost = 9 → add back → [6, 9]

3. Pick 2 smallest → 6 + 9 = 15 → cost = 15 → final rope

🧮 Total Cost = 5 + 9 + 15 = 29

 Why Use Min-Heap (PriorityQueue)?

To always get the smallest 2 ropes in O(log N) time.

import java.util.PriorityQueue;

public class MinCostOfRopes {

    public static int minCost(int[] ropes) {

        // Min Heap to store rope lengths

        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        // Add all ropes to minHeap

        for (int rope : ropes) {

            minHeap.add(rope);

        }

        int totalCost = 0;

        // Keep combining ropes until one remains

        while (minHeap.size() > 1) {

            int first = minHeap.poll();   // smallest rope

            int second = minHeap.poll();  // second smallest

            int cost = first + second;

            totalCost += cost;

            // Add the combined rope back to heap

            minHeap.add(cost);

        }

        return totalCost;

    }

    public static void main(String[] args) {

        int[] ropes = {4, 3, 2, 6};

        System.out.println("Minimum cost to connect ropes: " + minCost(ropes));

    }

}