Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1167.html

1167. Minimum Cost to Connect Sticks

Level

Medium

Description

You have some sticks with positive integer lengths.

You can connect any two sticks of lengths X and Y into one stick by paying a cost of X + Y. You perform this action until there is one stick remaining.

Return the minimum cost of connecting all the given sticks into one stick in this way.

Example 1:

Input: sticks = [2,4,3]

Output: 14

Example 2:

Input: sticks = [1,8,3,5]

Output: 30

Constraints:

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

Solution

Use the greedy approach. Use a priority queue to store all elements in sticks, where the minimum element is polled from the priority queue each time. While the priority queue contains at least 2 elements, poll 2 elements, calculate the sum, add the sum to the cost, and offer the sum to the priority queue. Repeat the process until the priority queue only contains 1 element. Then return the cost.

  • class Solution {
        public int connectSticks(int[] sticks) {
            PriorityQueue<Integer> priorityQueue = new PriorityQueue<Integer>();
            for (int stick : sticks)
                priorityQueue.offer(stick);
            int cost = 0;
            while (priorityQueue.size() > 1) {
                int stick1 = priorityQueue.poll();
                int stick2 = priorityQueue.poll();
                int sum = stick1 + stick2;
                cost += sum;
                priorityQueue.offer(sum);
            }
            return cost;
        }
    }
    
  • // OJ: https://leetcode.com/problems/minimum-cost-to-connect-sticks/
    // Time: O(NlogN)
    // Space: O(N)
    class Solution {
    public:
        int connectSticks(vector<int>& A) {
            priority_queue<int, vector<int>, greater<>> pq;
            for (int n : A) pq.push(n);
            int ans = 0;
            while (pq.size() > 1) {
                int a = pq.top();
                pq.pop();
                int b = pq.top();
                pq.pop();
                pq.push(a + b);
                ans += a + b;
            }
            return ans;
        }
    };
    
  • class Solution:
        def connectSticks(self, sticks: List[int]) -> int:
            h = []
            for s in sticks:
                heappush(h, s)
            res = 0
            while len(h) > 1:
                val = heappop(h) + heappop(h)
                res += val
                heappush(h, val)
            return res
    
    
    
  • func connectSticks(sticks []int) int {
    	h := IntHeap(sticks)
    	heap.Init(&h)
    	res := 0
    	for h.Len() > 1 {
    		val := heap.Pop(&h).(int)
    		val += heap.Pop(&h).(int)
    		res += val
    		heap.Push(&h, val)
    	}
    	return res
    }
    
    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 interface{}) {
    	*h = append(*h, x.(int))
    }
    func (h *IntHeap) Pop() interface{} {
    	old := *h
    	n := len(old)
    	x := old[n-1]
    	*h = old[0 : n-1]
    	return x
    }
    

All Problems

All Solutions