Log inSign up
mediumLeetCodeNot Started

Minimum Cost to Connect Sticks

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Heap
Solve on LeetCode
Lesson

Problem Statement

You have some number of sticks with positive integer lengths given in an array sticks. You can connect any two sticks of lengths x and y into one stick by paying a cost of x + y. You must repeat this operation until only one stick remains.

Return the minimum total cost to connect all sticks into one stick.

Example 1 · Example 1: Four Sticks:

Input: sticks = [2, 4, 3]
Output: 14
Explanation: 1. Connect sticks 2 and 3 for cost 2 + 3 = 5. Remaining sticks: [4, 5]. Total cost = 5. 2. Connect sticks 4 and 5 for cost 4 + 5 = 9. Remaining sticks: [9]. Total cost = 5 + 9 = 14. Min-Heap Tree: (2) merge 2 & 3 -> (5) / \ -----------------> (4) (3) (4) / (5)

Example 2 · Example 2: Single Stick:

Input: sticks = [5]
Output: 0
Explanation: Only one stick already exists, no merges required. Total cost = 0.

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand why greedy choice property holds for Huffman-style merges.
  • Implement dynamic Priority Queue in C++, Java, Python, and JavaScript.
  • Analyze why two-queue solution works in O(N) after initial sorting.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Repeatedly merge two smallest values until one remains.
  • Total cost depends on sum of intermediate merges.
  • Classic Huffman greedy merge pattern.

Algorithmic Decision Tree:

  • Sorting once is insufficient because newly merged sticks need to be placed into the sorted order.
  • Use a Min-Heap (PriorityQueue) to dynamically maintain the smallest elements after each merge.

Connected Patterns:

Connect Ropes with Minimum CostMerge k Sorted ListsHuffman Coding

1. Brute Force — Repeated Minimum Search in Array

Intuition

At each step of merging, find the index of the minimum element, remove it, then find the index of the second minimum element, add their sum to total cost, and insert the sum back into the array. Repeat until the array size is 1.

When to apply: When external libraries and heap data structures cannot be used and N is small (N <= 100).

Algorithm

  1. Step 1: Check if array has 1 or 0 elements; if so, return 0.
  2. Step 2: While array size > 1, scan array to find index of smallest stick min1.
  3. Step 3: Scan array to find index of second smallest stick min2.
  4. Step 4: Sum = min1 + min2. Add sum to total cost.
  5. Step 5: Remove min1 and min2 from array, append sum.
  6. Step 6: Repeat until 1 stick remains. Return total cost.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4using namespace std;
5
6class Solution {
7public:
8 int connectSticks(vector<int>& sticks) {
9 if (sticks.size() <= 1) return 0;
10 int totalCost = 0;
11 while (sticks.size() > 1) {
12 auto it1 = min_element(sticks.begin(), sticks.end());
13 int min1 = *it1;
14 sticks.erase(it1);
15
16 auto it2 = min_element(sticks.begin(), sticks.end());
17 int min2 = *it2;
18 sticks.erase(it2);
19
20 int combined = min1 + min2;
21 totalCost += combined;
22 sticks.push_back(combined);
23 }
24 return totalCost;
25 }
26};
27
28int main() {
29 Solution sol;
30 vector<int> sticks = {2, 4, 3};
31 cout << "Minimum Cost (Brute Force): " << sol.connectSticks(sticks) << endl;
32 return 0;
33}

Time & Space Complexity

  • Time complexity: O(N^2) — O(N2) because each iteration finds the minimum in linear time.
  • Space complexity: O(N) — O(N) to store copies of elements.

Why Brute Force Doesn't Scale:

With N = 105, an O(N2) brute force takes ~1010 operations which times out. Min-Heap scales to O(N log N) (~1.7 * 106 operations).

For N = 100,000, Min-Heap takes ~15ms whereas O(N2) takes several minutes.

2. Better — Two Queues Merge Strategy

Intuition

By sorting the sticks once, Queue 1 is in strictly ascending order. Since sum of smaller elements is monotonic, Queue 2 is also naturally produced in sorted order. At each step, picking the smallest from either Queue 1 or Queue 2 takes O(1) time.

When to apply: When sorting is already done or O(N log N) sorting followed by linear O(N) merging is preferred.

