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.

• Java
• C++
• Python
• Go
• TypeScript

• 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
  }
  

• function connectSticks(sticks: number[]): number {
      const pq = new Heap(sticks);
      let ans = 0;
      while (pq.size() > 1) {
          const x = pq.pop();
          const y = pq.pop();
          ans += x + y;
          pq.push(x + y);
      }
      return ans;
  }
  
  type Compare<T> = (lhs: T, rhs: T) => number;
  
  class Heap<T = number> {
      data: Array<T | null>;
      lt: (i: number, j: number) => boolean;
      constructor();
      constructor(data: T[]);
      constructor(compare: Compare<T>);
      constructor(data: T[], compare: Compare<T>);
      constructor(data: T[] | Compare<T>, compare?: (lhs: T, rhs: T) => number);
      constructor(
          data: T[] | Compare<T> = [],
          compare: Compare<T> = (lhs: T, rhs: T) =>
              lhs < rhs ? -1 : lhs > rhs ? 1 : 0,
      ) {
          if (typeof data === 'function') {
              compare = data;
              data = [];
          }
          this.data = [null, ...data];
          this.lt = (i, j) => compare(this.data[i]!, this.data[j]!) < 0;
          for (let i = this.size(); i > 0; i--) this.heapify(i);
      }
  
      size(): number {
          return this.data.length - 1;
      }
  
      push(v: T): void {
          this.data.push(v);
          let i = this.size();
          while (i >> 1 !== 0 && this.lt(i, i >> 1)) this.swap(i, (i >>= 1));
      }
  
      pop(): T {
          this.swap(1, this.size());
          const top = this.data.pop();
          this.heapify(1);
          return top!;
      }
  
      top(): T {
          return this.data[1]!;
      }
      heapify(i: number): void {
          while (true) {
              let min = i;
              const [l, r, n] = [i * 2, i * 2 + 1, this.data.length];
              if (l < n && this.lt(l, min)) min = l;
              if (r < n && this.lt(r, min)) min = r;
              if (min !== i) {
                  this.swap(i, min);
                  i = min;
              } else break;
          }
      }
  
      clear(): void {
          this.data = [null];
      }
  
      private swap(i: number, j: number): void {
          const d = this.data;
          [d[i], d[j]] = [d[j], d[i]];
      }
  }
  
  

All Problems

All Solutions