Minimum Cost to Connect Sticks

Share

Given sticks[], the cost to connect two sticks is their sum. Find the minimum cost to connect all sticks into one.

Example 1
Input: [2,4,3] → Output: 14 (2+3=5, 5+4=9, total=14)
Example 2
Input: [1,8,3,5] → Output: 30

Solution Approach

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.
Java
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)