LC 1167 Minimum Cost to Connect Sticks (C#)

https://leetcode.com/problems/minimum-cost-to-connect-sticks/

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.

Key Idea

The key thing to note here is that given a bunch of sticks the cost to combine any two sticks will be minimum for the two smallest sticks. Now you may immediately think of sorting the sticks and then just run through the array from smallest to largest combining sticks along the way. But, that would not be optimal because the key insight here is that once you combine two sticks you’ve got a new stick of a different length which may or may not be one of the two smallest. So what you’ve to do is to put the new stick back in the sticks and then pick up the two smallest sticks. This is what is called a Greedy algorithm because at each step it selects the best local approach.

How to do it in C#

We need a data structure which supports finding the minimum and removing it as quickly as possible. Heap data structure is exactly suited for this purpose — it supports adding elements and removing minimum in O(logN) time. C# doesn’t have a class for that exact purpose but it has SortedSet class which we can use as a heap (strictly speaking, it does a little more than a heap as it uses a red-black tree to maintain total sorted order but it’s better than implementing our own heap and the time complexity remains the same). But we need to be careful here because SortedSet doesn’t support duplicates and we could have multiple sticks of same length. So what we can do to get around that problem is create a wrapper class which holds a stick length and some other unique id to differentiate that stick from other sticks of same length. For that unique id one might think of using random numbers but that’s not suitable because two sticks might get the same random number as id and then SortedSet won’t add the second stick. Another option is to simply use an monotonically increasing number because all we care about is that the id is unique.

Note that SortedSet needs elements to be comparable so we will have to implement the IComparable interface which is simply a CompareTo method.

Code