Top k frequent elements

Return the k values that occur most often. Count frequencies with a dictionary, then rank by count.

The idea

A dictionary turns "how many times does each value occur" into a single pass: look up the current count, add one, write it back. Once every distinct value has a count, sort those values by count and keep the first k.

Code

public static int[] TopKFrequent(int[] a, int k) {
    var freq = new Dictionary<int, int>();
    foreach (int x in a) freq[x] = freq.GetValueOrDefault(x) + 1;
    return freq.OrderByDescending(kv => kv.Value)
               .Take(k)
               .Select(kv => kv.Key).ToArray();
}

Tips

• GetValueOrDefault(x) returns 0 for a value not yet in the dictionary, so counting is one line instead of a TryGetValue-then-if pair.
• For a true O(n) version, bucket values into buckets[count] (an array of lists indexed by frequency) instead of sorting; frequencies only ever range from 1 to n.

In the .NET library

OrderByDescending costs O(d log d) for d distinct values, so the whole algorithm is O(n log n) in the worst case where every value is distinct. Bucketing by count removes that sort and gets to true O(n).