Top K Frequent Elements

MEDIUM

Description

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 <= 10⁵
-10⁴ <= nums[i] <= 10⁴
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

Checkout 3 different approaches to solve Top K Frequent Elements. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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 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.
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 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.

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 Analysis

Time Complexity: 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 Complexity: 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 and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Top K Frequent Elements. Click on different languages to view the code.

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 (); } }

Video Solution

Watch the video walkthrough for Top K Frequent Elements

Algorithms:

Divide and ConquerSortingBucket SortQuickselect

Patterns:

Counting

Data Structures:

ArrayHash TableHeap (Priority Queue)

Companies:

Atlassian |Avito |ByteDance |Chewy |