< Back





1167. Minimum Cost to Connect Sticks

This problem is actually pretty closely related to the Huffman coding algorithm.
We're given a list of sticks and asked to find the minimum cost to connect them all. The cost is
determined by the length of the sticks being connected. Once a stick is connected to another stick,
it's returned to the list of sticks.

To easily solve this, we use a min heap to maintain the smallest sticks. While we have more than one
stick, we pop the two smallest sticks from the heap, add them together, record the cost, and push
them back onto the heap.

Eventually, we'll have connected all the sticks with the minimum cost to do so.

The solution is as follows:


  from heapq import *

  class Solution:
      def connectSticks(self, sticks: List[int]) -> int:
          heapify(sticks)
          ans, n = 0, len(sticks)

          while n > 1:
              cost = heappop(sticks) + heappop(sticks)
              heappush(sticks, cost)
              ans += cost
              n -= 1

          return ans


_ Time Complexity:

  O(n log n) - Where n is the number of sticks - process all n sticks. Each heap operation costs
  log n time.

_ Space Complexity:

  O(n) - We store all the sticks in the heap.