1167. Minimum Cost to Connect Sticks

• Time: $O(n\log n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution { public: int connectSticks(vector& sticks) { int ans = 0; priority_queue, greater<>> minHeap; for (const int stick : sticks) minHeap.push(stick); while (minHeap.size() > 1) { const int x = minHeap.top(); minHeap.pop(); const int y = minHeap.top(); minHeap.pop(); ans += x + y; minHeap.push(x + y); } return ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public int connectSticks(int[] sticks) { int ans = 0; Queue minHeap = new PriorityQueue<>(); for (final int stick : sticks) minHeap.offer(stick); while (minHeap.size() > 1) { final int x = minHeap.poll(); final int y = minHeap.poll(); ans += x + y; minHeap.offer(x + y); } return ans; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 class Solution: def connectSticks(self, sticks: List[int]) -> int: ans = 0 heapq.heapify(sticks) while len(sticks) > 1: x = heapq.heappop(sticks) y = heapq.heappop(sticks) ans += x + y heapq.heappush(sticks, x + y) return ans