Minimum Cost to Connect Sticks

8
0

Given an array of positive integers sticks, where each element represents the length of a stick. Any two sticks of lengths x and y can be connected into a longer stick by paying a cost equal to x + y. The newly formed stick is returned to the pool of sticks.

Continue connecting sticks until all sticks merge into one single stick and return the minimum cost to connect all sticks.

Example 1

Input: sticks = [2, 4, 3]

Output: 14

Explanation:

Connect sticks 2 and 3 → cost = 2 + 3 = 5 (sticks = [5, 4]),

Connect sticks 4 and 5 → cost = 4 + 5 = 9 (sticks = [9]),

Total cost = 5 + 9 = 14

Example 2

Input: sticks = [5]

Output: 0

Explanation: Only one stick exists initially. Zero operations required. Total cost = 0.

Brute Force Approach

The main idea is to try every possible way of connecting two sticks and pick the one that gives the smallest total cost. Every time two sticks are joined, their combined length is paid as a cost, and the new stick is added back to the pile. Repeating this choice for every pair until only one stick is left helps find the cheapest overall path.

Algorithm

  • If the list contains zero or one stick, no connection is needed, so return 0.

  • Initialize a variable to a very large number to track the lowest cost found.

  • Pick two sticks from the list at a time to test every possible combination.

  • For the selected pair, calculate the cost by adding their lengths together.

  • Create a new list containing the remaining sticks along with the newly merged stick.

  • Call the function recursively on this new list to find the cost of connecting the rest of the sticks.

  • Add the current connection cost to the recursive cost, and update the minimum cost if this path is smaller.

  • Continue this process for all pairs and return the minimum cost found.

Dry Run

Minimum Cost to Connect Sticks - Brute

Minimum Cost to Connect Sticks - Brute

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Computes the minimum cost to connect all sticks into one single stick.
int connectSticks(vector<int> sticks) {
// If there is zero or one stick, no connection is needed.
if (sticks.size() <= 1) {
return 0;
}
int minCostResult = INT_MAX;
// Iterate through all pairs to test every possible merge.
for (int i = 0; i < sticks.size(); i++) {
for (int j = i + 1; j < sticks.size(); j++) {
vector<int> newSticks;
int mergedCost = sticks[i] + sticks[j];
// Copy all elements except the two selected sticks into the new vector.
for (int k = 0; k < sticks.size(); k++) {
/*
If the current index is neither i nor j,
keep the stick for the next step.
*/
if (k != i && k != j) {
newSticks.push_back(sticks[k]);
}
}
// Add the newly combined stick to the remaining collection.
newSticks.push_back(mergedCost);
// Recursively compute the total cost for this choice.
int cost = mergedCost + connectSticks(newSticks);
minCostResult = min(minCostResult, cost);
}
}
return minCostResult;
}
};
// Driver Code starts
int main() {
vector<int> sticks = {2, 4, 3};
Solution solution;
// Call the function to compute the minimum connection cost.
int answer = solution.connectSticks(sticks);
cout << answer << "\n";
return 0;
}

Complexity Analysis

• Time Complexity: O(N!), as every possible pair of sticks is considered for merging at each step. Exploring all possible pairings across the recursive steps leads to factorial time complexity.

• Space Complexity: O(N), as the maximum recursion depth is proportional to N, with each merge reducing the number of sticks by one. This results in an O(N) recursion stack space.

Optimal Approach

In the brute force approach, every pair was tested recursively, which is way too slow because the number of combinations explodes. But testing every pair isn't really necessary. The key observation is that sticks merged early get added over and over again in future merges.

To keep the final cost as low as possible, the smallest sticks should always be merged first. Doing this manually with sorting after every merge would be slow, so a min-heap (priority queue) is used instead. A min-heap always keeps the smallest elements right at the top, making it super easy to grab the two shortest sticks, combine them, and throw the new stick back in heap.

Algorithm

  • If there is only one stick (or none), no connections are needed, so return 0 directly.

  • Initialize a variable to 0 to keep track of the total cost.

  • Put all the stick lengths into a min-heap so the smallest ones are always readily available.

  • Repeat the process as long as there is more than one stick in the heap:

    • Pull out the two smallest sticks from the top of the heap.

    • Add their lengths together to get the cost of this connection.

    • Add this cost to the running total.

    • Push the newly merged stick back into the min-heap.

  • Once only one stick remains in the heap, return the total cost.

Dry Run

Minimum Cost to Connect Sticks - Optimal

Minimum Cost to Connect Sticks - Optimal

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Computes the minimum cost to connect all sticks into one using a min-heap.
int connectSticks(vector<int>& sticks) {
// If there is zero or one stick, no connection is needed.
if (sticks.size() <= 1) {
return 0;
}
int totalCost = 0;
// Min-heap to always access the two smallest stick lengths efficiently.
priority_queue<int, vector<int>, greater<int>> minHeap;
// Push all initial stick lengths into the min-heap.
for (int i = 0; i < sticks.size(); i++) {
minHeap.push(sticks[i]);
}
// Continue merging until only one stick remains in the heap.
while (minHeap.size() > 1) {
// Extract the two smallest sticks available.
int stick1 = minHeap.top();
minHeap.pop();
int stick2 = minHeap.top();
minHeap.pop();
// Cost of combining these two sticks is the sum of their lengths.
int cost = stick1 + stick2;
totalCost += cost;
// Push the newly merged stick back into the heap.
minHeap.push(cost);
}
return totalCost;
}
};
// Driver Code starts
int main() {
vector<int> sticks = {2, 4, 3};
Solution solution;
// Call the function to compute the minimum connection cost.
int answer = solution.connectSticks(sticks);
cout << answer << "\n";
return 0;
}

Complexity Analysis

• Time Complexity: O(Nlog(N)), as inserting all N elements into the min-heap takes O(Nlog(N)) time. Additionally, N - 1 merging operations are performed, each requiring two extractions and one insertion, taking O(log(N)) time per operation.

• Space Complexity: O(N), as the min-heap can store up to N elements simultaneously, requiring linear extra space.

Interview follow-up Questions

No. An initial sort arranges the original sticks, but as soon as two sticks are combined, the new sum often turns out larger than several upcoming untouched sticks. To keep things in order without a heap, the new value would either require shifting elements in O(N) time or maintaining a separate queue for merged sticks. A min-heap automatically rearranges elements in O(log(N)) time, avoiding complex bookkeeping.

HeapTCS NQT

Read Similar Blogs

Comments0