Top amazon questions — Minimum Cost to Connect Sticks [LC-1167]

Amazon’s logo

This is an explanation on how to solve Minimum Cost to Connect Sticks from the Top amazon questions section in leetcode.

The question asks to count the total cost to connect sticks. Where a stick is an integer in an array. To “paste” two sticks we pay the sum of their lengths, we want to find the minimum cost to paste all sticks together.

sticks = [2,4,3]
result = 14 

Solution

A greedy approach is the optimal approach for this problem. This claim can be backed by a greedy correctness proof. However, I won’t go into that level of detail. The main intuition for this problem is that choosing the two smallest sticks results in an increase less than or equal to adding any two other sticks in every iteration of the algorithm.

Now that we have chosen an approach to solve the problem, its time to build the solution. We want to have fast access to the smallest two sticks in every iterations, to achieve this can use a min priority queue to contain the sticks. This way we don’t have to sort the list every time we merge two sticks to find the new smallest sticks. We repeat this procedure n-1 times until we have 1 stick. The solution will have a nlogn runtime.

Code

class Solution {
public:
    int connectSticks(vector<int>& sticks) {
    
      priority_queue<int, vector<int>, greater<int> > q;
 
      for(int stick:sticks)
          q.push(stick);
      
      int count = 0, a, b;
      
      while(q.size()>1){
        a = q.top();
        q.pop();
        b = q.top();
        q.pop();
        count+=a+b;
        q.push(a+b);
      }
      return count;
      
      
    }
};