26. Minimum Cost of Ropes
✅ GFG solution to the Minimum Cost of Ropes problem: find minimum total cost to connect all ropes using greedy approach with min-heap. 🚀
The problem can be found at the following link: 🔗 Question Link
🧩 Problem Description
You are given an array arr[] of rope lengths. Your task is to connect all ropes into a single rope with the minimum total cost. The cost to connect two ropes is equal to the sum of their lengths.
The goal is to find the optimal order of connecting ropes to minimize the total cost of all connections.
📘 Examples
Example 1
Input: arr[] = [4, 3, 2, 6]
Output: 29
Explanation: First connect 2 and 3 to get [4, 5, 6] with a cost of 5, then connect 4 and 5
to get [9, 6] with a cost of 9, and finally connect 9 and 6 to get one rope with a cost of 15,
giving a total minimum cost of 29.Example 2
Input: arr[] = [4, 2, 7, 6, 9]
Output: 62
Explanation: First, connect ropes 4 and 2, which makes the array [6, 7, 6, 9]. Cost = 6.
Next, add ropes 6 and 6, which results in [12, 7, 9]. Cost = 12.
Then, add 7 and 9, which makes the array [12, 16]. Cost = 16.
Finally, add these two which gives [28]. Cost = 28.
Total cost = 6 + 12 + 16 + 28 = 62.Example 3
Input: arr[] = [10]
Output: 0
Explanation: Since there is only one rope, no connections are needed, so the cost is 0.🔒 Constraints
$1 \le \text{arr.size()} \le 10^5$
$1 \le \text{arr}[i] \le 10^4$
✅ My Approach
The optimal approach uses a Greedy Algorithm with a Min-Heap (Priority Queue) to efficiently select and combine the smallest ropes:
Greedy Min-Heap Strategy
Initialize Min-Heap:
Insert all rope lengths into a min-heap (priority queue).
This allows us to extract the two smallest ropes in O(log n) time.
Greedy Selection:
Always extract the two smallest ropes from the heap.
This ensures minimum cost at each step (greedy choice property).
Combine and Update:
Calculate cost as the sum of the two smallest ropes.
Add this cost to the total result.
Push the combined rope length back into the heap.
Repeat Until One Rope:
Continue the process until only one rope remains in the heap.
The accumulated cost represents the minimum total cost.
Why Greedy Works:
Combining smallest ropes first minimizes the number of times larger ropes are added.
Each rope contributes to the cost based on how many times it's involved in combinations.
This follows the optimal substructure property of Huffman coding.
📝 Time and Auxiliary Space Complexity
Expected Time Complexity: O(n log n), where n is the number of ropes. Building the heap takes O(n), and we perform n-1 extract-min and insert operations, each taking O(log n) time.
Expected Auxiliary Space Complexity: O(n), as we store all rope lengths in the priority queue (min-heap).
🧑💻 Code (C)
void heapify(int arr[], int n, int i) {
int smallest = i, l = 2 * i + 1, r = 2 * i + 2;
if (l < n && arr[l] < arr[smallest]) smallest = l;
if (r < n && arr[r] < arr[smallest]) smallest = r;
if (smallest != i) {
int temp = arr[i];
arr[i] = arr[smallest];
arr[smallest] = temp;
heapify(arr, n, smallest);
}
}
int minCost(int arr[], int n) {
for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i);
int res = 0, size = n;
while (size > 1) {
int first = arr[0];
arr[0] = arr[size - 1];
size--;
heapify(arr, size, 0);
int second = arr[0];
arr[0] = arr[size - 1];
size--;
heapify(arr, size, 0);
int sum = first + second;
res += sum;
arr[size] = sum;
size++;
heapify(arr, size, 0);
}
return res;
}🧑💻 Code (C++)
class Solution {
public:
int minCost(vector<int>& arr) {
priority_queue<int, vector<int>, greater<int>> pq(arr.begin(), arr.end());
int res = 0;
while (pq.size() > 1) {
int first = pq.top(); pq.pop();
int second = pq.top(); pq.pop();
res += first + second;
pq.push(first + second);
}
return res;
}
};☕ Code (Java)
class Solution {
public static int minCost(int[] arr) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int x : arr) pq.add(x);
int res = 0;
while (pq.size() > 1) {
int sum = pq.poll() + pq.poll();
res += sum;
pq.add(sum);
}
return res;
}
}🐍 Code (Python)
import heapq
class Solution:
def minCost(self, arr):
heapq.heapify(arr)
res = 0
while len(arr) > 1:
sum_val = heapq.heappop(arr) + heapq.heappop(arr)
res += sum_val
heapq.heappush(arr, sum_val)
return res🧠 Contribution and Support
For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: 📬 Any Questions?. Let's make this learning journey more collaborative!
⭐ If you find this helpful, please give this repository a star! ⭐
📍Visitor Count
Last updated