347. Top K Frequent Elements - Detailed Explanation
Problem Statement
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order. In other words, find the k values that appear most frequently in the array.
-
Example 1:
Input:nums = [1,1,1,2,2,3],k = 2
Output:[1, 2]
Explanation: The number1appears 3 times, and2appears 2 times. These are the two most frequent elements in the array. -
Example 2:
Input:nums = [1],k = 1
Output:[1]
Explanation: With only one element, that element is the most frequent by default.
Constraints:
1 <= nums.length <= 10^5(up to 100,000 elements in the array).-10^4 <= nums[i] <= 10^4(array elements can be negative or positive).1 <= k <=number of unique elements innums. (You will never be asked for more elements than exist.)- The output is guaranteed to be unique for the given input (there's only one correct set of top k frequent elements for each test case).
- Follow-up: You should strive for an algorithm faster than O(n log n) for large inputs .
Hints
- Use a hash map (dictionary) to count the frequency of each number in the array. This will give you a frequency count for each unique element.
- Once you have the frequencies, think about how to get the top k counts efficiently:
- One straightforward way is to sort the elements by frequency, but that costs O(n log n) time. The problem’s follow-up specifically hints to find a faster solution than sorting.
- Consider using a heap (priority queue) data structure. Heaps are excellent for maintaining top elements in streaming or selection problems. For example, a min-heap of size k can store the top k frequencies seen so far.
- Another insight: since frequencies range from 1 up to n, you can use a bucket sort style approach. Create buckets for each possible frequency and distribute elements into these buckets based on their count. Then you can collect results starting from the highest frequency bucket.
- Think about edge cases like when k equals the number of unique elements (then you would return all elements), or when the array contains all identical elements.
Multiple Approaches with Code
Brute Force Approach (Sorting-based frequency count)
Detailed Explanation:
This approach uses sorting to determine the most frequent elements. First, count the occurrences of each number using a hash map (or Python’s Counter). Then convert the frequency map into a list of (element, frequency) pairs and sort this list by frequency in descending order. Finally, pick the first k elements from the sorted list. This method is straightforward to implement. However, sorting all unique elements by frequency has a time complexity of about O(n log n) in the worst case (when there are n unique elements). This is acceptable for moderately sized n, but the follow-up asks for a faster solution. Space complexity is O(n) due to storing the frequency map and the list of pairs.
Python Code Implementation
Explanation: We use a dictionary freq to count occurrences. Then we sort freq.items() by the second value (frequency) in reverse (highest first). Finally, we take the first k keys from the sorted list. In the example, freq would be {1:3, 2:2, 3:1}, sorting by values gives [(1,3), (2,2), (3,1)], and the top 2 keys are [1, 2].
Java Code Implementation
Explanation: We use a HashMap<Integer,Integer> to count frequencies. Then, we create a list of map entries and sort it using a custom comparator that compares the entry values (frequencies) in descending order. Finally, we take the first k keys from the sorted list. The output array result contains the k most frequent numbers. (The Arrays.toString is used to print the array in a readable format.)
Heap-based Approach (Using Min-Heap / Priority Queue)
Detailed Explanation:
This approach leverages a min-heap (priority queue) to keep track of the top k frequent elements without sorting the entire list of unique elements. We still start by counting frequencies in a hash map. Then:
- Use a min-heap of size at most k, ordered by frequency. As you iterate through the frequency map, push each
(frequency, element)pair onto the min-heap. If the heap grows larger than size k, remove the smallest frequency element (the min-heap property ensures the smallest frequency is at the root). This way, the heap always holds at most k elements, and they are the k most frequent seen so far. - After processing all elements, the heap contains the k most frequent elements, but in no particular order. You can then extract all elements from the heap; they will come out from lowest frequency to highest frequency. The order of output doesn't matter in this problem, so we can return them as is (or sort them by frequency if needed for presentation).
Using a min-heap of size k yields a time complexity of about O(n log k): for each of the n unique elements we do a log k push/pop operation. If k is much smaller than n, this is efficient. In the worst case where k ≈ n, the complexity approaches O(n log n). Space complexity is O(n) for the frequency map plus O(k) for the heap storage. (Using a max-heap and popping k times is an alternative: build a max-heap of all unique elements and pop k times, which is O(n + k log n) time. The min-heap method is slightly more optimal when k << n.)
Python Code Implementation
Explanation: We maintain a heap of at most k elements. The heapq module in Python implements a min-heap, so the smallest frequency is always at heap[0]. We push (frequency, num) for each item, and if the heap grows larger than k, we pop the smallest frequency. This ensures that after iterating through all items, the heap contains only the k largest frequencies. We then pop all elements from the heap into result. In this example, after counting we have freq = {1:3, 2:2, 3:1}. The heap will end up containing [(2,2), (3,1)] (frequencies 2 and 3). Popping from the heap yields 2 then 1, and reversing gives [1, 2]. (Even without reversing, any order is acceptable; we reverse just to show the highest frequency first.)
Java Code Implementation
Explanation: We use Java’s PriorityQueue with a custom comparator to serve as a min-heap based on the frequency value of the map entries. We iterate through the frequency map, add each entry to the heap, and if the heap’s size exceeds k, we remove the smallest frequency entry. After this, the heap contains k entries with the largest frequencies. We then poll the heap to build the result array. In the example, the heap will contain the entries for 1 and 2 (frequencies 3 and 2). Polling the heap might retrieve 2 before 1 (since 2 has the smaller frequency), yielding output [2, 1]. This is fine because the problem does not require the result to be sorted—only that it contains the two most frequent elements. (If needed, we could sort the result or use a different data structure to preserve order, but it's not required.)
Bucket Sort Approach (Optimized frequency bucket method)
Detailed Explanation:
This approach uses an array of "buckets" to avoid sorting comparisons. The idea is to group numbers by their frequency. Since an element’s frequency can range from 1 up to n (where n is the array length), we create an array of size n+1 where each index i represents a bucket of elements that appear exactly i times.
Steps:
- Count frequencies with a hash map (same as before).
- Create a list of buckets, where
buckets[i]will hold all numbers that appear i times in the array. - Iterate over the frequency map and append each number to the bucket corresponding to its frequency.
- Finally, iterate over the buckets from highest frequency to lowest. Collect numbers from non-empty buckets until we have k elements.
By iterating from the maximum frequency downwards, we gather the most frequent elements first. We stop once we have k elements. This approach runs in O(n) time on average and in the worst case also O(n) (we do a pass to count, a pass to distribute into buckets, and at most n steps to collect results, which is O(n + n + n) = O(n) ). Space complexity is O(n) for the frequency map plus the bucket list. This meets the follow-up requirement of better than O(n log n) time. Keep in mind that although it's linear time, it may use more memory and have larger constants; in practice, if k is small, the heap approach can be very efficient too.
Python Code Implementation
Explanation: We allocate n+1 buckets (where n = len(nums)). For each number, we place it into the bucket corresponding to its frequency. In the example, freq = {1:3, 2:2, 3:1}. We create 7 buckets (indices 0 through 6, since n=6). We put 1 in buckets[3], 2 in buckets[2], and 3 in buckets[1]. Then we iterate from bucket 6 down to 1 and collect numbers. Buckets 6,5,4 are empty; bucket 3 contains [1] → add 1 to result; result length is 1 (need 2); bucket 2 contains [2] → add 2; result length is 2, we stop. The result is [1, 2]. This method effectively avoids sorting by using the frequency as an index.
Java Code Implementation
Explanation: This Java implementation mirrors the Python bucket strategy. We use an array of ArrayList<Integer> for buckets of frequencies. After filling the buckets, we iterate from count = n downwards and collect elements. We stop once we have collected k elements. Finally, we convert the list to an array for output. The output will contain the k most frequent elements. In the example, the bucket at index 3 contains 1, index 2 contains 2, and we collect [1, 2].
Complexity Analysis
-
Brute Force (Sorting-based): Counting frequencies takes O(n) time. Sorting the unique elements by frequency takes O(m log m), where m is the number of unique elements (m ≤ n). In the worst case (all elements unique), this is O(n log n). Therefore, overall time complexity is O(n log n). Space complexity is O(n) to store the frequency map and the list of sorted entries.
-
Heap-based: Building the frequency map is O(n). Pushing all m unique elements into a heap and then popping down to size k takes O(m log m) in the worst case, but using the size-limited min-heap approach, each insertion/poll operation is O(log k). Doing this for m elements gives O(m log k) time, which is O(n log k) in the worst case (still better than n log n when k < n). If k is small relative to n, this is very efficient. Space complexity is O(n) for the map plus O(k) for the heap (in the worst case, O(n) if k ~ n). The output array of size k is negligible. For example, if n = 100,000 and k = 10, this approach handles the counting in 100k and only performs log(10) operations per element for the heap, which is very fast in practice.
-
Bucket Sort: Counting is O(n). Creating the buckets array of size n is O(n), and filling it with m entries is O(m) (which is ≤ n). Collecting the top k from the buckets is at most O(n) in the worst case (if we had to look through many buckets to gather k elements). Overall, this approach is O(n) time. Space complexity is O(n) for the frequency map plus O(n) for the buckets (total O(n)). This meets the linear time goal. Note: In practice, the bucket approach can have larger constant factors (allocating an array of size n, and many empty buckets) and can incur more cache misses. For typical inputs where k is not extremely large, the heap approach may perform similarly or even faster due to lower constant overhead, even though its theoretical complexity is slightly higher.
In summary, the heap and bucket approaches both avoid the full O(n log n) sort. The heap runs in O(n log k) and the bucket in O(n). For large n with relatively small k, the heap approach is practically very efficient. The bucket approach guarantees linear time at the cost of extra space.
Common Mistakes
- Not using a hash map for counting: A common mistake is trying to sort the array or use some other method without first counting frequencies. Without counting, it’s difficult to identify the most frequent elements directly.
- Sorting the array values instead of frequencies: Some might sort the array numerically or try to group equal values by scanning, which complicates the process. It's much easier to use a map to count, then sort by the count.
- Misusing the heap: If using a min-heap (as in Python’s
heapqor Java’sPriorityQueue), forgetting to limit its size can lead to storing all elements (losing the benefit of the heap approach). On the flip side, using a max-heap and then trying to pop k times works, but you must be careful to pop exactly k elements. Also, in Python,heapqis a min-heap by default; to use it as a max-heap, people sometimes push negative frequencies or useheapq.nlargest. Not handling that correctly can lead to errors. - Off-by-one errors in bucket construction: Remember that if an element appears n times, it should go into bucket index n. If your buckets array is of length n, you need indices 0..n (inclusive n), so typically define it as size n+1. Forgetting the +1 or mis-indexing will either waste index 0 or miss index n. In our bucket code, we included index 0 (which remains empty because no element can have frequency 0) just to align counts with indices.
- Assuming output order: The problem states the answer can be in any order, so you don’t need to sort the output. A mistake is to spend extra time ordering the result. For example, the heap approach might output the top k in increasing frequency order. This is still a correct answer. Only worry about ordering if the problem specifically asks for it (here it does not).
- Not considering all unique elements: If k equals the number of unique elements, the result should simply be all unique elements. Make sure your logic handles that (it usually will, but it’s worth noting as a check).
- Memory issues: Although not likely with these constraints, using extremely large data structures unnecessarily could be a mistake. For instance, creating a bucket array of size much larger than n (perhaps using value range instead of frequency range by accident) would be wrong. Always base the bucket on frequency, not on the value of the numbers.
Edge Cases
- Single element array: e.g.,
nums = [5],k = 1. The output should just be[5]. All approaches handle this by returning the single element. - All elements identical: e.g.,
nums = [2,2,2,2],k = 1. The most frequent (and only) element is 2. The output should be[2]. Ensure that your algorithm doesn’t mistakenly try to return more elements or have an issue with bucket size (bucket index equal to n in this case). - All elements unique: e.g.,
nums = [1,2,3,4],k = 2. Here each element’s frequency is 1. The top 2 frequent elements could technically be any two of them since all have the same frequency. The problem guarantee that “answer is unique” suggests they might not include cases with ties that affect the top k boundary. But even if they did, any two of the elements would be a correct answer (e.g.,[1,2]or[3,4]). Your algorithm should handle this by returning any k elements (usually it will pick the first k it encounters in some order). - k equals number of unique elements: e.g.,
nums = [4,4,6,6,7],k = 3. The unique elements are {4,6,7} and k=3 means return all of them. Make sure the code doesn’t stop early or omit an element in this scenario. Both the heap and bucket methods will naturally return all unique elements if k matches that count. - Negative and zero values: e.g.,
nums = [0, -1, -1, -2, -2, -2],k = 2. The output should be[-2, -1](since -2 appears 3 times, -1 appears 2 times). The counting logic should treat negative numbers or zero just like any other key. All our approaches use the numbers as map keys, which works for negatives and zero. - Large input size: If
numshas 100,000 elements, ensure your solution is efficient. The sorting approach will work but is borderline (O(n log n) with n=100k is okay, but the follow-up implies they test higher performance). The heap and bucket approaches should handle it comfortably. Also ensure no excessive memory usage (the bucket array of length 100k + 1 is fine).
By considering these edge cases, you can be confident your solution handles all typical scenarios.
Alternative Variations
This problem can be adapted or extended in various ways:
- Top K Frequent Words: Instead of integers, you might be given a list of words and asked for the k most frequent words. The core approach is similar (count with a hash map, then use a heap or sort or bucket). One added twist is usually that if two words have the same frequency, you have to sort them alphabetically. This variation is actually a LeetCode problem ("Top K Frequent Words") that can be solved with a similar heap approach using a custom comparator for strings.
- K Least Frequent Elements: A variation could ask for the k least frequent elements. You could solve this by simply inverting the comparison – for example, using a max-heap of size k (to weed out larger frequencies) or sorting in ascending order of frequency. Or, find the top k frequent and then consider the remaining if needed. The bucket idea can also be used by iterating from lowest frequency upwards.
- Return Elements by Frequency Order: Another twist might be to return all elements sorted by frequency (not just the top k). This is effectively what the bucket sort does if you were to output all buckets in descending order. A known problem "Sort Characters By Frequency" (for strings) uses this concept. It’s like taking the bucket approach and not stopping at k but continuing through all frequencies.
- Real-time Stream Processing: In an interview setting, you might be asked how to maintain the top k frequent elements in a stream of data (where the list is too large to store, or data is coming in one by one). In that case, you could mention using a frequency map plus a min-heap of size k that you update as new data comes in (possibly also needing a data structure like a hash map + heap or a tree that can update frequencies on the fly). This is a more advanced scenario that combines concepts of this solution with data stream algorithms.
- Quickselect approach: As an alternative solution approach (not a different problem), one can use the Quickselect algorithm (a selection algorithm similar to QuickSort's partitioning) to find the k-th most frequent threshold and partition the unique elements around that frequency. This can achieve average O(n) time without the extra space of a heap or buckets. This approach is complex to implement correctly, but it's a valid variation to mention for completeness. (In fact, the theoretical fastest solution for this problem uses Quickselect to achieve average linear time.)
Related Problems for Further Practice
To strengthen your understanding, you can practice these problems which are similar in concept:
- Top K Frequent Words (LeetCode 692) – Find the k most frequent strings in an array of words. Very similar to this problem, but requires handling lexicographical order for ties.
- Sort Characters By Frequency (LeetCode 451) – Given a string, sort it in decreasing order by character frequency. You can apply a counting and bucket sort approach, analogous to what we discussed.
- Kth Largest Element in an Array (LeetCode 215) – Find the k-th largest element (by value) in an unsorted array. This can be solved by a heap or Quickselect. It’s a different scenario (based on values rather than frequency), but practicing it helps understand heap and selection algorithms.
- Majority Element (LeetCode 169) – Find the element that appears more than ⌊n/2⌋ times in an array. This is essentially the “top 1 frequent” problem with a guaranteed count > n/2. It can be solved with a hash map count (or in linear time with the Boyer-Moore voting algorithm).
- Majority Element II (LeetCode 229) – Find all elements that appear more than ⌊n/3⌋ times. This is another frequency-based problem where a hash map or Boyer-Moore extended algorithm can be used. While not about top k, it’s about finding elements with frequency above a certain threshold.
- Bucket Sort and Counting Sort implementations – While not a specific LeetCode problem, practicing implementing bucket sort or counting sort in different contexts (like sorting an array of integers with known range) can reinforce the idea of using an array of frequencies, which is directly applicable to the bucket method used here.
GET YOUR FREE
Coding Questions Catalog
