Minimum Cost To Connect Sticks - Leetcode Solution

Problem Statement

Given n sticks with their respective lengths, connect them to form a single stick with minimum possible cost. The cost of connecting any two sticks is equal to the sum of their lengths. Return the minimum possible cost to connect all the given sticks.

Solution

Approach:

We can solve this problem using a priority queue. First, we can add all the given sticks to the priority queue. After that, we can pick two sticks with the shortest lengths and add their sum to the answer variable. Next, we can add the sum of the two sticks back to the priority queue. We can repeat these steps until only one stick remains in the priority queue. The final value of the answer variable will be the minimum possible cost of connecting all the given sticks.

Algorithm:

1. Create a priority queue and insert all given sticks into it.
2. While the priority queue has more than one stick: a. Pop the shortest two sticks from the priority queue. b. Add their sum to the answer variable. c. Add the sum of the two sticks back to the priority queue.
3. Return the answer variable.

Code

Here is the implementation of the above algorithm in Python:

import heapq

def connectSticks(sticks):
    # create a priority queue and insert all given sticks into it
    heap = []
    for stick in sticks:
        heapq.heappush(heap, stick)
    
    # process sticks until only one stick remains in the priority queue
    ans = 0
    while len(heap) > 1:
        # pop the shortest two sticks from the priority queue
        stick1 = heapq.heappop(heap)
        stick2 = heapq.heappop(heap)
        
        # add their sum to the answer variable
        cost = stick1 + stick2
        ans += cost
        
        # add the sum of the two sticks back to the priority queue
        heapq.heappush(heap, cost)
    
    # return the answer variable
    return ans

Time Complexity:

The time complexity of this algorithm is O(n log n), where n is the number of sticks. We need to iterate over each stick once to insert it into the priority queue. After that, we need to remove and add sticks back to the priority queue n-1 times. Thus, the time complexity of removing and adding sticks to the priority queue is O(log n). Therefore, the overall time complexity of the algorithm is O(n log n).

1