Problem of The Day: Minimum Cost to Connect Sticks

Problem Statement

leetcode problem link

Min-heap approach [Accepted]

class Solution:
    def connectSticks(self, sticks: List[int]) -> int:
        min_heap = []
        cost = 0
        for stick in sticks:
            heapq.heappush(min_heap, stick)

        while len(min_heap) >= 2:
            x = heapq.heappop(min_heap)
            y = heapq.heappop(min_heap)
            curr_cost = x + y
            cost += curr_cost
            if not min_heap:
                break
            heapq.heappush(min_heap, curr_cost)


        return cost

Editorial

Approach 1: Greedy

class Solution:
    def connectSticks(self, sticks: List[int]) -> int:
        min_heap = sticks
        heapify(min_heap)
        total_cost = 0

        while len(min_heap) > 1:
            new_stick = heappop(min_heap) + heappop(min_heap)
            total_cost += new_stick
            heappush(min_heap, new_stick)

        return total_cost