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.

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 |