Domain 2MediumMEDIUM

Minimum Cost to Connect Sticks

Use a min-heap to greedily merge the two smallest sticks at each step, accumulating costs until one stick remains.

Domain: medium•Updated: 2026-09-09
#Greedy#Min-Heap/Priority Queue#$O(N log N)$#$O(1)$ auxiliary

Problem Breakdown

We are given an array of positive integers representing stick lengths and need to reduce them to a single stick by repeatedly merging any two sticks into one with cost equal to their sum. The goal is to minimize the total accumulated cost. This problem can be modeled as finding an optimal binary tree structure where leaf nodes are initial stick lengths, minimizing ∑(leaf_value×depth)\sum (\text{leaf\_value} \times \text{depth}).

  • Inputs: An array sticks of positive integers (1≤sticks.length≤1041 \le sticks.length \le 10^4, 1≤sticks[i]≤1041 \le sticks[i] \le 10^4).
  • Output: A single integer representing the minimum total cost.
  • Constraints: The order of merging significantly impacts the final sum; we must ensure smaller values are merged more frequently to minimize their contribution to subsequent costs.

Intuition

The core observation is that every stick’s length contributes to the total cost for every merge operation it participates in. To minimize the total cost, sticks with smaller lengths should be involved in as many merges as possible (higher depth), while larger sticks should participate fewer times.

This suggests a Greedy Strategy: At any point where we need two sticks to perform a merge, selecting the two smallest available sticks ensures that their combined length is added back into the pool of “available” lengths for future operations. By merging small values first, they are effectively removed from consideration as independent entities sooner but contribute less per unit cost than larger sticks would if merged later. This logic mirrors Huffman Coding, where nodes with lower frequency (or weight) are combined first to minimize weighted path length.

Approach

  1. Edge Case Check: If the array has fewer than or equal to one stick, no merges are needed; return 0.
  2. Heap Initialization: Convert the list of sticks into a Min-Heap using linear time complexity O(N)O(N). This allows efficient retrieval and removal of minimum elements.
  3. Merge Loop: While more than one stick remains in the heap:
    • Extract (pop) the smallest length (a).
    • Extract (pop) the next smallest length (b).
    • Calculate cost = a + b. Add this to the running total cost.
    • Insert the new combined stick (a + b) back into the heap using O(log⁡N)O(\log N) time.
  4. Termination: The loop ends when only one stick remains in the heap (the final merged stick). Return total_cost.

Complexity Analysis

  • Time Complexity: O(Nlog⁡N)O(N \log N).
    • Building the initial heap takes O(N)O(N).
    • We perform exactly N−1N-1 merge operations. Each operation involves two extract-min and one insert, each taking O(log⁡N)O(\log N) time on a binary heap.
    • Total: (N−1)×O(log⁡N)+O(N)=O(Nlog⁡N)(N - 1) \times O(\log N) + O(N) = O(N \log N).
  • Space Complexity: O(1)O(1) auxiliary space if we modify the input list in-place (as heapq does), or technically O(N)O(N) to store the heap elements. Given Python’s implementation, it reuses the array structure provided by the caller for efficiency.

Solution

import heapq

def minCost(sticks):
    # If there is only one stick or fewer (though constraints say >=1), 
    # no merging cost is incurred.
    if len(sticks) <= 1:
        return 0
    
    # Transform the list into a heap in O(N) time.
    heapq.heapify(sticks)
    
    total_cost = 0
    
    # Continue until only one stick remains (heap size == 1).
    while len(sticks) > 1:
        # Extract the two smallest sticks from the min-heap.
        first_stick = heapq.heappop(sticks)
        second_stick = heapq.heappop(sticks)
        
        current_merge_cost = first_stick + second_stick
        
        # Add this merge cost to our running total.
        total_cost += current_merge_cost
        
        # Push the new combined stick back into the heap for future merges.
        heapq.heappush(sticks, current_merge_cost)
    
    return total_cost

# Example usage:
print(minCost([2, 4, 3]))      # Output: 14
print(minCost([1, 8, 3, 5]))   # Output: 30

Edge Cases Handled

  • Single Stick: The loop condition len(sticks) > 1 prevents execution if only one stick exists; the function returns 0 immediately. This covers Example 3 ([5]).
  • Empty Input: Although constraints specify length ≥1\ge 1, the check handles an empty list gracefully by returning 0, preventing errors on heappop.
  • Large Values/Overflow: Python automatically promotes integers to arbitrary precision, so overflow is not a concern even if intermediate sums exceed standard integer limits. The logic holds for maximum constraints (N=104N=10^4, values ≤104\le 10^4).