Minimum Cost to Connect Sticks

Minimum Cost to Connect Sticks

What is this problem about?

The Minimum Cost to Connect Sticks problem gives you several sticks of different lengths. You can connect two sticks into one by paying a cost equal to the sum of their lengths. You repeat this until only one stick remains. The goal is to find the minimum total cost to connect all the sticks.

Why is this asked in interviews?

This is a classic Minimum Cost to Connect Sticks interview question at Amazon and J.P. Morgan. It is the same underlying problem as Huffman Coding. It tests if a candidate understands that to minimize the total sum, the smallest values should be combined as many times as possible (i.e., they should be deeper in the "combination tree").

Algorithmic pattern used

The Greedy with Heap (Priority Queue) interview pattern is the optimal solution.

1. Put all stick lengths into a Min-Heap.
2. While more than one stick remains:
   • Extract the two smallest sticks a and b.
   • The cost to connect them is a + b.
   • Add this cost to the total.
   • Push the new stick of length a + b back into the heap.
3. The final total is the minimum cost.

Example explanation

Sticks: [2, 4, 3].

1. Min-Heap: [2, 3, 4].
2. Connect 2 and 3: Cost = 5. New heap: [4, 5]. Total cost = 5.
3. Connect 4 and 5: Cost = 9. New heap: [9]. Total cost = 5 + 9 = 14. If we connected 4 and 3 first (7), then 7 and 2 (9), the total would be 7 + 9 = 16, which is higher.

Common mistakes candidates make

• Sorting once and using a loop: Thinking that you can just sort and combine in order. This fails because the new combined stick might be smaller than some other existing sticks and should be combined sooner.
• Using a Max-Heap: This would combine the largest sticks first, leading to the maximum possible cost.
• Not using a Heap: Trying to re-sort the array after every connection, which makes the algorithm $O(N^2 \log N)$ instead of $O(N \log N)$.

Interview preparation tip

Whenever you have a problem that involves "repeatedly combining the two smallest/largest elements," immediately think of a Priority Queue. This is the standard way to maintain a sorted set of elements where values are constantly changing.