Problem of The Day: Minimum Cost to Connect Sticks

2 min read 501 words

Problem Statement

leetcode problem link

Solution [Accepted]

class Solution:
    def connectSticks(self, sticks: List[int]) -> int:
        if len(sticks) == 1:
            return 0
        min_heap = sticks[:]
        heapq.heapify(min_heap)
        res = 0
        while len(min_heap) > 1:
            x = heapq.heappop(min_heap)
            y = heapq.heappop(min_heap)
            res += (x + y)
            heapq.heappush(min_heap, x + y)

        return res

time: O(n log n) space: O(n)

Editorial

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

public class Solution {
    public int ConnectSticks(int[] sticks) {
        // Edge case: no cost needed if 0 or 1 stick
        if (sticks.Length <= 1) {
            return 0;
        }

        // Use min-heap (PriorityQueue) to always get smallest sticks
        // Time: O(n) to build heap
        var minHeap = new PriorityQueue<int, int>();
        foreach (var stick in sticks) {
            minHeap.Enqueue(stick, stick);
        }

        int totalCost = 0;

        // Greedy approach: always combine two smallest sticks
        // Each combination reduces stick count by 1
        // Time: O(n log n) - (n-1) iterations × O(log n) per heap op
        while (minHeap.Count > 1) {
            // Extract two smallest sticks
            int first = minHeap.Dequeue();
            int second = minHeap.Dequeue();

            // Cost to combine them
            int combined = first + second;
            totalCost += combined;

            // Put combined stick back for future combinations
            minHeap.Enqueue(combined, combined);
        }

        return totalCost;
    }
}