⚡Flashcard Drill➔
NeetCode #528LC-1167MediumHeap / Priority QueueNC Algo100
← Back to All Problems

#528 · #1167 · Minimum Cost to Connect Sticks(连接棒材的最低费用)

📌 Problem Statement & Constraints

You are given an array sticks of positive integers. Repeatedly connect two sticks into one, paying the cost of the combined length. Return the minimum total cost to connect all sticks into one. Constraints: 1 <= sticks.length <= 10^4, 1 <= sticks[i] <= 10^4.

💡 Core Algorithmic Approaches

  1. Always combining the two shortest sticks is optimal -- this is Huffman coding.
  2. A min-heap gives the two shortest in O(log n).
  3. Push the combined length back and add the cost.
  4. The greedy is optimal by an exchange argument: any solution can be transformed to one that combines the shortest pair first without increasing the cost.

💻 Benchmark Python3 Implementation

class Solution:
    def connectSticks(self, sticks: List[int]) -> int:
        import heapq
        if len(sticks) < 2:
            return 0                       # nothing to connect
        heapq.heapify(sticks)
        total = 0
        while len(sticks) > 1:
            s = heapq.heappop(sticks) + heapq.heappop(sticks)   # two shortest
            total += s                     # pay the combined length
            heapq.heappush(sticks, s)
        return total

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n log n): each of the n - 1 connections costs O(log n).
💾 Space Complexity
O(1) beyond the heap (the input array is reused).

⚠️ Interview Pitfalls & Follow-ups

  • Combining the two longest: that maximises the cost.
  • Sorting once and combining left to right: the combined sticks must re-enter the pool, so a heap is required.
  • Forgetting the len < 2 case: the loop simply does not execute, returning 0, which is correct -- but the guard documents it.
  • Adding the cost before combining: the cost is the sum of the two sticks, so the order within the expression matters only for clarity.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Heap / Priority Queue Problems