LeetCode 1167 - Minimum Cost to Connect Sticks

The problem gives us an array of positive integers called sticks, where each value represents the length of a stick. We are allowed to repeatedly connect any two sticks together.

leetcodemediumarraygreedyheap-(priority-queue)

LeetCode Problem 1167

Difficulty: 🟡 Medium
Topics: Array, Greedy, Heap (Priority Queue)

Solution

Problem Understanding

The problem gives us an array of positive integers called sticks, where each value represents the length of a stick. We are allowed to repeatedly connect any two sticks together. If we connect sticks with lengths x and y, the operation costs x + y, and the resulting stick has length x + y.

The goal is to continue combining sticks until only one stick remains, while minimizing the total cost paid across all operations.

This is important because every newly created stick may be used again in future combinations. That means a large intermediate stick can contribute to the total cost multiple times. Because of this, the order in which we combine sticks directly affects the final answer.

For example, suppose we have sticks [1, 2, 100].

If we combine 1 + 2 = 3 first:

  • Cost so far = 3
  • Remaining sticks = [3, 100]
  • Final merge cost = 103
  • Total = 106

If we combine 100 + 2 = 102 first:

  • Cost so far = 102
  • Remaining sticks = [102, 1]
  • Final merge cost = 103
  • Total = 205

The first ordering is much cheaper.

The constraints are:

  • 1 <= sticks.length <= 10^4
  • 1 <= sticks[i] <= 10^4

The array can contain up to ten thousand elements, so repeatedly sorting the entire array after every operation would become inefficient. We need a solution that efficiently retrieves the smallest available sticks at every step.

Several edge cases are important:

  • A single stick, such as [5], should return 0 because no merges are needed.
  • Many identical values, such as [1,1,1,1], should still work correctly.
  • Very unbalanced inputs, such as [1,1,1,10000], can expose inefficient or incorrect greedy choices.
  • Large arrays require an algorithm better than repeated full sorting.

Approaches

Brute Force Approach

A brute force strategy would try all possible ways to combine sticks and compute the total cost for every possible merge order. Since every step allows multiple choices, the number of possible merge sequences grows extremely quickly.

For example, with n sticks:

  • At the first step, we choose 2 sticks out of n
  • At the next step, we choose 2 sticks out of n - 1
  • This branching continues until only one stick remains

This produces a combinatorial explosion. Even for relatively small inputs, the number of possible merge orders becomes enormous.

Although this approach guarantees the optimal answer because it checks every possibility, it is completely impractical for n = 10^4.

Another slightly better brute force method would repeatedly:

  1. Sort the array
  2. Take the two smallest sticks
  3. Merge them
  4. Insert the merged stick back into the array
  5. Sort again

This works correctly because it follows the optimal greedy strategy, but repeatedly sorting is inefficient.

Key Insight

The crucial observation is that we should always combine the two smallest sticks first.

Why?

Every merged stick may participate in future merges. If we create a large stick too early, that large value gets added repeatedly in later operations, increasing the total cost significantly.

This problem is structurally identical to the classic Huffman coding greedy strategy. Combining the two smallest values minimizes the future contribution of large sums.

To efficiently retrieve the two smallest sticks repeatedly, we use a min heap, also called a priority queue.

A min heap allows:

  • Removing the smallest element in O(log n)
  • Inserting a new element in O(log n)
  • Building the heap initially in O(n)

This makes the entire algorithm efficient enough for the problem constraints.

Approach Time Complexity Space Complexity Notes
Brute Force Exponential Exponential Tries all merge orders
Repeated Sorting O(n² log n) O(n) Sorts after every merge
Optimal Heap Solution O(n log n) O(n) Uses a min heap to always access smallest sticks

Algorithm Walkthrough

  1. Handle the edge case where the array contains only one stick.

If there is only one stick, no merges are needed, so the answer is 0. 2. Convert the input array into a min heap.

A min heap always keeps the smallest element at the top. This allows us to efficiently retrieve the two smallest sticks at every step. 3. Initialize a variable called total_cost to 0.

This variable accumulates the total merge cost across all operations. 4. Repeat while the heap contains more than one stick.

As long as multiple sticks remain, we still need additional merges. 5. Remove the two smallest sticks from the heap.

These are the optimal sticks to merge next because choosing the smallest pair minimizes future costs. 6. Compute their merge cost.

If the two sticks are a and b, then:

merged = a + b 7. Add the merge cost to total_cost.

Every merge operation contributes directly to the final answer. 8. Push the merged stick back into the heap.

The newly formed stick may participate in future merges, so it must remain available. 9. Continue until only one stick remains.

At that point, all sticks have been connected into a single stick. 10. Return total_cost.

Why it works

The greedy strategy works because every merged stick can be reused in future operations. Smaller sticks should therefore contribute to future costs as little as possible.

By always combining the two smallest sticks first, we minimize the growth of intermediate stick lengths. Any alternative strategy that merges a larger stick earlier would increase future merge costs.

This property is the same reasoning used in Huffman coding, where repeatedly combining the smallest weights produces the minimum total weighted path length.

Python Solution

from typing import List
import heapq

class Solution:
    def connectSticks(self, sticks: List[int]) -> int:
        if len(sticks) <= 1:
            return 0

        heapq.heapify(sticks)

        total_cost = 0

        while len(sticks) > 1:
            first = heapq.heappop(sticks)
            second = heapq.heappop(sticks)

            merged = first + second
            total_cost += merged

            heapq.heappush(sticks, merged)

        return total_cost

The implementation begins by handling the simplest edge case. If there is only one stick, the function immediately returns 0.

Next, heapq.heapify(sticks) transforms the list into a valid min heap in linear time. This is more efficient than inserting elements one by one.

