[Uber] Top K Frequent Elements

Problem: Given a non-empty array of integers, return the k most frequent elements.

Example:

Input: nums = [1,1,1,1,3,2,2,3,3], k = 2
Output: [1,3]

Approach: We can use the quick select approach which we used in our previous problem of getting the kth smallest number in an unsorted array. Here are the few points which we need to take care:

1. Partial sorting will be done based on frequency of the number so to efficiently get the frequency of a number, we can maintain a hash with key as element of input array and value as the frequency of this number.
2. Here we need to get rid of duplicates as we need to return the top k frequent elements, right. That means we need to apply quick select on an array containing unique numbers of input array.
3. We need to get the top k frequent elements that means we just need to find (n - k)th less frequent element. Once we get it, our answer will be unique[n-k...n] where unique is the array of unique numbers of input array.

That's all!

Implementation in C#:

    public int[] TopKFrequent(int[] nums, int k) 

    {

        Dictionary<int, int> frequencies = new Dictionary<int, int>();

        foreach(int num in nums)

        {

            if (!frequencies.ContainsKey(num))

            {

                frequencies.Add(num, 0);

            }

            ++frequencies[num];

        }

        int[] uniqueNums = frequencies.Keys.ToArray();

        return this.FindKMostFrequentElements(uniqueNums, uniqueNums.Length - k + 1, 0, uniqueNums.Length - 1, frequencies, k);

    }

    

    private int[] FindKMostFrequentElements(int[] uniqueNums, int k, int start, int end, Dictionary<int, int> frequencies, int length)

    {

        if (k > 0 && k <= end - start + 1)

        {

            int pos = this.RandomPartition(uniqueNums, start, end, frequencies);

            if (pos - start + 1 == k)

            {

                return this.SubArray(uniqueNums, pos, length);

            }

            else if (pos - start + 1 > k)

            {

                return this.FindKMostFrequentElements(uniqueNums, k, start, pos - 1, frequencies, length);

            }

            return this.FindKMostFrequentElements(uniqueNums, k - (pos - start + 1), pos + 1, end, frequencies, length);

        }

        return new int[] { };

    }

    

    private int RandomPartition(int[] uniqueNums, int start, int end, Dictionary<int, int> frequencies)

    {

        int pivot = new Random().Next(start, end);

        this.SwapElements(uniqueNums, pivot, end);

        return this.Partition(uniqueNums, start, end, frequencies);

    }

    

    private int Partition(int[] uniqueNums, int start, int end, Dictionary<int, int> frequencies)

    {

        int x = uniqueNums[end];

        int i = start;

        for (int j = start; j < end; ++j)

        {

            if (frequencies[uniqueNums[j]] < frequencies[x])

            {

                this.SwapElements(uniqueNums, i, j);

                ++i;

            }

        }

        this.SwapElements(uniqueNums, i, end); 

        return i;

    }

    

    public void SwapElements(int[] arr, int i, int j)

    {

        int temp = arr[i];

        arr[i] = arr[j];

        arr[j] = temp;

    }

    

    public int[] SubArray(int[] array, int startIndex, int length)

    {

        int[] subArray = new int[length];

        Array.Copy(array, startIndex, subArray, 0, length);

        return subArray;

    }

Complexity: O(n)