1046. Last Stone Weight

Here is my discussion post.

The algorithm can be solved using minimum heap. To convert maximum two numbers to minimum two numbers, negative value is used instead.

Here are highlights:

1. Understand C# SortedDictionary can be used to impelement minimum heap first;
2. Apply all ement value to negative one, so maximum heap turns into a minimum heap problem;
3. Get familiar with IEnumberable First API and it can be used to get the minimum one from the heap.

public class Solution {
    /// <summary>
        /// Oct.4, 2019
        /// Implement a maximum heap - 
        /// what I can do is to use negative value 
        /// </summary>
        /// <param name="stones"></param>
        /// <returns></returns>
        public int LastStoneWeight(int[] stones)
        {
            var sorted = new SortedDictionary<int, int>();

            // put all numbers into minimum heap - default - negative value
            foreach (var number in stones)
            {
                var key = number * (-1);
                if (!sorted.ContainsKey(key))
                {
                    sorted.Add(key, 0);
                }

                sorted[key]++; 
            }

            while (!((sorted.Keys.Count == 1 && sorted[sorted.Keys.ToList()[0]] == 1) || sorted.Keys.Count == 0))
            {
                // get minimum two values from minimum heap
                var key = sorted.Keys.First();
                var hasAtLeastTwo = sorted[key] > 1;
                if (hasAtLeastTwo)
                {
                    sorted[key] -= 2;
                    if(sorted[key] == 0)
                    {
                        sorted.Remove(key);
                    }
                }
                else 
                {
                    var minimum = key;
                    sorted.Remove(key);
                    var next = sorted.Keys.First();
                    sorted[next]--;

                    if (sorted[next] == 0)
                    {
                        sorted.Remove(next);
                    }

                    var diff = Math.Abs(minimum - next);
                    var newKey = diff * (-1);

                    if (newKey == 0)
                        continue;

                    if (!sorted.ContainsKey(newKey))
                    {
                        sorted.Add(newKey, 0);
                    }

                    sorted[newKey]++;
                }                
            }

            if (sorted.Keys.Count == 0)
                return 0;

            return sorted.Keys.ToList()[0] * (-1);
        }
}