Skip to main content
Talentd

Minimum Cost to Connect Sticks - Solution & Explanation

MediumPremiumFree on FleetCodeArrayGreedyHeap (Priority Queue)8 min readAsked at: Amazon, IBM, Google +2
Practice this problem

Problem Statement

You have some number of sticks with positive integer lengths. These lengths are given as an array sticks, where sticks[i] is the length of the ith stick.

You can connect any two sticks of lengths x and y into one stick by paying a cost of x + y. You must connect all the sticks until there is only one stick remaining.

Return the minimum cost of connecting all the given sticks into one stick in this way.

 

Example 1:

Input: sticks = [2,4,3]
Output: 14
Explanation: You start with sticks = [2,4,3].
1. Combine sticks 2 and 3 for a cost of 2 + 3 = 5. Now you have sticks = [5,4].
2. Combine sticks 5 and 4 for a cost of 5 + 4 = 9. Now you have sticks = [9].
There is only one stick left, so you are done. The total cost is 5 + 9 = 14.

Example 2:

Input: sticks = [1,8,3,5]
Output: 30
Explanation: You start with sticks = [1,8,3,5].
1. Combine sticks 1 and 3 for a cost of 1 + 3 = 4. Now you have sticks = [4,8,5].
2. Combine sticks 4 and 5 for a cost of 4 + 5 = 9. Now you have sticks = [9,8].
3. Combine sticks 9 and 8 for a cost of 9 + 8 = 17. Now you have sticks = [17].
There is only one stick left, so you are done. The total cost is 4 + 9 + 17 = 30.

Example 3:

Input: sticks = [5]
Output: 0
Explanation: There is only one stick, so you don't need to do anything. The total cost is 0.

 

Constraints:

  • 1 <= sticks.length <= 104
  • 1 <= sticks[i] <= 104

Approach Overview

Problem Overview: You are given an array where each value represents the length of a stick. Connecting two sticks costs the sum of their lengths, and the resulting stick can be used again. The goal is to connect all sticks into one while minimizing the total cost.

Approach 1: Repeated Sorting (Greedy Simulation) (Time: O(n2 log n), Space: O(1) or O(n) depending on sorting)

The greedy idea is straightforward: always connect the two smallest sticks first because smaller merges produce lower accumulated cost. A simple implementation repeatedly sorts the array, removes the two smallest values, adds their sum to the total cost, and inserts the merged stick back into the list. This works because the greedy choice is locally optimal, but repeatedly sorting the array is expensive. Each iteration performs a sort, leading to poor performance as the list shrinks.

Approach 2: Greedy + Min Heap (Priority Queue) (Time: O(n log n), Space: O(n))

The optimal approach uses a min heap (priority queue) to efficiently retrieve the two smallest sticks at every step. First push all stick lengths into the heap. Then repeatedly pop the two smallest elements, add their sum to the total cost, and push the merged stick back into the heap. Each pop and push operation takes O(log n), so the entire process runs in O(n log n). This pattern is identical to the classic optimal merge pattern and Huffman-style greedy construction.

The correctness comes from a greedy insight: combining the smallest sticks early prevents large values from being added repeatedly in future merges. A heap guarantees that the smallest elements are always accessible in logarithmic time, which removes the expensive repeated sorting.

The input itself is simply an array of stick lengths, but the real optimization comes from choosing the right data structure to repeatedly access minimum elements.

Recommended for interviews: The Greedy + Min Heap approach is what interviewers expect. It demonstrates recognition of the optimal merge pattern and efficient use of a priority queue. Mentioning the naive repeated-sort method helps show the reasoning process, but implementing the heap-based solution proves strong algorithmic fundamentals.

Solution

We can use a greedy approach, each time choosing the shortest two sticks to connect, which ensures the minimum cost of connection.

Therefore, we can use a priority queue (min heap) to maintain the current stick lengths. Each time, we take out two sticks from the priority queue to connect, then put the connected stick back into the priority queue, until there is only one stick left in the priority queue.

The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the length of the array sticks.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor ā†’

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Repeated Sorting (Greedy Simulation)O(nĀ² log n)O(1)ā€“O(n)Conceptual understanding of the greedy rule; acceptable only for very small inputs
Greedy + Min Heap (Priority Queue)O(n log n)O(n)Optimal approach for production code and coding interviews

Video Solution

Minimum Cost to Connect Sticks ā€¢ Kevin Naughton Jr. ā€¢ 23,128 views views

Watch 9 more video solutions ā†’

Frequently Asked Questions

Is Minimum Cost to Connect Sticks easy or hard?
Minimum Cost to Connect Sticks is typically classified as a Medium problem. The implementation is short, but recognizing the greedy pattern and using a priority queue correctly is the main challenge for many candidates.
Minimum Cost to Connect Sticks Python/Java solution
Most implementations use a built-in priority queue. Python uses heapq, Java uses PriorityQueue, C++ uses priority_queue with a min comparator, and similar structures exist in Go and TypeScript. All implementations follow the same pattern: push all sticks, repeatedly pop two smallest, add cost, and push the merged value.
How to solve Minimum Cost to Connect Sticks in O(n log n)?
Insert all stick lengths into a min heap. Repeatedly remove the two smallest sticks, add their sum to the total cost, and push the combined stick back into the heap. Continue until one stick remains. Heap operations guarantee O(log n) time per merge, giving an overall O(n log n) solution.
What is the best approach for Minimum Cost to Connect Sticks?
The optimal approach uses a greedy strategy with a min heap (priority queue). Always combine the two smallest sticks, add their cost to the total, and push the merged stick back into the heap. This ensures the smallest values are merged early, minimizing repeated large costs. The time complexity is O(n log n) and space complexity is O(n).
Is Minimum Cost to Connect Sticks asked at Google/Amazon/Meta?
Minimum Cost to Connect Sticks frequently appears in interviews at companies that test greedy algorithms and heap usage, including Amazon and Google-style interview rounds. The problem mirrors the optimal merge pattern and Huffman coding strategy, making it a common assessment of priority queue fundamentals.
What data structure is used in Minimum Cost to Connect Sticks?
The key data structure is a min heap (priority queue). It allows efficient retrieval of the two smallest stick lengths at each step. Without a heap, repeatedly sorting the array would significantly increase the runtime.
What is the time complexity of Minimum Cost to Connect Sticks?
The optimal solution using a min heap runs in O(n log n) time. Building the heap takes O(n), and each merge operation performs two heap pops and one push, each costing O(log n). Since there are nāˆ’1 merges, the overall complexity becomes O(n log n). Space complexity is O(n) for the heap.

Ready to solve this problem?

Practice Minimum Cost to Connect Sticks with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Cost to Merge Stones