Minimum Cost to Connect Sticks
Problem
You have sticks with positive integer lengths. You can connect any two sticks into one for a cost equal to the sum of their lengths. Return the minimum total cost of connecting all sticks into a single stick.
sticks = [2, 4, 3]14import heapq
def connect_sticks(sticks):
heapq.heapify(sticks)
cost = 0
while len(sticks) > 1:
a = heapq.heappop(sticks)
b = heapq.heappop(sticks)
cost += a + b
heapq.heappush(sticks, a + b)
return costfunction connectSticks(sticks) {
const h = new MinHeap(sticks);
let cost = 0;
while (h.size() > 1) {
const a = h.pop();
const b = h.pop();
cost += a + b;
h.push(a + b);
}
return cost;
}class Solution {
public int connectSticks(int[] sticks) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int s : sticks) pq.offer(s);
int cost = 0;
while (pq.size() > 1) {
int a = pq.poll();
int b = pq.poll();
cost += a + b;
pq.offer(a + b);
}
return cost;
}
}int connectSticks(vector<int>& sticks) {
priority_queue<int, vector<int>, greater<int>> pq(sticks.begin(), sticks.end());
int cost = 0;
while ((int)pq.size() > 1) {
int a = pq.top(); pq.pop();
int b = pq.top(); pq.pop();
cost += a + b;
pq.push(a + b);
}
return cost;
}Explanation
Every time we connect two sticks, the cost is their combined length, and that combined stick gets reused in later connections. To keep total cost low, we should always join the two shortest sticks available — a classic Huffman-style greedy.
Why the two shortest? Because a stick's length is counted again in every future merge it takes part in. Smaller sticks get merged first, so the big lengths are added to the total fewer times.
A min-heap makes this easy: its root is the shortest stick. We repeatedly pop the two smallest, add their sum to cost, and push the sum back as a new stick. We continue until only one stick remains.
Example: sticks=[2,4,3]. Pop 2 and 3 → cost 5, push 5 (heap is [4,5]). Pop 4 and 5 → cost 9, total 5 + 9 = 14. The answer is 14.
Each merge does a couple of heap operations costing log n, so the whole process is efficient even with many sticks.