{x}
blog image

Minimum Cost to Connect Sticks

Solution Explanation: Minimum Cost to Connect Sticks

This problem asks to find the minimum cost to connect a given set of sticks into a single stick. The cost to connect two sticks is the sum of their lengths. A greedy approach provides an optimal solution.

Greedy Approach:

The core idea is to repeatedly connect the two shortest sticks. This is a greedy strategy because connecting the shortest sticks first minimizes the immediate cost and, surprisingly, leads to the overall minimum cost.

Algorithm:

  1. Initialization: Use a min-heap (priority queue) to store the stick lengths. A min-heap efficiently provides the smallest elements.

  2. Iteration: While there is more than one stick in the heap:

    • Extract the two smallest sticks from the heap.
    • Calculate the cost of connecting them (sum of their lengths).
    • Add this cost to the total cost.
    • Create a new stick with the combined length and add it back to the heap.

  3. Result: The total cost accumulated after all sticks are connected is the minimum cost.

Time Complexity: The heappop and heappush operations in the priority queue take O(log n) time each. We perform these operations at most n-1 times (where n is the number of sticks). Therefore, the overall time complexity is O(n log n).

Space Complexity: The priority queue requires O(n) space to store the sticks.

Code Implementation (Python):

import heapq
 
class Solution:
    def connectSticks(self, sticks: List[int]) -> int:
        heapq.heapify(sticks)  # Convert list to a min-heap in-place
        total_cost = 0
        while len(sticks) > 1:
            shortest1 = heapq.heappop(sticks)
            shortest2 = heapq.heappop(sticks)
            cost = shortest1 + shortest2
            total_cost += cost
            heapq.heappush(sticks, cost)  # Add the combined stick back
        return total_cost

Code Implementation (Java):

import java.util.PriorityQueue;
 
class Solution {
    public int connectSticks(int[] sticks) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int stick : sticks) {
            pq.offer(stick);
        }
        int totalCost = 0;
        while (pq.size() > 1) {
            int shortest1 = pq.poll();
            int shortest2 = pq.poll();
            int cost = shortest1 + shortest2;
            totalCost += cost;
            pq.offer(cost);
        }
        return totalCost;
    }
}

Code Implementation (C++):

#include <queue>
#include <vector>
 
using namespace std;
 
class Solution {
public:
    int connectSticks(vector<int>& sticks) {
        priority_queue<int, vector<int>, greater<int>> pq(sticks.begin(), sticks.end()); //Min Heap
        int totalCost = 0;
        while (pq.size() > 1) {
            int shortest1 = pq.top(); pq.pop();
            int shortest2 = pq.top(); pq.pop();
            int cost = shortest1 + shortest2;
            totalCost += cost;
            pq.push(cost);
        }
        return totalCost;
    }
};

Code Implementation (Go):

import (
	"container/heap"
	"sort"
)
 
type IntHeap []int
 
func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
 
func (h *IntHeap) Push(x any) {
	*h = append(*h, x.(int))
}
 
func (h *IntHeap) Pop() any {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}
 
func connectSticks(sticks []int) int {
	h := &IntHeap{}
	heap.Init(h)
	for _, s := range sticks {
		heap.Push(h, s)
	}
 
	totalCost := 0
	for h.Len() > 1 {
		shortest1 := heap.Pop(h).(int)
		shortest2 := heap.Pop(h).(int)
		totalCost += shortest1 + shortest2
		heap.Push(h, shortest1+shortest2)
	}
	return totalCost
}

Code Implementation (TypeScript): (Requires a custom heap implementation, which is omitted for brevity but easily found online.) The logic would be nearly identical to the Python or Java examples.

The provided code examples in various languages demonstrate the implementation of the greedy algorithm using a min-heap data structure. The core logic remains the same across languages, highlighting the elegance and efficiency of this approach.