LeetCode: Top K Frequent Element

https://leetcode.com/problems/top-k-frequent-elements/:

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

For example,
Given [1,1,1,2,2,3] and k = 2, return [1,2].

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.

Subscribe to see which companies asked this question

Hide Tags

 Hash Table Heap

Show Similar Problems

I did look at the hints for this problem, which suggested "Hash Tables" and "Heaps". With that information in mind then the solution becomes:
 - Create a class that implements a heap. In my case I had a Priority Queue class, which should do the trick
 - Add all the elements in the array to a hash table (add the count of elements to the hash table)
 - Go thru the hash table and add the elements to the priority queue
 - Pick the top K from the priority queue

It turns out that the solution runs in O(klogn), slightly better than O(nlogn). Cheers, Marcelo.

    public class Solution
    {
        public IList<int> TopKFrequent(int[] nums, int k)
        {
            Hashtable ht = new Hashtable();
            for (int i = 0; i < nums.Length; i++)
            {
                if (!ht.ContainsKey(nums[i])) ht.Add(nums[i], 0);
                ht[nums[i]] = (int)ht[nums[i]] + 1;
            }

            PriorityQueue pq = new PriorityQueue();

            foreach (int key in ht.Keys)
            {
                pq.Enqueue(key, (int)ht[key]);
            }

            List<int> retVal = new List<int>();
            for (int i = 0; i < k; i++)
            {
                retVal.Add((int)pq.Dequeue());
            }

            return retVal;
        }
    }
    public class PriorityQueue
    {
        public struct HeapEntry
        {
            private object item;
            private int priority;
            public HeapEntry(object item, int priority)
            {
                this.item = item;
                this.priority = priority;
            }
            public object Item
            {
                get
                {
                    return item;
                }
            }
            public int Priority
            {
                get
                {
                    return priority;
                }
            }
        }

        private int count;
        private int capacity;
        private HeapEntry[] heap;

        public int Count
        {
            get
            {
                return this.count;
            }
        }

        public PriorityQueue()
        {
            capacity = 100000;
            heap = new HeapEntry[capacity];
        }

        public object Dequeue()
        {
            object result = heap[0].Item;
            count--;
            trickleDown(0, heap[count]);
            return result;
        }

        public void Enqueue(object item, int priority)
        {
            count++;
            bubbleUp(count - 1, new HeapEntry(item, priority));
        }

        private void bubbleUp(int index, HeapEntry he)
        {
            int parent = (index - 1) / 2;
            // note: (index > 0) means there is a parent
            while ((index > 0) && (heap[parent].Priority < he.Priority))
            {
                heap[index] = heap[parent];
                index = parent;
                parent = (index - 1) / 2;
            }
            heap[index] = he;
        }

        private void trickleDown(int index, HeapEntry he)
        {
            int child = (index * 2) + 1;
            while (child < count)
            {
                if (((child + 1) < count) &&
                    (heap[child].Priority < heap[child + 1].Priority))
                {
                    child++;
                }
                heap[index] = heap[child];
                index = child;
                child = (index * 2) + 1;
            }
            bubbleUp(index, he);
        }
    }