Algorithm

  1. Step 1: Sort sticks in ascending order and push all into queue q1.
  2. Step 2: Initialize an empty queue q2 for merged sticks.
  3. Step 3: While q1.size() + q2.size() > 1, extract the smaller of front(q1) and front(q2) twice.
  4. Step 4: Sum the two extracted values, add to total cost, and push sum into q2.
  5. Step 5: Return total cost.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 int connectSticks(vector<int>& sticks) {
10 if (sticks.size() <= 1) return 0;
11 sort(sticks.begin(), sticks.end());
12 queue<int> q1, q2;
13 for (int s : sticks) q1.push(s);
14
15 int totalCost = 0;
16 auto getMin = [&]() {
17 if (q1.empty()) { int val = q2.front(); q2.pop(); return val; }
18 if (q2.empty()) { int val = q1.front(); q1.pop(); return val; }
19 if (q1.front() <= q2.front()) { int val = q1.front(); q1.pop(); return val; }
20 int val = q2.front(); q2.pop(); return val;
21 };
22
23 while (q1.size() + q2.size() > 1) {
24 int first = getMin();
25 int second = getMin();
26 int combined = first + second;
27 totalCost += combined;
28 q2.push(combined);
29 }
30 return totalCost;
31 }
32};
33
34int main() {
35 Solution sol;
36 vector<int> sticks = {2, 4, 3};
37 cout << "Minimum Cost (Two Queues): " << sol.connectSticks(sticks) << endl;
38 return 0;
39}

Time & Space Complexity

  • Time complexity: O(N log N) — O(N log N) dominated by the initial sort.
  • Space complexity: O(N) — O(N) auxiliary space to store queues.

3. Optimal — Min-Heap (Priority Queue)

Intuition

A binary min-heap allows retrieving and removing the minimum element in O(log N) time. After pushing all elements into the min-heap in O(N) using Floyd's build-heap algorithm, we execute N-1 extractions and insertions, each taking O(log N) time.

When to apply: Standard optimal approach for Huffman merges and dynamic priority problems.

Algorithm

  1. Step 1: If sticks has 0 or 1 element, return 0.
  2. Step 2: Insert all elements of sticks into a Min-Heap.
  3. Step 3: While heap size > 1, extract smallest stick a and second smallest b.
  4. Step 4: Sum = a + b. Add sum to totalCost.
  5. Step 5: Push sum back into the Min-Heap.
  6. Step 6: Return totalCost once heap has only 1 element.

Interactive Trace for Minimum Cost to Connect Sticks

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1: Heap initialized with sticks [1, 3, 5, 8]
Visual state
Values and pointers at this exact step
tree
Root: 1
1
Left: 3
3
Right: 5
5
Child: 8
8

Node order shown; add connections to display explicit tree edges.

extract: h1
Check / comparison
Extract 1 and 3. Sum = 4. Total cost = 4.
Decision / next transition
Insert 4 back into Min-Heap.
Why this step matters

Step 1: Heap initialized with sticks [1, 3, 5, 8]. Top elements are 1 and 3.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4using namespace std;
5
6class Solution {
7public:
8 int connectSticks(vector<int>& sticks) {
9 if (sticks.size() <= 1) return 0;
10 priority_queue<int, vector<int>, greater<int>> minHeap(sticks.begin(), sticks.end());
11 int totalCost = 0;
12 while (minHeap.size() > 1) {
13 int first = minHeap.top(); minHeap.pop();
14 int second = minHeap.top(); minHeap.pop();
15 int combined = first + second;
16 totalCost += combined;
17 minHeap.push(combined);
18 }
19 return totalCost;
20 }
21};
22
23int main() {
24 Solution sol;
25 vector<int> sticks = {2, 4, 3};
26 cout << "Minimum Cost (Optimal Min-Heap): " << sol.connectSticks(sticks) << endl;
27 return 0;
28}

Time & Space Complexity

  • Time complexity: O(N log N) — O(N log N) from N-1 iterations of logarithmic heap operations.
  • Space complexity: O(N) — O(N) to store elements inside the Min-Heap.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Linear Scan MergeO(N^2)O(1) auxiliaryIn each step, scan the remaining list to find the two minimum sticks, merge them, and overwrite elements.Linear scan to repeatedly find minimums.
2.Better — Two QueuesO(N log N)O(N)Sort initial sticks into Queue 1. Put merged sums into Queue 2. The minimum at any step is the min of the heads of Queue 1 and Queue 2.Initial sorting step.
3.Optimal — Min-Heap Priority QueueOptimalO(N log N)O(N)Heapify all sticks in O(N). Repeatedly extract two smallest elements, add their sum to total cost, and insert their sum back into heap until size becomes 1.None. Optimal.

Common Pitfalls & Crucial Edge Cases

Forgetting to insert the merged stick back

Must re-enter heap to participate in subsequent merges.

Returning the final combined stick instead of total cost

The problem asks for cumulative cost paid, not final stick length.

Sorting only once without maintaining new sums

New sums must be inserted into the sorted order, which requires a heap or two queues.

Crucial Edge Cases to Validate:

  • Single stick (N = 1) — No connections can be made; return cost 0.
  • Two sticks (N = 2) — Return their sum directly after 1 merge.
  • All identical stick lengths — Handled consistently by min-heap ordering.
  • Large sticks — Values can accumulate to large integers; ensure 64-bit integer handling where applicable.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Mention Huffman coding immediately — interviewers love candidates who recognize that this problem is mathematically identical to Huffman code construction.
  2. Discuss the Two-Queues approach as a follow-up if asked how to optimize after an initial sort.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does the greedy choice of picking the two smallest sticks always yield minimum total cost?

Back to DSA Sheet