Course4all
Join us on telegram
Home/dsa/Greedy/Minimum Cost to Connect Sticks

Minimum Cost to Connect Sticks

Master this topic with zero to advance depth.

Minimum Cost to Connect Sticks

You have sticks with positive integer lengths. You can connect any two sticks into one by paying a cost equal to their sum. Return the minimum cost to connect all sticks.

Visual Representation

Sticks: [2, 4, 3] 1. Combine 2 and 3: Cost = 5. Remaining: [5, 4] 2. Combine 5 and 4: Cost = 9. Remaining: [9] Total: 14
Medium

Examples

Input: sticks = [2,4,3]
Output: 14

Combining 2+3 first followed by 4 is cheaper than other combinations.

Approach 1

Level I: Brute Force (Try All Pairs)

Intuition

Try every possible sequence of connecting two sticks and find the one that results in the minimum total cost. This can be implemented using recursion by trying all pairs at each step.

Thought Process

  1. If only 1 stick remains, return 0.
  2. For every pair of sticks (i,j)(i, j):
    • Combine them: cost = sticks[i] + sticks[j].
    • Recursively solve for the new set of sticks.
    • Track the minimum total cost across all possible initial pairs.
⏱ O(N!)💾 O(N)

Detailed Dry Run

sticks = [2, 4, 3]

  • Option 1: (2,4) -> [6,3]. Then (6,3) -> [9]. Cost = 6 + 9 = 15.
  • Option 2: (2,3) -> [5,4]. Then (5,4) -> [9]. Cost = 5 + 9 = 14. (MIN)
  • Option 3: (4,3) -> [7,2]. Then (7,2) -> [9]. Cost = 7 + 9 = 16.
java
public class Solution {
    public int connectSticks(int[] sticks) {
        List<Integer> list = new ArrayList<>();
        for (int s : sticks) list.add(s);
        return solve(list);
    }
    private int solve(List<Integer> list) {
        if (list.size() <= 1) return 0;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < list.size(); i++) {
            for (int j = i + 1; j < list.size(); j++) {
                int sum = list.get(i) + list.get(j);
                List<Integer> next = new ArrayList<>();
                for (int k = 0; k < list.size(); k++)
                    if (k != i && k != j) next.add(list.get(k));
                next.add(sum);
                min = Math.min(min, sum + solve(next));
            }
        }
        return min;
    }
}
Approach 2

Level II: Sorting and Re-sorting

Intuition

At each step, we identify the two smallest sticks by sorting the list, combine them, and repeat. While better than brute force, re-sorting at every step is inefficient.

Thought Process

  1. While more than 1 stick exists:
    • Sort the current list of sticks.
    • Take the two smallest elements, sum them.
    • Add the sum to totalCost, remove the two elements, and add the sum back.
  2. Repeat until 1 stick remains.
⏱ O(N^2 log N)💾 O(N)

Detailed Dry Run

sticks = [2, 4, 3]

  1. Sort: [2, 3, 4]. Combine 2+3=5. Total=5. Sticks: [5, 4]
  2. Sort: [4, 5]. Combine 4+5=9. Total=14. Sticks: [9] Result: 14
java
public class Solution {
    public int connectSticks(int[] sticks) {
        List<Integer> list = new ArrayList<>();
        for (int s : sticks) list.add(s);
        int total = 0;
        while (list.size() > 1) {
            Collections.sort(list);
            int sum = list.remove(0) + list.remove(0);
            total += sum;
            list.add(sum);
        }
        return total;
    }
}
Approach 3

Level III: Optimal Greedy (Min-Heap)

Intuition

To minimize the total cost, we should always combine the two smallest sticks currently available. This is the Huffman Coding principle.

Thought Process

  1. Add all sticks to a Min-Heap.
  2. While heap.size() > 1:
    • Pop s1 and s2 (two smallest).
    • cost = s1 + s2.
    • totalCost += cost, Push cost back to heap.

Pattern: Huffman Coding (Greedy Merging)

⏱ O(N log N) for heap operations.💾 O(N) for heap.

Detailed Dry Run

Sticks: [1, 8, 3, 5]

  1. Pop 1, 3. Sum = 4. Total = 4. Heap: [4, 5, 8]
  2. Pop 4, 5. Sum = 9. Total = 13. Heap: [8, 9]
  3. Pop 8, 9. Sum = 17. Total = 30. Result: 30
java
public class Solution {
    public int connectSticks(int[] sticks) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int s : sticks) pq.add(s);
        int totalCost = 0;
        while (pq.size() > 1) {
            int sum = pq.poll() + pq.poll();
            totalCost += sum;
            pq.add(sum);
        }
        return totalCost;
    }
}
← Previous QuestionCandy Distribution
Next Question →Patching Array