Minimum Cost to Connect Sticks

How it works

When combining two sticks, the cost equals the sum of their lengths, and that combined stick may be used in future combinations. Sticks combined early contribute their length to multiple subsequent operations. To minimize total cost, we should combine the smallest sticks first so that larger values are added fewer times. A min-heap lets us efficiently retrieve and combine the two smallest sticks at each step.

Steps

1. Build a min-heap from all stick lengths.
2. While more than one stick remains:
   • Pop the two smallest sticks.
   • Combine them (sum their lengths).
   • Add the combination cost to the total.
   • Push the new stick back into the heap.
3. Return the total cost.

Complexity

• Time complexity: O(N log N)
• Space complexity: O(N)

Where N is the length of the input array.

Things to watch for

Using a Max-Heap Instead of a Min-Heap

The greedy strategy requires always combining the two smallest sticks first. Using a max-heap retrieves the largest elements, which leads to suboptimal costs because larger values get added multiple times in subsequent operations.

Forgetting to Push the Combined Stick Back

After popping two sticks and combining them, the new stick must be pushed back into the heap. Forgetting this step results in losing track of the combined stick, causing incorrect total cost calculations and potentially an infinite loop or early termination.

Not Handling the Single Stick Edge Case

When the input contains only one stick, no combinations are needed, and the cost should be 0. Failing to handle this edge case may cause attempts to pop from an empty heap or return an incorrect non-zero result.

from typing import List
import heapq

class Solution:
    def connectSticks(self, sticks: List[int]) -> int:
        min_heap = sticks
        heapq.heapify(min_heap)
        total_cost = 0

        while len(min_heap) > 1:
            new_stick = heapq.heappop(min_heap) + heapq.heappop(min_heap)
            total_cost += new_stick
            heapq.heappush(min_heap, new_stick)

        return total_cost

class Solution {
public:
    int connectSticks(vector<int>& sticks) {
        int totalCost = 0;

        priority_queue<int, vector<int>, greater<int>> pq;

        for (int i = 0; i < sticks.size(); i++) {
            pq.push(sticks[i]);
        }

        // combine two of the smallest sticks until we are left with just one.
        while (pq.size() > 1) {
            int stick1 = pq.top();
            pq.pop();
            int stick2 = pq.top();
            pq.pop();

            int cost = stick1 + stick2;
            totalCost += cost;

            pq.push(stick1+stick2);
        }

        return totalCost;
    }
};