The variable total_cost tracks the cumulative merge cost.

Inside the loop, the algorithm repeatedly removes the two smallest sticks using heapq.heappop. Their sum becomes both:

  • The cost of the current operation
  • The length of the newly formed stick

The merged stick is inserted back into the heap using heapq.heappush, allowing it to participate in future merges.

The loop continues until only one stick remains, meaning all sticks have been connected.

Go Solution

package main

import (
	"container/heap"
)

type MinHeap []int

func (h MinHeap) Len() int {
	return len(h)
}

func (h MinHeap) Less(i, j int) bool {
	return h[i] < h[j]
}

func (h MinHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h *MinHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}

func (h *MinHeap) Pop() interface{} {
	old := *h
	n := len(old)

	value := old[n-1]
	*h = old[:n-1]

	return value
}

func connectSticks(sticks []int) int {
	if len(sticks) <= 1 {
		return 0
	}

	h := MinHeap(sticks)
	heap.Init(&h)

	totalCost := 0

	for h.Len() > 1 {
		first := heap.Pop(&h).(int)
		second := heap.Pop(&h).(int)

		merged := first + second
		totalCost += merged

		heap.Push(&h, merged)
	}

	return totalCost
}

The Go implementation uses the container/heap package, which requires defining a custom heap type that implements the heap.Interface.

Unlike Python, Go does not provide a built in min heap for integers directly, so we define:

  • Len
  • Less
  • Swap
  • Push
  • Pop

The logic of the algorithm remains identical to the Python version.

Go slices are dynamic, so the heap operations modify the underlying slice in place. Integer overflow is not a concern here because the constraints keep the total well within Go's integer range.

Worked Examples

Example 1

Input:

sticks = [2,4,3]

After heapification:

[2,3,4]
Step Heap Before Removed Merge Cost Total Cost Heap After
1 [2,3,4] 2, 3 5 5 [4,5]
2 [4,5] 4, 5 9 14 [9]

Final answer:

14

Example 2

Input:

sticks = [1,8,3,5]

After heapification:

[1,5,3,8]
Step Heap Before Removed Merge Cost Total Cost Heap After
1 [1,3,5,8] 1, 3 4 4 [4,5,8]
2 [4,5,8] 4, 5 9 13 [8,9]
3 [8,9] 8, 9 17 30 [17]

Final answer:

30

Example 3

Input:

sticks = [5]

Since only one stick exists, no merges are required.

Step Action
Initial One stick only
Result Return 0

Final answer:

0

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Each heap operation costs O(log n), and we perform O(n) merges
Space O(n) The heap stores all sticks

The heap initially contains all n sticks. Each merge removes two sticks and inserts one new stick, so there are exactly n - 1 merge operations.

Each pop and push operation costs O(log n), making the total runtime O(n log n).

The heap itself stores up to n elements, so the auxiliary space complexity is O(n).

Test Cases

from typing import List
import heapq

class Solution:
    def connectSticks(self, sticks: List[int]) -> int:
        if len(sticks) <= 1:
            return 0

        heapq.heapify(sticks)

        total_cost = 0

        while len(sticks) > 1:
            first = heapq.heappop(sticks)
            second = heapq.heappop(sticks)

            merged = first + second
            total_cost += merged

            heapq.heappush(sticks, merged)

        return total_cost

solution = Solution()

assert solution.connectSticks([2, 4, 3]) == 14  # Example 1
assert solution.connectSticks([1, 8, 3, 5]) == 30  # Example 2
assert solution.connectSticks([5]) == 0  # Single stick edge case
assert solution.connectSticks([1, 1]) == 2  # Smallest non-trivial input
assert solution.connectSticks([1, 1, 1, 1]) == 8  # Repeated identical values
assert solution.connectSticks([1, 2, 3, 4, 5]) == 33  # Increasing sequence
assert solution.connectSticks([5, 4, 3, 2, 1]) == 33  # Decreasing sequence
assert solution.connectSticks([10000, 10000]) == 20000  # Large values
assert solution.connectSticks([1, 1, 1, 10000]) == 10008  # Very unbalanced input
assert solution.connectSticks([2, 2, 3, 3]) == 20  # Multiple equal merges
Test Why
[2,4,3] Validates the basic example
[1,8,3,5] Tests multiple merge rounds
[5] Tests single element edge case
[1,1] Smallest possible merge
[1,1,1,1] Ensures repeated equal values work correctly
[1,2,3,4,5] Tests increasing input order
[5,4,3,2,1] Tests decreasing input order
[10000,10000] Tests large stick values
[1,1,1,10000] Tests greedy correctness on unbalanced inputs
[2,2,3,3] Tests repeated intermediate merges

Edge Cases

Single Stick

An input such as [5] is important because no merge operations are necessary. A careless implementation might still attempt heap operations and fail when trying to pop two elements.

The implementation handles this immediately with:

if len(sticks) <= 1:
    return 0

This guarantees safe execution for the smallest possible input.

Many Equal Values

Inputs like [1,1,1,1] can expose bugs in heap handling or merge ordering assumptions. Since many values are identical, the algorithm must still correctly maintain heap structure and cumulative cost.

The min heap naturally handles duplicate values without any special logic, ensuring correct behavior.

Highly Unbalanced Values

An input such as [1,1,1,10000] demonstrates why the greedy strategy matters. Combining large sticks too early dramatically increases future costs.

The implementation always extracts the two smallest sticks first, ensuring the large value remains untouched until necessary. This minimizes the repeated contribution of large intermediate sums.

Large Input Size

The problem allows up to 10^4 sticks. A naive solution that repeatedly sorts the array after every merge would become inefficient.

Using a min heap guarantees efficient O(log n) insertions and removals, allowing the algorithm to scale comfortably within the constraints.