You have some number of sticks with positive integer lengths. These lengths are given as an array sticks, where sticks[i] is the length of the ith stick.
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 of connecting 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]. 1. Combine sticks 2 and 3 for a cost of 2 + 3 = 5. Now you have sticks = [5,4]. 2. Combine sticks 5 and 4 for a cost of 5 + 4 = 9. Now you have sticks = [9]. There is only one stick left, so you are done. The total cost is 5 + 9 = 14.
Example 2:
Input: sticks = [1,8,3,5] Output: 30 Explanation: You start with sticks = [1,8,3,5]. 1. Combine sticks 1 and 3 for a cost of 1 + 3 = 4. Now you have sticks = [4,8,5]. 2. Combine sticks 4 and 5 for a cost of 4 + 5 = 9. Now you have sticks = [9,8]. 3. Combine sticks 9 and 8 for a cost of 9 + 8 = 17. Now you have sticks = [17]. There is only one stick left, so you are done. The total cost is 4 + 9 + 17 = 30.
Example 3:
Input: sticks = [5] Output: 0 Explanation: There is only one stick, so you don't need to do anything. The total cost is 0.
Constraints:
1 <= sticks.length <= 10^41 <= sticks[i] <= 10^4
The description was taken from https://leetcode.com/problems/minimum-cost-to-connect-sticks.
#O(N(Log(N))) Time, O(N) Spaceclass Solution:
def connectSticks(self, sticks: List[int]) -> int:
cost = 0
heap = []
for stick in sticks:
heapq.heappush(heap, stick)
while heap:
if len(heap) == 1:
return cost
stick_one = heapq.heappop(heap)
stick_two = heapq.heappop(heap)
combined = stick_one + stick_two
cost += combined
heapq.heappush(heap, combined)This is a greedy problem.
One of the clues is when the description wants us to return the minimum cost of something.
Like other greedy problems, this is going to entail sorting the input so that we can prioritize the cheapest, or most expensive tasks first to conserve the most resources.
The cheapest tasks are the sticks with the lowest values, so we should prioritize those first to save the most money. We will push each stick into a heap so that we have the minimum cost at each point in time. We will then continuously pop two sticks off, combine them, add their costs, then push the combined stick back in.
Once we have only one stick in the heap, we will return the cost it took to combine all of the sticks.
Let's start by initializing our cost and heap.
cost = 0
heap = []
Then, we will iterate through the sticks array and push each stick into the heap.
for stick in sticks:
heapq.heappush(heap, stick)
Now we will begin combining sticks.
while heap:
If we only have one stick left in the heap, we will return that stick and the cost it took to combine the sticks into that one.
if len(heap) == 1:
return cost
Otherwise, we will continue by popping two sticks off the heap, combining them, and adding the stick costs to the total cost.
stick_one = heapq.heappop(heap)
stick_two = heapq.heappop(heap)
combined = stick_one + stick_two
cost += combined
Once we do that, we will push the stick back into the heap.
heapq.heappush(heap, combined)