Minimum Cost to Connect Sticks

January 23, 2024

Problem Statement #

You have some sticks with positive integer lengths. You can connect any two sticks of lengths X and Y into one stick by paying a cost of X + Y. You must connect all the sticks until there is only one stick remaining. Return the minimum cost to connect all the given sticks into one stick in this way.

Example:

1. Input: sticks = [2, 4, 3] Output: 14 Explanation: You start with sticks = [2,4,3]. 1st step: Combine 2 and 3 (cost: 5), new sticks = [5,4] 2nd step: Combine 5 and 4 (cost: 9), new sticks = [9] Total cost = 5 + 9 = 14.

Solution Approach #

The solution involves using a min heap to always combine the smallest two sticks first, ensuring the minimum cost.

Algorithm Steps #

1. Create a min heap from the list of sticks.
2. While there are more than one stick in the heap, do the following: a. Pop the two smallest sticks from the heap. b. Calculate the cost of combining them and add the cost to the total. c. Push the combined stick back into the heap.
3. Return the total cost.

Code (Python) #

import heapq

def connectSticks(sticks):
    heapq.heapify(sticks)
    total_cost = 0

    while len(sticks) > 1:
        cost = heapq.heappop(sticks) + heapq.heappop(sticks)
        total_cost += cost
        heapq.heappush(sticks, cost)

    return total_cost

# Test the function
print(connectSticks([2, 4, 3]))  # Output: 14

Time Complexity #

O(n log n), where n is the number of sticks. The heap operations contribute to the log n factor.

Space Complexity #

O(n), for the heap.