Minimum Cost to Connect Sticks

1. Define the problem

You have sticks with positive whole-number lengths. You may join any two sticks into one longer stick, and joining sticks of length x and y costs x + y. Keep joining until only one stick is left, and return the smallest total cost possible. The trick is that every join you do early gets paid for again inside every later join, so you should always join the two shortest sticks available . A min-heap hands you those two shortest sticks straight away, and the joined stick goes back into the heap to be considered again.

Constraints

1 ≤ sticks.length ≤ 10⁴
1 ≤ sticks_i ≤ 10⁴
A single stick needs no joining, so the cost is 0

Example

Inputsticks = [1, 8, 3, 5]

Output30

Explanation Join 1 and 3 for a cost of 4, giving sticks 4, 5 and 8. Join 4 and 5 for a cost of 9, giving 8 and 9. Join 8 and 9 for a cost of 17. The total is 4 + 9 + 17 = 30.

2. Know the words first

In plain terms

Heap: A container that always knows its best item, where best means smallest or largest depending on how you set it up. Adding an item or taking the best item out costs about log n steps, and you never have to sort the whole collection.
Backing array: A heap is stored as one plain list. The item at position i keeps its parent at position (i - 1) / 2 rounded down, and its two children at positions 2i + 1 and 2i + 2. That is why every picture below is a row of numbered boxes.
Min-heap: A heap whose best item is the smallest one. Looking at the top always shows you the smallest value still inside.
Greedy choice: Picking whatever looks best right now and never going back. Here, joining the two shortest sticks at every turn happens to give the cheapest total.

3. Visualize the solution

The row of boxes is the backing array of the min-heap for sticks = [1, 8, 3, 5]

Statusbuild

Push all four sticks into the min-heap. Slot 0 holds the shortest stick, 1.

What happens in this step

sticks = [1, 8, 3, 5]
backing array = [1, 5, 3, 8]
cost = 0

Slot 0 holds 1 and its children in slots 1 and 2 hold 5 and 3.
Neither child is smaller than its parent, so this is a valid min-heap.

Step 1 of 5

Steps to visualize

Each box is one slot of the list that stores the heap. Slot 0 always holds the shortest stick.
A slot showing — is unused, because two sticks came out and only one went back in.
On every turn, pop twice to get the two shortest sticks, add their lengths to the running cost, and push the joined stick back.
The heap shrinks by one stick per turn, so four sticks take three turns.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

The row of boxes is the backing array of the min-heap for sticks = [1, 8, 3, 5]

Statusbuild

Push all four sticks into the min-heap. Slot 0 holds the shortest stick, 1.

What happens in this step

sticks = [1, 8, 3, 5]
backing array = [1, 5, 3, 8]
cost = 0

Slot 0 holds 1 and its children in slots 1 and 2 hold 5 and 3.
Neither child is smaller than its parent, so this is a valid min-heap.

Step 1 of 5

5. Solution

Solution

solution.tsTypeScript

function connectSticks(sticks) {
  if (sticks.length < 2) return 0;

  const heap = new Heap((a, b) => a - b);

  for (const stick of sticks) {
    heap.push(stick);
  }

  let cost = 0;

  while (heap.size() > 1) {
    const first = heap.pop();
    const second = heap.pop();
    const joined = first + second;
    cost += joined;
    heap.push(joined);
  }

  return cost;
}

class Heap {
  constructor(compare) {
    this.items = [];
    this.compare = compare;
  }

  size() {
    return this.items.length;
  }

  peek() {
    return this.items[0];
  }

  push(value) {
    this.items.push(value);
    let child = this.items.length - 1;

    while (child > 0) {
      const parent = (child - 1) >> 1;
      if (this.compare(this.items[child], this.items[parent]) >= 0) break;
      const swap = this.items[child];
      this.items[child] = this.items[parent];
      this.items[parent] = swap;
      child = parent;
    }
  }

  pop() {
    const top = this.items[0];
    const last = this.items.pop();

    if (this.items.length > 0) {
      this.items[0] = last;
      let parent = 0;

      while (true) {
        const left = parent * 2 + 1;
        const right = parent * 2 + 2;
        let best = parent;

        if (left < this.items.length && this.compare(this.items[left], this.items[best]) < 0) best = left;
        if (right < this.items.length && this.compare(this.items[right], this.items[best]) < 0) best = right;
        if (best === parent) break;

        const swap = this.items[parent];
        this.items[parent] = this.items[best];
        this.items[best] = swap;
        parent = best;
      }
    }

    return top;
  }
}

Time: O(n log n)
Space: O(n)

6. Test cases

Test cases

Input	Expected	Covers
`sticks = [1, 8, 3, 5]`	`30`	example from the docstring
`sticks = [2, 4, 3]`	`14`	joining 2 and 3 first costs 5, then 5 and 4 costs 9
`sticks = [5]`	`0`	nothing to join, so the cost is zero
`sticks = []`	`0`	empty input
`sticks = [1, 1, 1, 1]`	`8`	duplicate lengths
`sticks = [20, 4, 8, 2]`	`54`	one very long stick that should be joined last

Minimum Cost to Connect Sticks