Minimum Cost to Connect Sticks

Share

Connect all sticks into one. Cost to connect two sticks equals their sum. Minimize total cost.

Example 1
Input: sticks=[2,4,3] → Output: 14. Connect 2+3=5 (cost 5), then 5+4=9 (cost 9). Total=14.
Example 2
Input: sticks=[1,8,3,5] → Output: 30

Solution Approach

Use a min-heap. Always combine the two smallest sticks to minimize cost.

  • Add all sticks to a min-heap
  • While heap has more than 1 element
  • Poll two smallest sticks, compute sum
  • Add sum back to heap, add to total cost
  • Return total cost
Java
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 sum = pq.poll() + pq.poll();
        cost += sum;
        pq.offer(sum);
    }
    return cost;
}
  • Time Complexity: O(n log n)
  • Space Complexity: O(n)