Solution: Minimum Cost to Connect Sticks

Statement

You are given a set of sticks with positive integer lengths represented as an array, sticks, where sticks[i] denotes the length of the $i^{th}$ stick.

You can connect any two sticks into one stick at a cost equal to the sum of their lengths. Once two sticks are combined, they form a new stick whose length is the sum of the two original sticks. This process continues until there is only one stick remaining.

Your task is to determine the minimum cost required to connect all the sticks into a single stick.

Constraints:

• $1 \leq$ sticks.length $\leq 10^3$

• $1 \leq$ sticks[i] $\leq 10^3$

Solution

This algorithm calculates the minimum cost to combine all sticks into one by repeatedly merging the two shortest sticks at each step. The idea is to minimize the cumulative merging cost by prioritizing smaller sticks earlier in the process. Merging smaller sticks earlier minimizes the cost since their combined length won’t contribute as much to future merges, ensuring an optimal solution. To achieve this efficiently, a min heap is utilized, enabling quick extraction of the smallest sticks and dynamically maintaining the current state of the remaining sticks.

At each step, the two shortest sticks are removed from the heap and merged, and their combined length is added back into the heap. This ensures that the heap always reflects the updated set of sticks for future merges. Additionally, the combined length of the two sticks is added to the total cost, incrementally tracking the overall cost of the merging process.

The steps of the algorithm are as follows:

1. Create a min heap from the input list of stick lengths using minHeap.add. A min heap allows efficient extraction of the two smallest elements.

2. Initialize a variable, totalCost, to 0 to track the cumulative cost of combining sticks.

3. Perform the below steps as long as there is more than one stick in the heap.

   1. Use minHeap.remove to remove and retrieve the two smallest sticks from the heap.

   2. Calculate the cost of combining the two sticks (first + second) and add this to totalCost.

   3. Insert the combined stick back into the heap using minHeap.add.

4. Once only one stick remains in the heap, the iterations end, and the totalCost is returned as the minimum cost of combining all sticks.

Let’s look at the following illustration to get a better understanding of the solution: