Top K Frequent Elements
Med#0334Time: 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).35 companies
Patterns
Data structures
Prompt
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] <= 104kis 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
3 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Create a
HashMapto store the frequency of each number. - Iterate through the input array
numsand 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
kentries from the sorted list. - Return the resulting array of
kelements.
Walkthrough
The most intuitive approach is to first determine the frequency of every element, and then sort the elements based on these frequencies.
- Count Frequencies: We use a
HashMapwhere keys are the numbers from the input array and values are their frequencies. We iterate through thenumsarray once to populate this map. - 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.
- Extract Top K: After sorting, the
kmost frequent elements will be the firstkelements in the sorted list. We create a result array of sizekand populate it with these elements.
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<Integer, Integer> count = new HashMap<>(); for (int n : nums) { count.put(n, count.getOrDefault(n, 0) + 1); } // 2. Create a list of map entries List<Map.Entry<Integer, Integer>> 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; }}Complexity
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).
Trade-offs
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.
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.
Algorithm
- Create a
HashMapto store the frequency of each number. - Iterate through
numsto populate the frequency map. - Initialize a min-heap (
PriorityQueue) of sizek. 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
kmost frequent elements. Extract them into an array and return it.
Walkthrough
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.
- Count Frequencies: As with the previous approach, we first build a
HashMapto store the frequency of each number. This takes O(N) time. - Use a Min-Heap: We initialize a min-heap (a
PriorityQueuein Java). The heap's comparator will order elements based on their frequency, keeping the element with the minimum frequency at the top. - 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 usingpoll(). 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 thekmost frequent elements encountered so far. - Extract Result: After iterating through all unique numbers, the heap holds the
kmost frequent elements in the entire array. We can then extract these elements from the heap to form our result array.
import java.util.*; class Solution { public int[] topKFrequent(int[] nums, int k) { // 1. Build hash map: character -> its frequency Map<Integer, Integer> 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<Integer> 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; }}Complexity
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).
Trade-offs
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
kis large (close to N).
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.
Algorithm
- Create a
HashMapto store the frequency of each number. - Iterate through
numsto populate the frequency map. - Create an array of lists called
buckets. The size of this array should ben + 1, wherenis the length ofnums. - Iterate through the frequency map. For each number, add it to the list at the index corresponding to its frequency in the
bucketsarray. - Initialize an empty result list.
- Iterate through the
bucketsarray 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
kelements from the result list as an array.
Walkthrough
This approach achieves a linear time complexity by adapting the idea of Bucket Sort. Instead of sorting, we group elements by their frequency.
- Count Frequencies: Same as before, we use a
HashMapto count the frequency of each number in O(N) time. - 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 benums.length + 1, as the maximum possible frequency isnums.length(if all elements are the same). - Populate Buckets: We iterate through our frequency map. For each
(number, frequency)pair, we add thenumberto the list atbuckets[frequency]. - Gather Top K: To find the top
kfrequent elements, we iterate through thebucketsarray 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 containskelements.
This method avoids any comparison-based sorting, leading to a very efficient O(N) time complexity.
import java.util.*; class Solution { public int[] topKFrequent(int[] nums, int k) { // 1. Build hash map: character -> its frequency Map<Integer, Integer> 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<Integer>[] 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<Integer> 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; }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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 (); } }''' >>> 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// 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 ; } };Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.