LeetCode: Top K Frequent Elements C# https://leetcode.com/explore/interview/card/top-interview-questions-medium/110/sorting-and-searching/799


  Given a non-empty array of integers, return the k most frequent
  elements.
  
  Example 1:
  
  Input: nums = [1,1,1,2,2,3], k = 2 
  Output: [1,2] 
  
  Example 2:
  
  Input: nums = [1], k = 1 Output: [1] Note:
  
  You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
  Your algorithm's time complexity must be better than O(n log n), where
  n is the array's size.


using System.Collections.Generic;
using System.Linq;
using Microsoft.VisualStudio.TestTools.UnitTesting;


//good example for bucket sort
namespace SortingQuestions
{
    /// &lt;summary&gt;
    /// https://leetcode.com/explore/interview/card/top-interview-questions-medium/110/sorting-and-searching/799
    /// &lt;/summary&gt;
    [TestClass]
    public class TopKFrequentTest
    {
        [TestMethod]
        public void SimpleUseCaseTest()
        {
            int[] nums = { 1, 1, 1, 2, 2, 3 };
            int k = 2;
            int[] expected = { 1, 2 };
            CollectionAssert.AreEqual(expected, TopKFrequentClass.TopKFrequent(nums, k).ToArray());
        }
    }

    public class TopKFrequentClass
    {
        public static IList&lt;int&gt; TopKFrequent(int[] nums, int k)
        {
            Dictionary&lt;int, int&gt; number2Count = new Dictionary&lt;int, int&gt;();

            //we count how many times each number appears
            foreach (var num in nums)
            {
                number2Count.TryGetValue(num, out var temp);
                number2Count[num] = temp + 1;
            }

            List&lt;int&gt;[] bucket = new List&lt;int&gt;[nums.Length + 1];

            //we allocate an array in the size of the original list of numbers
            //we iterate all of the numbers and for add each number to the index in the array
            // the index represents how many times that number appeared
            //
            //    0 times -&gt; none
            //    1 times -&gt; number 3
            //    2 times -&gt; number 2
            //    3 times -&gt; number 1
            //    4 times -&gt; none
            //    5 times -&gt; none
            foreach (var key in number2Count.Keys)
            {
                int frequency = number2Count[key];
                if (bucket[frequency] == null)
                {
                    bucket[frequency] = new List&lt;int&gt;();
                }
                bucket[frequency].Add(key);
            }

            List&lt;int&gt; result = new List&lt;int&gt;();
            // we iterate the list bucket in reverse until the number of items in the result
            // list equals k, because we iterate in reserve we get the biggest numbers
            for (int pos = bucket.Length - 1; pos &gt;= 0 &amp;&amp; result.Count &lt; k; pos--)
            {
                if (bucket[pos] != null)
                {
                    result.AddRange(bucket[pos]);
                }
            }

            return result;
        }
    }
}


I really like this question and it took me some time to understand how to implement the bucket sorting.

I know I can also use MaxHeap. 
Since C# doesn't have a MaxHeap, do you think using a SortedList can help here somehow with the performance? (remember the question limitations)

I am mainly looking for performance optimizations.
I think that in terms of performance you'd be hard pressed to do better than a LINQ query.  Not only fast but very compact and relatively easy to understand.  It could look something like this:

public IList&lt;int&gt; TopKFrequent(int[] nums, int k) {
    var answer = (from int n in nums
                  group n by n into g
                  orderby g.Count() descending 
                  select g.Key).Take((k)).ToList();
    return answer;
}


For those that prefer method syntax here's the equivalent:

public IList&lt;int&gt; TopKFrequent(int[] nums, int k) {
    var answer = nums.GroupBy(n =&gt; n).OrderByDescending(g =&gt; g.Count()).Take(k).Select(g =&gt; g.Key).ToList();
    return answer;
}