Given an integer array nums and an integer k , return the k most frequent elements . You may return the answer in any order . Example 1: Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2] Example 2: Input: nums = , k = 1 Output:  Option 1 - Map to count + Sort to get top k - O(nlgn) We need to count what is the freq or how many times an item appeared. The obvious thing is for each item put it in a hashmap where Key is the item Value is the number of times it appeared Now the only thing that is left is to sort this hashtable. sorting is O(nlgn), placing everyting and counting is O(n) so this makes it overall O(nlgn) Option 2 - Improvement over option 1 - Instead of sorting use a Heap This is a common thing when you need to sort but the core of the problem is not sorting but as in this example only get top k then we could utilize a heap. We still build a map as in option 1 which takes O(n) this is the counting map. Building a heap heapify takes O(n) Remove each
Software Engineering Best Practices, System Design, High Scale, Algorithms, Math, Programming Languages, Statistics, Machine Learning, Databases, Front Ends, Frameworks, Low Level Machine Structure, Papers and Computing, Computer Science Book Reviews - Everything!