Problem

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.

Examples

Example 1:

1
2
3
4
5
6

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:

1
2
3
4
5
6
7

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:

1
2
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 <= 10^4
  • 1 <= sticks[i] <= 10^4

Solution

Method 1 – Greedy with Min-Heap

Intuition

To minimize the total cost, always connect the two smallest sticks first. This is because connecting larger sticks later will accumulate less cost overall. Using a min-heap allows us to efficiently pick the two smallest sticks at each step.

Approach

  1. Insert all stick lengths into a min-heap (priority queue).
  2. While there is more than one stick in the heap:
    • Pop the two smallest sticks.
    • Add their lengths to get the cost for this connection.
    • Add the cost to the running total.
    • Push the combined stick back into the heap.
  3. Return the total cost after all sticks are connected.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    int connectSticks(vector<int>& sticks) {
        priority_queue<int, vector<int>, greater<int>> pq(sticks.begin(), sticks.end());
        int ans = 0;
        while (pq.size() > 1) {
            int a = pq.top(); pq.pop();
            int b = pq.top(); pq.pop();
            ans += a + b;
            pq.push(a + b);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func connectSticks(sticks []int) int {
    h := &heapMin{}; heap.Init(h)
    for _, v := range sticks { heap.Push(h, v) }
    ans := 0
    for h.Len() > 1 {
        a := heap.Pop(h).(int)
        b := heap.Pop(h).(int)
        ans += a + b
        heap.Push(h, a+b)
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    public int connectSticks(int[] sticks) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int v : sticks) pq.offer(v);
        int ans = 0;
        while (pq.size() > 1) {
            int a = pq.poll(), b = pq.poll();
            ans += a + b;
            pq.offer(a + b);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    fun connectSticks(sticks: IntArray): Int {
        val pq = PriorityQueue<Int>()
        sticks.forEach { pq.add(it) }
        var ans = 0
        while (pq.size > 1) {
            val a = pq.poll()
            val b = pq.poll()
            ans += a + b
            pq.add(a + b)
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def connectSticks(self, sticks: list[int]) -> int:
        import heapq
        heapq.heapify(sticks)
        ans = 0
        while len(sticks) > 1:
            a = heapq.heappop(sticks)
            b = heapq.heappop(sticks)
            ans += a + b
            heapq.heappush(sticks, a + b)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

impl Solution {
    pub fn connect_sticks(sticks: Vec<i32>) -> i32 {
        use std::collections::BinaryHeap;
        let mut heap = BinaryHeap::new();
        for v in sticks { heap.push(-v); }
        let mut ans = 0;
        while heap.len() > 1 {
            let a = -heap.pop().unwrap();
            let b = -heap.pop().unwrap();
            ans += a + b;
            heap.push(-(a + b));
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    connectSticks(sticks: number[]): number {
        const pq = [...sticks].sort((a, b) => a - b);
        let ans = 0;
        while (pq.length > 1) {
            pq.sort((a, b) => a - b);
            const a = pq.shift()!;
            const b = pq.shift()!;
            ans += a + b;
            pq.push(a + b);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n log n) where n is the number of sticks, due to heap operations.
  • 🧺 Space complexity: O(n) for the heap.