Minimum cost to connect sticks

Array Greedy Heap (Priority Queue)

71.8% acceptance

Mar 31, 2026

1353

158

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.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn connect_sticks(sticks: Vec<i32>) -> i32 {
    use std::collections::BinaryHeap;
    use std::cmp::Reverse;
    let mut heap: BinaryHeap<Reverse<i32>> = sticks.into_iter().map(Reverse).collect();
    let mut cost = 0;
    while heap.len() > 1 {
      let a = heap.pop().unwrap().0;
      let b = heap.pop().unwrap().0;
      let sum = a + b;
      cost += sum;
      heap.push(Reverse(sum));
    }
    cost
  }
}