Code Implementation

import heapq

class Solution:
    def connectSticks(self, sticks):
        heapq.heapify(sticks)
        cost = 0
        while len(sticks) > 1:
            first = heapq.heappop(sticks)
            second = heapq.heappop(sticks)
            combined = first + second
            cost += combined
            heapq.heappush(sticks, combined)
        return cost
      

#include <vector>
#include <queue>
using namespace std;

class Solution {
public:
    int connectSticks(vector<int>& sticks) {
        priority_queue<int, vector<int>, greater<int>> minHeap(sticks.begin(), sticks.end());
        int cost = 0;
        while (minHeap.size() > 1) {
            int first = minHeap.top(); minHeap.pop();
            int second = minHeap.top(); minHeap.pop();
            int combined = first + second;
            cost += combined;
            minHeap.push(combined);
        }
        return cost;
    }
};
      

import java.util.PriorityQueue;

class Solution {
    public int connectSticks(int[] sticks) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int stick : sticks) minHeap.add(stick);
        int cost = 0;
        while (minHeap.size() > 1) {
            int first = minHeap.poll();
            int second = minHeap.poll();
            int combined = first + second;
            cost += combined;
            minHeap.add(combined);
        }
        return cost;
    }
}
      

// Min Heap implementation for JS
class MinHeap {
    constructor() { this.heap = []; }
    push(val) {
        this.heap.push(val);
        let i = this.heap.length - 1, p;
        while (i > 0 && this.heap[(p = ((i - 1) >> 1))] > this.heap[i]) {
            [this.heap[i], this.heap[p]] = [this.heap[p], this.heap[i]];
            i = p;
        }
    }
    pop() {
        if (this.heap.length === 1) return this.heap.pop();
        let top = this.heap[0], last = this.heap.pop();
        this.heap[0] = last;
        let i = 0, n = this.heap.length;
        while (true) {
            let l = 2 * i + 1, r = 2 * i + 2, smallest = i;
            if (l < n && this.heap[l] < this.heap[smallest]) smallest = l;
            if (r < n && this.heap[r] < this.heap[smallest]) smallest = r;
            if (smallest === i) break;
            [this.heap[i], this.heap[smallest]] = [this.heap[smallest], this.heap[i]];
            i = smallest;
        }
        return top;
    }
    size() { return this.heap.length; }
}

var connectSticks = function(sticks) {
    let heap = new MinHeap();
    for (let stick of sticks) heap.push(stick);
    let cost = 0;
    while (heap.size() > 1) {
        let first = heap.pop();
        let second = heap.pop();
        let combined = first + second;
        cost += combined;
        heap.push(combined);
    }
    return cost;
};
      

Problem Description

You are given an array sticks, where each element represents the length of a stick. Your task is to connect all the sticks into one. You can only connect two sticks at a time, and the cost of connecting two sticks is equal to the sum of their lengths. The resulting stick is then available to be connected with others. Return the minimum total cost required to connect all the sticks into one stick.

• Each connection must combine exactly two sticks.
• Each stick can only be used once per connection, but is reintroduced as a new stick after a merge.
• There is always exactly one valid way to connect all the sticks (since we must connect until only one stick remains).
• Input: sticks is an array of positive integers.
• Output: An integer representing the minimal total cost.

Thought Process

At first glance, it seems like we might connect sticks in any order, but the cost depends on which sticks we combine first. If we always combine the largest sticks, the new stick will be big and expensive to connect later, increasing total cost. Brute force would try all possible pairings, but that's not practical for even medium-sized inputs.

A better approach is to always connect the two smallest sticks first, so the resulting stick is as small as possible and doesn't add too much cost when used in future connections. This is a greedy strategy, similar to the one used in optimal merge patterns (like Huffman coding).

To efficiently find the smallest sticks, we can use a min-heap (priority queue), which allows us to always remove the two smallest elements quickly.

Solution Approach

• Step 1: Insert all stick lengths into a min-heap (priority queue). This allows us to always access the two shortest sticks easily.
• Step 2: While there is more than one stick in the heap:
  • Remove the two shortest sticks from the heap.
  • Add their lengths to get the cost of this connection.
  • Add this cost to a running total.
  • Insert the new combined stick back into the heap.
• Step 3: Repeat until only one stick remains. The running total is the minimum cost to connect all sticks.

We use a min-heap because it gives us O(log n) insertions and removals of the smallest elements, which is much faster than searching through an array each time.

Example Walkthrough

Let's say sticks = [2, 4, 3].

1. Put all sticks into a min-heap: [2, 3, 4] (heap order may vary, but smallest is always on top).
2. Pop 2 and 3 (the smallest): cost = 2 + 3 = 5. Add 5 to total cost (total = 5).
3. Push 5 back into the heap: [4, 5].
4. Pop 4 and 5: cost = 4 + 5 = 9. Add 9 to total cost (total = 14).
5. Push 9 back. Only one stick left, so we're done.
6. Final answer: 14

Notice how always combining the smallest sticks keeps the costs low at each step.

Time and Space Complexity

• Brute-force approach: Trying all possible pairings would be factorial time, O(n!), which is infeasible for large n.
• Optimized (heap-based) approach:
  • Building the heap: O(n)
  • Each of n-1 connections: removing two elements and adding one, each O(log n)
  • Total time: O(n log n)
  • Space: O(n) for the heap

The heap ensures efficient access to the smallest sticks at every step, making this approach optimal.

Summary

The key to minimizing the total cost is always connecting the two shortest sticks first, which is efficiently managed by a min-heap. This greedy approach ensures that each new stick added is as small as possible, keeping future connection costs low. The heap-based algorithm is both elegant and efficient, running in O(n log n) time and requiring only O(n) space.