Top K Most Frequent Numbers using Linq Orderby (Heap-less Solution)

gistfile1.txt

/*

Given an unsorted array of numbers, find the top ‘K’ frequently occurring numbers in it.

Example:

Input: [1, 3, 5, 12, 11, 12, 11], K = 2
Output: [12, 11]

Approach:
// Create a dictionary to hold numCount KeyValuePairs
// Iterate through entire input array, adding/incrementing key value pairs // O(N), O(N)
// Create a list of keyvaluepairs, which is a sorted list version of the dictionary, orderbydescending // O(n log n), O(N)
// Add the first K elements from that list, into a result list of numbers // O(K), O(K)
// return the result list

Complexity:
// O(N + N log N + K) => O (n log n + k)
// O(N + N + K) => O(N + K)

*/

using System;
using System.Collections.Generic;
using System.Linq;

class Solution
{
    static void Main(string[] args)
    {
        int[] example = new int[] {1, 3, 5, 12, 11, 12, 11};
        List<int> answer = FindTopKFrequentNumbers(example,2);
        foreach (int number in answer)
        {
            Console.Write(number + " ");
        }
    }
    
    public static List<int> FindTopKFrequentNumbers (int[] input, int k)
    {
        List<int> result = new List<int>();
        Dictionary<int, int> numCounts = new Dictionary<int, int>();
    
        foreach (int number in input)
        {
            if (!numCounts.ContainsKey(number))
            {
                numCounts.Add(number,0);
            }
            numCounts[number]++;
        }
        
        List<KeyValuePair<int, int>> sortedNumCounts = numCounts.OrderByDescending(numCount => numCount.Value).ToList();
        
        
        for(int i = 0; i < k; i++)
        {
            result.Add(sortedNumCounts[i].Key);
        }
        
        return result;
    }
}