Given sticks[], the cost to connect two sticks is their sum. Find the minimum cost to connect all sticks into one.
Input: [2,4,3] → Output: 14 (2+3=5, 5+4=9, total=14)Input: [1,8,3,5] → Output: 30
This is the Huffman encoding approach. Always merge the two smallest sticks. Use a min-heap.
- Add all sticks to a min-heap.
- While heap.size() > 1: pop two smallest, add their sum to cost, push sum back.
- Return total cost.
import java.util.*;
class Solution {
public int connectSticks(int[] sticks) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int s : sticks) minHeap.offer(s);
int cost = 0;
while (minHeap.size() > 1) {
int merged = minHeap.poll() + minHeap.poll();
cost += merged;
minHeap.offer(merged);
}
return cost;
}
}
- Time Complexity: O(N log N)
- Space Complexity: O(N)