📚 Minimum Cost to Connect Sticks – Java Cheat Sheet

📌 What Is It?

The problem involves connecting a set of sticks into one stick. The cost of connecting two sticks is equal to the sum of their lengths. The goal is to minimize the total cost of connecting all the sticks.

To solve this efficiently, we use a min-heap to always connect the two smallest sticks first, minimizing the cost at each step.

🧱 Pattern Template

class Solution {
    public int connectSticks(int[] sticks) {
        // Step 1: Add all sticks to a min-heap
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int stick : sticks) {
            minHeap.offer(stick);
        }

        int totalCost = 0;

        // Step 2: Combine sticks until only one stick remains
        while (minHeap.size() > 1) {
            int stick1 = minHeap.poll(); // Smallest stick
            int stick2 = minHeap.poll(); // Second smallest stick
            int cost = stick1 + stick2; // Cost to combine them
            totalCost += cost;
            minHeap.offer(cost); // Add the combined stick back to the heap
        }

        return totalCost;
    }
}

📊 Time Complexity

Heap Initialization: O(n log n) – Adding all sticks to the heap.
Heap Operations: O(n log n) – Combining sticks involves n-1 heap operations.
Overall Complexity: O(n log n).

✅ Use Cases

Minimizing costs in resource allocation problems
Efficiently combining elements with a cost function
Applications in Huffman coding and data compression

📘 Common LeetCode Problems

1167. Minimum Cost to Connect Sticks [Medium] Heap

🧪 Example: Minimum Cost to Connect Sticks

Input: sticks = [2, 4, 3]
Output: 14

Explanation:
- Combine sticks 2 and 3 for a cost of 5. Sticks = [5, 4].
- Combine sticks 5 and 4 for a cost of 9. Sticks = [9].
- Total cost = 5 + 9 = 14.

💡 Pro Tips

Always combine the two smallest sticks to minimize the cost.
Edge cases: single stick (cost is 0), all sticks of the same length.
Use a min-heap to efficiently retrieve the smallest sticks.