# Top K Frequent Elements **Difficulty:** MEDIUM [External](https://leetcode.com/problems/top-k-frequent-elements) Canonical: https://scaleengineer.com/dsa/problems/top-k-frequent-elements **Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting) **Algorithms:** [Divide and Conquer](https://scaleengineer.com/algorithms/divide-and-conquer), [Sorting](https://scaleengineer.com/algorithms/sorting), [Bucket Sort](https://scaleengineer.com/algorithms/bucket-sort), [Quickselect](https://scaleengineer.com/algorithms/quickselect) **Data structures:** Array, Hash Table, Heap (Priority Queue) **Companies:** [Atlassian](https://scaleengineer.com/companies/atlassian), [Avito](https://scaleengineer.com/companies/avito), [ByteDance](https://scaleengineer.com/companies/bytedance), [Chewy](https://scaleengineer.com/companies/chewy), [Cisco](https://scaleengineer.com/companies/cisco), [Docusign](https://scaleengineer.com/companies/docusign), [DoorDash](https://scaleengineer.com/companies/doordash), [Dropbox](https://scaleengineer.com/companies/dropbox), [EPAM Systems](https://scaleengineer.com/companies/epam-systems), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Hubspot](https://scaleengineer.com/companies/hubspot), [Intuit](https://scaleengineer.com/companies/intuit), [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan), [Nutanix](https://scaleengineer.com/companies/nutanix), [PayPal](https://scaleengineer.com/companies/paypal), [Snowflake](https://scaleengineer.com/companies/snowflake), [SoFi](https://scaleengineer.com/companies/sofi), [Visa](https://scaleengineer.com/companies/visa), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Yandex](https://scaleengineer.com/companies/yandex), [Yelp](https://scaleengineer.com/companies/yelp), [eBay](https://scaleengineer.com/companies/ebay), [Netflix](https://scaleengineer.com/companies/netflix), [Salesforce](https://scaleengineer.com/companies/salesforce), [Tesla](https://scaleengineer.com/companies/tesla), [Snap](https://scaleengineer.com/companies/snap), [Microstrategy](https://scaleengineer.com/companies/microstrategy), [Arista Networks](https://scaleengineer.com/companies/arista-networks), [Pinterest](https://scaleengineer.com/companies/pinterest), [Twilio](https://scaleengineer.com/companies/twilio), [Pocket Gems](https://scaleengineer.com/companies/pocket-gems), [Roku](https://scaleengineer.com/companies/roku), [Smartsheet](https://scaleengineer.com/companies/smartsheet), [Robinhood](https://scaleengineer.com/companies/robinhood), [Tiger Analytics](https://scaleengineer.com/companies/tiger-analytics) --- ## Problem 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 = [1], k = 1 **Output:** [1] **Constraints:** * `1 <= nums.length <= 105` * `-104 <= nums[i] <= 104` * `k` is in the range `[1, the number of unique elements in the array]`. * It is **guaranteed** that the answer is **unique**. **Follow up:** Your algorithm's time complexity must be better than `O(n log n)`, where n is the array's size. # Approaches ## Sorting by Frequency This approach first calculates the frequency of each element using a hash map. Then, it converts the map entries into a list, sorts this list based on frequencies in descending order, and finally picks the first `k` elements. **Time:** O(M log M), where N is the number of elements in `nums` and M is the number of unique elements. In the worst case, M can be equal to N, leading to O(N log N). The steps are: O(N) to build the frequency map and O(M log M) to sort. · **Space:** O(M), where M is the number of unique elements. This space is used for the frequency map and the list used for sorting. In the worst case, M can be N, so the space complexity is O(N). **Pros:** Relatively straightforward to understand and implement.; Leverages standard library sorting functions. **Cons:** The time complexity of O(N log N) does not meet the follow-up requirement for a better-than-O(N log N) solution.; Sorting all unique elements is unnecessary work when we only need the top `k`. ### Explanation The most intuitive approach is to first determine the frequency of every element, and then sort the elements based on these frequencies. 1. **Count Frequencies**: We use a `HashMap` where keys are the numbers from the input array and values are their frequencies. We iterate through the `nums` array once to populate this map. 2. **Sort**: We convert the map's entries into a list. Then, we sort this list in descending order based on the frequency values. A custom comparator or a lambda expression is used for the sorting logic. 3. **Extract Top K**: After sorting, the `k` most frequent elements will be the first `k` elements in the sorted list. We create a result array of size `k` and populate it with these elements. ```java import java.util.*; class Solution { public int[] topKFrequent(int[] nums, int k) { if (k == nums.length) { return nums; } // 1. Build hash map: character -> its frequency Map count = new HashMap<>(); for (int n : nums) { count.put(n, count.getOrDefault(n, 0) + 1); } // 2. Create a list of map entries List> list = new ArrayList<>(count.entrySet()); // 3. Sort the list by frequency in descending order list.sort((a, b) -> b.getValue().compareTo(a.getValue())); // 4. Build the result array int[] result = new int[k]; for (int i = 0; i < k; i++) { result[i] = list.get(i).getKey(); } return result; } } ``` ### Algorithm - Create a `HashMap` to store the frequency of each number. - Iterate through the input array `nums` and populate the frequency map. - Convert the map's entry set into a `List`. - Sort the list in descending order based on the frequency (the map's value). - Extract the keys of the first `k` entries from the sorted list. - Return the resulting array of `k` elements. ## Using a Min-Heap This approach improves upon sorting by using a min-heap of size `k`. After counting frequencies, we iterate through the unique elements. For each element, we add it to the heap. If the heap size exceeds `k`, we remove the element with the smallest frequency. This ensures the heap always holds the `k` most frequent elements seen so far. **Time:** O(N log k). Building the frequency map takes O(N). Then, we iterate through M unique elements (M <= N). For each element, we perform a heap insertion which takes O(log k). This results in a total time of O(N + M log k). Since M is at most N, the complexity is dominated by O(N log k). · **Space:** O(M + k), where M is the number of unique elements. O(M) for the frequency map and O(k) for the heap. In the worst case, this is O(N). **Pros:** More efficient than the sorting approach, with a time complexity of O(N log k).; Satisfies the follow-up requirement as O(N log k) is better than O(N log N) when k is smaller than N. **Cons:** Can be slightly slower than the O(N) approaches if `k` is large (close to N). ### Explanation To avoid the cost of sorting all M unique elements, we can use a data structure that maintains just the top `k` elements at any time. A min-heap is perfect for this. 1. **Count Frequencies**: As with the previous approach, we first build a `HashMap` to store the frequency of each number. This takes O(N) time. 2. **Use a Min-Heap**: We initialize a min-heap (a `PriorityQueue` in Java). The heap's comparator will order elements based on their frequency, keeping the element with the *minimum* frequency at the top. 3. **Maintain Heap of Size k**: We iterate through our frequency map. For each number, we add it to the heap. Immediately after adding, we check if the heap's size has grown larger than `k`. If it has, we remove the root element using `poll()`. Since it's a min-heap, this removes the element with the lowest frequency among those in the heap. This process ensures that the heap only contains the `k` most frequent elements encountered so far. 4. **Extract Result**: After iterating through all unique numbers, the heap holds the `k` most frequent elements in the entire array. We can then extract these elements from the heap to form our result array. ```java import java.util.*; class Solution { public int[] topKFrequent(int[] nums, int k) { // 1. Build hash map: character -> its frequency Map count = new HashMap<>(); for (int n : nums) { count.put(n, count.getOrDefault(n, 0) + 1); } // 2. Initialize a min-heap with a comparator for frequency PriorityQueue heap = new PriorityQueue<>((n1, n2) -> count.get(n1) - count.get(n2)); // 3. Maintain a heap of size k for (int n : count.keySet()) { heap.add(n); if (heap.size() > k) { heap.poll(); } } // 4. Build the result array from the heap int[] result = new int[k]; for (int i = k - 1; i >= 0; i--) { result[i] = heap.poll(); } return result; } } ``` ### Algorithm - Create a `HashMap` to store the frequency of each number. - Iterate through `nums` to populate the frequency map. - Initialize a min-heap (`PriorityQueue`) of size `k`. The comparison will be based on element frequencies. - Iterate through the keys (unique numbers) of the frequency map. - For each number, add it to the heap. - If the heap's size exceeds `k`, remove the top element (which has the minimum frequency). - After the loop, the heap contains the `k` most frequent elements. Extract them into an array and return it. ## Bucket Sort This is a linear time complexity approach. After counting frequencies, we use an array of lists (buckets), where the index of the array corresponds to a frequency. We place each number in the bucket corresponding to its frequency. Finally, we iterate through the buckets from highest frequency to lowest, collecting elements until we have `k` of them. **Time:** O(N). Building the frequency map is O(N). Populating the buckets takes O(M) time, where M is the number of unique elements (M <= N). Iterating through the buckets to get the final result takes O(N) in the worst case. Thus, the total time complexity is O(N). · **Space:** O(N + M) which simplifies to O(N). O(M) for the frequency map and O(N) for the `buckets` array. The total number of items stored across all buckets is M. **Pros:** Optimal time complexity of O(N).; Guaranteed linear time performance, unlike Quickselect which has a worst-case of O(N^2).; Conceptually simple, using a direct mapping from frequency to elements. **Cons:** Can use a significant amount of space, O(N), for the buckets array, even if the number of unique elements is small. ### Explanation This approach achieves a linear time complexity by adapting the idea of Bucket Sort. Instead of sorting, we group elements by their frequency. 1. **Count Frequencies**: Same as before, we use a `HashMap` to count the frequency of each number in O(N) time. 2. **Create Buckets**: We create an array of lists, let's call it `buckets`. The index of this array will represent the frequency of an element. For example, `buckets[3]` will hold a list of all numbers that appear 3 times. The size of this array needs to be `nums.length + 1`, as the maximum possible frequency is `nums.length` (if all elements are the same). 3. **Populate Buckets**: We iterate through our frequency map. For each `(number, frequency)` pair, we add the `number` to the list at `buckets[frequency]`. 4. **Gather Top K**: To find the top `k` frequent elements, we iterate through the `buckets` array from the end (highest frequency) down to the beginning. We add the elements from each bucket to our result list. We stop as soon as our result list contains `k` elements. This method avoids any comparison-based sorting, leading to a very efficient O(N) time complexity. ```java import java.util.*; class Solution { public int[] topKFrequent(int[] nums, int k) { // 1. Build hash map: character -> its frequency Map count = new HashMap<>(); for (int n : nums) { count.put(n, count.getOrDefault(n, 0) + 1); } // 2. Create buckets for frequencies // The index of the array is the frequency. List[] buckets = new List[nums.length + 1]; for (int i = 0; i < buckets.length; i++) { buckets[i] = new ArrayList<>(); } // 3. Populate buckets for (int num : count.keySet()) { int frequency = count.get(num); buckets[frequency].add(num); } // 4. Gather top k elements from buckets List resultList = new ArrayList<>(); for (int i = buckets.length - 1; i >= 1 && resultList.size() < k; i--) { if (!buckets[i].isEmpty()) { resultList.addAll(buckets[i]); } } // 5. Convert to array int[] result = new int[k]; for (int i = 0; i < k; i++) { result[i] = resultList.get(i); } return result; } } ``` ### Algorithm - Create a `HashMap` to store the frequency of each number. - Iterate through `nums` to populate the frequency map. - Create an array of lists called `buckets`. The size of this array should be `n + 1`, where `n` is the length of `nums`. - Iterate through the frequency map. For each number, add it to the list at the index corresponding to its frequency in the `buckets` array. - Initialize an empty result list. - Iterate through the `buckets` array in reverse order (from highest frequency to lowest). - Add the numbers from each bucket to the result list until the list's size is `k`. - Return the first `k` elements from the result list as an array. # Solutions ### Java ```java import java.util.* ; public class Top_K_Frequent_Elements { // ref: https://leetcode.com/problems/top-k-frequent-elements/solution/ class Solution_official_oN { int [] unique ; Map < Integer , Integer > count ; public void swap ( int a , int b ) { int tmp = unique [ a ]; unique [ a ] = unique [ b ]; unique [ b ] = tmp ; } public int partition ( int left , int right , int pivot_index ) { int pivot_frequency = count . get ( unique [ pivot_index ]); // 1. move pivot to end swap ( pivot_index , right ); int store_index = left ; // 2. move all less frequent elements to the left for ( int i = left ; i <= right ; i ++) { if ( count . get ( unique [ i ]) < pivot_frequency ) { swap ( store_index , i ); store_index ++; } } // 3. move pivot to its final place swap ( store_index , right ); return store_index ; } public void quickselect ( int left , int right , int k_smallest ) { /* Sort a list within left..right till kth less frequent element takes its place. */ // base case: the list contains only one element if ( left == right ) return ; // select a random pivot_index Random random_num = new Random (); int pivot_index = left + random_num . nextInt ( right - left ); // find the pivot position in a sorted list pivot_index = partition ( left , right , pivot_index ); // if the pivot is in its final sorted position if ( k_smallest == pivot_index ) { return ; } else if ( k_smallest < pivot_index ) { // go left quickselect ( left , pivot_index - 1 , k_smallest ); } else { // go right quickselect ( pivot_index + 1 , right , k_smallest ); } } public int [] topKFrequent ( int [] nums , int k ) { // build hash map : character and how often it appears count = new HashMap <>(); for ( int num: nums ) { count . put ( num , count . getOrDefault ( num , 0 ) + 1 ); } // array of unique elements int n = count . size (); unique = new int [ n ]; int i = 0 ; for ( int num: count . keySet ()) { unique [ i ] = num ; i ++; } // kth top frequent element is (n - k)th less frequent. // Do a partial sort: from less frequent to the most frequent, till // (n - k)th less frequent element takes its place (n - k) in a sorted array. // All element on the left are less frequent. // All the elements on the right are more frequent. quickselect ( 0 , n - 1 , n - k ); // Return top k frequent elements return Arrays . copyOfRange ( unique , n - k , n ); } } class Solution_optimize { public int [] topKFrequent ( int [] nums , int k ) { // O(1) time if ( k == nums . length ) { return nums ; } // 1. build hash map : character and how often it appears // O(N) time Map < Integer , Integer > countMap = new HashMap (); for ( int n: nums ) { countMap . put ( n , countMap . getOrDefault ( n , 0 ) + 1 ); } // init heap 'the less frequent element first', poll到最后剩下K个最大的 Queue < Integer > heap = new PriorityQueue <>( ( n1 , n2 ) -> countMap . get ( n1 ) - countMap . get ( n2 )); // 2. keep k top frequent elements in the heap // O(N log k) < O(N log N) time for ( int n: countMap . keySet ()) { heap . add ( n ); if ( heap . size () > k ) heap . poll (); } // 3. build an output array // O(k log k) time int [] top = new int [ k ]; for ( int i = k - 1 ; i >= 0 ; -- i ) { top [ i ] = heap . poll (); } return top ; } } // use an array to save numbers into different bucket whose index is the frequency public class Solution_bucketCount { public List < Integer > topKFrequent ( int [] nums , int k ) { List < Integer > result = new LinkedList <>(); if ( nums == null || nums . length == 0 ) { return result ; } Map < Integer , Integer > hm = new HashMap <>(); for ( int n: nums ){ hm . put ( n , hm . getOrDefault ( n , 0 ) + 1 ); } // @note: corner case: if there is only one number in nums, we need the bucket has index 1. LinkedList [] bucket = new LinkedList [ nums . length + 1 ]; for ( int n: hm . keySet ()){ int freq = hm . get ( n ); if ( bucket [ freq ] == null ) { bucket [ freq ] = new LinkedList <>(); } bucket [ freq ]. add ( n ); } for ( int i = bucket . length - 1 ; i > 0 && k > 0 ; i --){ // @note: possible tie happening if ( bucket [ i ] != null ){ List < Integer > list = bucket [ i ]; result . addAll ( list ); k -= list . size (); } } return result ; } } class Solution { public List < Integer > topKFrequent ( int [] nums , int k ) { List < Integer > result = new ArrayList <>(); if ( nums == null || nums . length == 0 ) { return result ; } // from num, to its count HashMap < Integer , Integer > hm = new HashMap <>(); // to store top k PriorityQueue < Pair > heap = new PriorityQueue <>( ( o1 , o2 ) -> ( o1 . count - o2 . count ) ); for ( int each: nums ) { hm . put ( each , 1 + hm . getOrDefault ( each , 0 )); } for ( Map . Entry < Integer , Integer > entry: hm . entrySet ()) { heap . offer ( new Pair ( entry . getKey (), entry . getValue ())); // @note: i missed it if ( heap . size () > k ) { heap . poll (); } } while (! heap . isEmpty ()) { result . add ( heap . poll (). num ); } Collections . reverse ( result ); return result ; } } class Pair { int num ; int count ; public Pair ( int num , int count ){ this . num = num ; this . count = count ; } } } ////// class Solution { public int [] topKFrequent ( int [] nums , int k ) { Map < Integer , Long > frequency = Arrays . stream ( nums ). boxed (). collect ( Collectors . groupingBy ( Function . identity (), Collectors . counting ())); Queue < Map . Entry < Integer , Long >> queue = new PriorityQueue <>( Map . Entry . comparingByValue ()); for ( var entry : frequency . entrySet ()) { queue . offer ( entry ); if ( queue . size () > k ) { queue . poll (); } } return queue . stream (). mapToInt ( Map . Entry :: getKey ). toArray (); } } ``` ### Python ```python ''' >>> nums = ["a", "a", "b", "c", "c"] >>> cnt = Counter(nums) >>> cnt Counter({'a': 2, 'c': 2, 'b': 1}) # default to keys >>> sorted_freqs = sorted(cnt, key=lambda x: (-cnt[x], x)) >>> sorted_freqs ['a', 'c', 'b'] ''' from collections import Counter class Solution : def topKFrequent ( self , nums : List [ int ], k : int ) -> List [ int ]: # Count the frequency of each element in the list cnt = Counter ( nums ) # Sort the elements by frequency in decreasing order # diff from below solution: sorted(cnt), not sorted(cnt.items()) # more in https://leetcode.ca/2017-10-22-692-Top-K-Frequent-Words/ sorted_freqs = sorted ( cnt , key = lambda x : ( - cnt [ x ], x )) return sorted_freqs [: k ] ############## class Solution : def topKFrequent ( self , nums : List [ int ], k : int ) -> List [ int ]: # Count the frequency of each element in the list freqs = Counter ( nums ) # Sort the elements by frequency in decreasing order sorted_freqs = sorted ( freqs . items (), key = lambda x : x [ 1 ], reverse = True ) # also passing OJ: sorted_freqs = sorted(freqs.items(), key=lambda x: -x[1]) # Take the top k elements top_k = [ num for num , freq in sorted_freqs [: k ]] return top_k ############## ''' >>> from heapq import heappush >>> h = [] >>> heappush(h, (3,1)) >>> heappush(h, (1,1)) >>> heappush(h, (2,1)) >>> h [(1, 1), (3, 1), (2, 1)] >>> from heapq import heappop >>> heappop(h) (1, 1) >>> heappop(h) (2, 1) >>> heappop(h) (3, 1) ''' from collections import Counter class Solution : # heap def topKFrequent ( self , nums : List [ int ], k : int ) -> List [ int ]: cnt = Counter ( nums ) hp = [] for num , freq in cnt . items (): heappush ( hp , ( freq , num )) # freq first, default sort by 1st element if len ( hp ) > k : heappop ( hp ) return [ v [ 1 ] for v in hp ] ############## from typing import List import random # O(n log(n)) in the average case # O(n^2) worst case class Solution : def topKFrequent ( self , nums : List [ int ], k : int ) -> List [ int ]: freq_map = {} for num in nums : freq_map [ num ] = freq_map . get ( num , 0 ) + 1 freq_list = list ( freq_map . items ()) self . quick_select ( freq_list , 0 , len ( freq_list ) - 1 , k ) return [ num for num , freq in freq_list [: k ]] def quick_select ( self , freq_list , start , end , k ): if start == end : return pivot_idx = random . randint ( start , end ) pivot_freq = freq_list [ pivot_idx ][ 1 ] left = start right = end while left <= right : while freq_list [ left ][ 1 ] > pivot_freq : left += 1 while freq_list [ right ][ 1 ] < pivot_freq : right -= 1 if left <= right : freq_list [ left ], freq_list [ right ] = freq_list [ right ], freq_list [ left ] left += 1 right -= 1 if k <= right : self . quick_select ( freq_list , start , right , k ) elif k >= left : self . quick_select ( freq_list , left , end , k ) ########### ''' >>> x = [1, 2, 3] >>> x.append([4, 5]) >>> print(x) [1, 2, 3, [4, 5]] >>> x = [1, 2, 3] >>> x.extend([4, 5]) >>> print(x) [1, 2, 3, 4, 5] ''' class Solution : def topKFrequent ( self , nums : List [ int ], k : int ) -> List [ int ]: freq = Counter ( nums ) # not always filled, max possible frequency is len(nums) [1,1,1,1,...] buckets = [[] for _ in range ( len ( nums ) + 1 )] for num , freq in freq . items (): buckets [ freq ]. append ( num ) res = [] for bucket in reversed ( buckets ): if bucket : res . extend ( bucket ) if len ( res ) >= k : break return res [: k ] ############ class Solution ( object ): def topKFrequent ( self , nums , k ): """ :type nums: List[int] :type k: int :rtype: List[int] """ d = {} res = [] ans = [] buckets = [[] for _ in range ( len ( nums ) + 1 )] for num in nums : d [ num ] = d . get ( num , 0 ) + 1 for key in d : res . append (( d [ key ], key )) for t in res : freq , key = t buckets [ freq ]. append ( key ) buckets . reverse () for item in buckets : if item and k > 0 : while item and k > 0 : ans . append ( item . pop ()) k -= 1 if k == 0 : return ans return ans ``` ### CPP ```cpp // OJ: https://leetcode.com/problems/top-k-frequent-elements/ // Time: O(N + U) on average, O(N + U^2) in the worst case // Space: O(U) class Solution { public: vector < int > topKFrequent ( vector < int >& A , int k ) { if ( A . size () == k ) return A ; unordered_map < int , int > cnt ; for ( int n : A ) cnt [ n ] ++ ; vector < int > ans ; for ( auto & [ n , c ] : cnt ) ans . push_back ( n ); if ( ans . size () == k ) return ans ; auto partition = [ & ]( int L , int R ) { int i = L , j = L , pivotIndex = L + rand () % ( R - L + 1 ), pivot = cnt [ ans [ pivotIndex ]]; swap ( ans [ pivotIndex ], ans [ R ]); for (; i < R ; ++ i ) { if ( cnt [ ans [ i ]] > pivot ) swap ( ans [ i ], ans [ j ++ ]); } swap ( ans [ j ], ans [ R ]); return j ; }; auto quickSelect = [ & ]( int k ) { int L = 0 , R = ans . size () - 1 ; while ( L < R ) { int M = partition ( L , R ); if ( M + 1 == k ) break ; if ( M + 1 > k ) R = M - 1 ; else L = M + 1 ; } }; quickSelect ( k ); ans . resize ( k ); return ans ; } }; ```