Minimum Cost to Connect Sticks

Medium Heaps Top K / Kth Largest / Smallest Original on LeetCode

Minimum Cost to Connect Sticks is a medium heaps problem solved with the top k / kth largest / smallest pattern. The best approach, optimal (min-heap greedy), runs in O(n log n) time and O(n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (scan for the two shortest) up.

Problem

You have sticks with positive integer lengths, given as the array sticks. You can join any two sticks of lengths x and y into one stick of length x + y, and that join costs x + y.

Keep joining until a single stick is left. Return the minimum total cost of doing so.

Examples

Example 1

Input
sticks = [3, 6, 2]
Output
16
Why
Join 2 + 3 = 5 (cost 5), then 5 + 6 = 11 (cost 11). Total 16.

Example 2

Input
sticks = [4, 4, 4, 4]
Output
32
Why
Join pairs into 8 and 8 (cost 16), then 8 + 8 = 16 (cost 16). Total 32.

Example 3

Input
sticks = [9]
Output
0
Why
There is already a single stick, so no joins are needed.

Constraints

  • 1 <= sticks.length <= 10^4
  • 1 <= sticks[i] <= 10^4

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (scan for the two shortest)O(n²)O(n)
Optimal (min-heap greedy)O(n log n)O(n)

1Brute force (scan for the two shortest)

TimeO(n²)There are n - 1 rounds and each scans up to n sticks.
SpaceO(n)The working list of sticks.

Apply the greedy rule directly with a plain list: every round, scan the list for the two shortest sticks, remove them, pay their sum and put the joined stick back.

  1. Copy the sticks into a list.
  2. While more than one stick remains, find the indices of the two smallest values with one scan.
  3. Remove both, add their sum to the cost, and append the sum to the list.
  4. Return the cost.
class Solution {
    public int connectSticks(int[] sticks) {
        List<Integer> list = new ArrayList<>();
        for (int s : sticks) list.add(s);
        int cost = 0;
        while (list.size() > 1) {
            int a = 0, b = 1;
            if (list.get(b) < list.get(a)) { a = 1; b = 0; }
            for (int i = 2; i < list.size(); i++) {
                if (list.get(i) < list.get(a)) { b = a; a = i; }
                else if (list.get(i) < list.get(b)) b = i;
            }
            int joined = list.get(a) + list.get(b);
            cost += joined;
            int hi = Math.max(a, b), lo = Math.min(a, b);
            list.set(hi, list.get(list.size() - 1));
            list.remove(list.size() - 1);
            list.set(lo, joined);
        }
        return cost;
    }
}

2Optimal (min-heap greedy)

TimeO(n log n)n - 1 rounds, each with two pops and one push on a heap of at most n items.
SpaceO(n)The heap holds up to n sticks.

Same greedy rule, but keep the sticks in a min-heap so the two shortest come out in O(log n) and the joined stick goes back in O(log n). Joining the two shortest first keeps the longest sticks out of most joins, which minimises the total.

  1. Push every stick into a min-heap.
  2. While the heap has at least two sticks, pop a and b, add a + b to the cost and push a + b.
  3. Return the cost.
class Solution {
    public int connectSticks(int[] sticks) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int s : sticks) heap.offer(s);
        int cost = 0;
        while (heap.size() > 1) {
            int joined = heap.poll() + heap.poll();
            cost += joined;
            heap.offer(joined);
        }
        return cost;
    }
}

Edge cases to test

  • A single stick costs 0
  • Two sticks: the cost is simply their sum
  • All sticks equal
  • One huge stick with many small ones: the big one should be joined last

Hints

Hint 1

Every stick's length is paid once for each join it takes part in, directly or inside a bigger stick. Which sticks should take part in the fewest joins?

Hint 2

Joining the two shortest sticks available is always safe (the same argument as building a Huffman code).

Hint 3

You need the two smallest values repeatedly while inserting new ones. Which data structure does that in O(log n)?

FAQ

What is the best time complexity for Minimum Cost to Connect Sticks?

Optimal (min-heap greedy) runs in O(n log n) time and O(n) extra space. n - 1 rounds, each with two pops and one push on a heap of at most n items.

Which pattern does Minimum Cost to Connect Sticks use?

It is a heaps problem that uses the top k / kth largest / smallest pattern. Other problems with the same pattern: Kth Largest Element in an Array, Kth Largest Element in a Stream, Top K Frequent Words.

Is there a brute force solution for Minimum Cost to Connect Sticks?

Yes. Brute force (scan for the two shortest) takes O(n²) time and O(n) space. Apply the greedy rule directly with a plain list: every round, scan the list for the two shortest sticks, remove them, pay their sum and put the joined stick back.

Which edge cases should I test for Minimum Cost to Connect Sticks?

A single stick costs 0; Two sticks: the cost is simply their sum; All sticks equal; One huge stick with many small ones: the big one should be joined last.