Course4all
Join us on telegram
Home/dsa/Heap / Priority Queue/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 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 until there is only one stick remaining.

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

Visual Representation

sticks = [2,4,3] Options: 1. Connect 2 and 3: cost = 5, sticks = [4, 5] Connect 4 and 5: cost = 9, sticks = [9] Total cost: 5 + 9 = 14 (Optimal) 2. Connect 4 and 3: cost = 7, sticks = [2, 7] Connect 2 and 7: cost = 9, sticks = [9] Total cost: 7 + 9 = 16 (Not Optimal)
Medium

Examples

Input: sticks = [2,4,3]
Output: 14
Input: sticks = [1,8,3,5]
Output: 30
Input: sticks = [5]
Output: 0
Approach 1

Level I: Sorting Repeatedly (Simulation)

Intuition

To minimize the total cost, we intuitively always want to connect the two currently smallest sticks. We can simulate this by sorting the array, removing the two smallest, adding their sum to the cost, putting the new stick back, and re-sorting.

Thought Process

  1. If sticks.length <= 1, cost is 0.
  2. Loop while we have more than 1 stick.
  3. Sort the array/list.
  4. Take the first two elements and add them to get currentCost.
  5. Add currentCost to totalCost.
  6. Remove the first two elements and insert currentCost.
  7. Repeat until 1 stick remains.
⏱ O(N^2 log N)💾 O(N)

Detailed Dry Run

sticks = [1,8,3,5]

  1. Sort: [1, 3, 5, 8]
  2. Take 1, 3. Sum = 4. Cost = 4. Array [4, 5, 8]
  3. Sort: [4, 5, 8]
  4. Take 4, 5. Sum = 9. Cost = 4 + 9 = 13. Array [9, 8]
  5. Sort: [8, 9]
  6. Take 8, 9. Sum = 17. Cost = 13 + 17 = 30. Total = 30.
java
import java.util.*;
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 s = list.remove(0) + list.remove(0);
            total += s;
            list.add(s);
        }
        return total;
    }
}
Approach 2

Level II: Binary Search Insertion (Optimized Simulation)

Intuition

Maintain the list in sorted order by using binary search to find the insertion point for each new combined stick.

⏱ O(N^2)💾 O(N)

Detailed Dry Run

sticks = [1,8,3,5]

  1. Sort: [1, 3, 5, 8]
  2. 1+3=4. Binary search 4 in [5, 8] -> index 0. List: [4, 5, 8].
  3. 4+5=9. Binary search 9 in [8] -> index 1. List: [8, 9].
  4. 8+9=17. Total: 4+9+17=30.
java
import java.util.*;
class Solution {
    public int connectSticks(int[] sticks) {
        LinkedList<Integer> list = new LinkedList<>();
        Arrays.sort(sticks);
        for (int s : sticks) list.add(s);
        int total = 0;
        while (list.size() > 1) {
            int sum = list.removeFirst() + list.removeFirst();
            total += sum;
            int idx = Collections.binarySearch(list, sum);
            if (idx < 0) idx = -(idx + 1);
            list.add(idx, sum);
        }
        return total;
    }
}
Approach 3

Level III: Min-Heap (Optimal)

Intuition

To minimize the cost, we should always combine the two smallest sticks available. A Min-Heap is the perfect data structure for this, as it allows us to efficiently extract the two smallest elements and insert their sum.

Thought Process

  1. Push all stick lengths into a Min-Heap.
  2. While the heap contains more than one stick:
    • Extract the two smallest sticks (s1, s2).
    • Calculate their sum (cost = s1 + s2).
    • Add cost to the totalCost.
    • Push the new combined stick (cost) back into the heap.
  3. Once only one stick remains in the heap, return totalCost.
⏱ O(N log N) since we perform `HeapPop` and `HeapPush` N-1 times💾 O(N) for storing elements in the heap

Detailed Dry Run

sticks = [1,8,3,5]

  1. Heap: [1, 3, 5, 8], Cost: 0
  2. Pop 1, 3. Sum = 4. Cost = 4. Push 4. Heap: [4, 5, 8]
  3. Pop 4, 5. Sum = 9. Cost = 4 + 9 = 13. Push 9. Heap: [8, 9]
  4. Pop 8, 9. Sum = 17. Cost = 13 + 17 = 30. Push 17. Heap: [17]
  5. One element left. Return 30.
java
import java.util.*;

public class Main {
    public static int connectSticks(int[] sticks) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int stick : sticks) minHeap.add(stick);
        
        int totalCost = 0;
        while (minHeap.size() > 1) {
            int stick1 = minHeap.poll();
            int stick2 = minHeap.poll();
            int cost = stick1 + stick2;
            totalCost += cost;
            minHeap.add(cost);
        }
        return totalCost;
    }

    public static void main(String[] args) {
        System.out.println(connectSticks(new int[]{1, 8, 3, 5})); // 30
    }
}
← Previous QuestionSort Characters By Frequency
Next Question →Find Median from Data Stream