Top K Frequent Elements

📋

Problem

Imagine you are analyzing a large dataset of user actions and want to quickly find the most common actions performed.

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

1 ≤ nums.length ≤ 10^5-10^4 ≤ nums[i] ≤ 10^4k is in the range [1, the number of unique elements in the array]

Edge cases: All elements are the same → return that elementk equals number of unique elements → return all elementsArray with negative and positive numbers → handle negative keys correctly

</>

IDE

def topKFrequent(nums: list[int], k: int) -> list[int]:public int[] topKFrequent(int[] nums, int k)vector<int> topKFrequent(vector<int>& nums, int k)function topKFrequent(nums, k)

def topKFrequent(nums, k):
    # Write your solution here
    pass

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // Write your solution here
        return new int[0];
    }
}

#include <vector>
using namespace std;

vector<int> topKFrequent(vector<int>& nums, int k) {
    // Write your solution here
    return {};
}

function topKFrequent(nums, k) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [3]Returning only one element when k=2 due to incorrect loop or early return.✅ Ensure your code returns exactly k elements by slicing or extracting top k from sorted or heap structure.

Wrong: [1,2,3,4]Returning all elements regardless of k, ignoring the k parameter.✅ Return only the first k elements after sorting or heap extraction.

Wrong: [1]Fails on single element input by returning empty or wrong output.✅ Handle single element input by returning that element when k=1.

Wrong: [1,2,3]Fails to handle ties in frequency, returning more than k elements or wrong elements.✅ Return exactly k elements even if multiple have same frequency; use stable sorting or heap.

Wrong: [4,3]Sorting by element value instead of frequency.✅ Sort or heapify by frequency counts, not element values.

✓

Test Cases

Try testing your solution on empty and minimal inputs to catch base case bugs.

Consider cases with frequency ties and verify your sorting or heap logic.

Focus on algorithmic complexity and data structures to handle large inputs efficiently.

t1_01basic

Input{"nums":[1,1,1,2,2,3],"k":2}

Expected[1,2]

⏱ Performance - must finish in 2000ms

1 appears 3 times, 2 appears 2 times, 3 appears once. The top 2 frequent elements are 1 and 2.

💡 Count the frequency of each element using a hash map.

💡 Use a sorting or heap method to find the top k frequent elements.

💡 Sort unique elements by frequency descending and return the first k.

Why it failed: Failed to return correct top k elements by frequency; likely sorting or frequency counting error. Fix by sorting unique elements by frequency descending and returning first k.

✓ Correctly identified top k frequent elements.

t1_02basic

Input{"nums":[4,4,4,6,6,7,7,7,7],"k":3}

Expected[7,4,6]

⏱ Performance - must finish in 2000ms

7 appears 4 times, 4 appears 3 times, 6 appears 2 times. The top 3 frequent elements are 7, 4, and 6.

💡 Map each number to its frequency count.

💡 Extract unique elements and sort or use a heap by frequency.

💡 Return the top k elements sorted by frequency descending.

Why it failed: Incorrect top k elements returned; likely frequency map or sorting logic bug. Fix by ensuring frequency counts are accurate and sorting unique elements by frequency descending.

✓ Correctly returned top 3 frequent elements.

t2_01edge

Input{"nums":[],"k":0}

Expected[]

⏱ Performance - must finish in 2000ms

Empty input array and k=0 means no elements to return.

💡 Check how your code handles empty input arrays.

💡 Ensure frequency map and sorting handle empty cases gracefully.

💡 Return empty list immediately if nums is empty or k is zero.

Why it failed: Code crashes or returns non-empty output on empty input; fix by adding base case to return empty list if nums is empty or k is zero.

✓ Correctly handles empty input and k=0.

t2_02edge

Input{"nums":[5],"k":1}

Expected[5]

⏱ Performance - must finish in 2000ms

Single element array; top 1 frequent element is the element itself.

💡 Test with smallest non-empty input.

💡 Frequency map should count single element correctly.

💡 Return the single element when k=1 and nums length=1.

Why it failed: Fails to handle single element input; fix by ensuring frequency map and return logic handle single element arrays.

✓ Correctly returns single element for single-item input.

t2_03edge

Input{"nums":[1,2,3,4],"k":4}

Expected[1,2,3,4]

⏱ Performance - must finish in 2000ms

k equals number of unique elements; return all elements.

💡 Check behavior when k equals number of unique elements.

💡 Frequency map counts all unique elements once.

💡 Return all unique elements when k equals unique count.

Why it failed: Fails to return all unique elements when k equals unique count; fix by returning all unique keys if k equals their count.

✓ Correctly returns all unique elements when k equals unique count.

t2_04edge

Input{"nums":[-1,-1,2,2,3],"k":2}

Expected[-1,2]

⏱ Performance - must finish in 2000ms

Negative and positive numbers present; -1 and 2 both appear twice, top 2 frequent elements are -1 and 2.

💡 Ensure frequency map handles negative keys correctly.

💡 Count frequencies for all elements regardless of sign.

💡 Return top k elements by frequency including negatives.

Why it failed: Fails to count or return negative numbers correctly; fix by using a hash map that supports negative keys.

✓ Correctly handles negative and positive numbers.

t3_01corner

Input{"nums":[1,1,2,2,3,3],"k":2}

Expected[1,2]

⏱ Performance - must finish in 2000ms

Multiple elements have the same frequency (2 each); any two of the three elements are valid top 2 frequent elements.

💡 Consider how ties in frequency are handled.

💡 Check if your code returns exactly k elements even with ties.

💡 Return any k elements among those with highest frequency.

Why it failed: Returns fewer or more than k elements when frequencies tie; fix by ensuring exactly k elements are returned even if frequencies tie.

✓ Correctly returns any k elements among top frequencies with ties.

t3_02corner

Input{"nums":[1,1,1,2,2,2,3,3,3,4],"k":3}

Expected[1,2,3]

⏱ Performance - must finish in 2000ms

All top 3 elements have the same frequency (3 each); must return exactly 3 elements.

💡 Beware of greedy approaches that pick first k elements without frequency check.

💡 Use frequency map and sort or heap to get top k by frequency.

💡 Return exactly k elements even if multiple have same frequency.

Why it failed: Greedy approach fails by returning incorrect elements or wrong count; fix by sorting or using a heap based on frequency.

✓ Correctly handles multiple elements with same frequency and returns exactly k.

t3_03corner

Input{"nums":[1,2,2,3,3,3,4,4,4,4],"k":2}

Expected[4,3]

⏱ Performance - must finish in 2000ms

Top 2 frequent elements are 4 (4 times) and 3 (3 times).

💡 Check if your code confuses frequency counts with element values.

💡 Ensure sorting or heap is based on frequency, not element value.

💡 Return elements with highest frequency, not highest value.

Why it failed: Returns elements with highest values instead of highest frequency; fix by sorting or heapifying by frequency counts.

✓ Correctly returns elements with highest frequency.

t4_01performance

Input{"nums":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100],"k":10}

Expectednull

⏱ Performance - must finish in 2000ms

Input size n=100 with distinct elements; solution must run in O(n log k) or O(n) time within 2 seconds.

💡 Use a frequency map to count occurrences in O(n).

💡 Use a min-heap of size k or bucket sort for O(n) or O(n log k) complexity.

💡 Avoid sorting entire array which is O(n log n) and may time out.

Why it failed: Brute force or full sorting approach causes TLE; fix by using min-heap or bucket sort to achieve O(n log k) or O(n) time.

✓ Efficient solution runs within time limits using appropriate data structures.

Practice

1. You are given a list of strings and need to group them so that each group contains strings that are permutations of each other. Which approach guarantees an optimal solution in terms of time complexity?

easy

A. Use a brute force approach comparing every pair of strings by sorting them and grouping if equal.

B. Use a hash map with a character frequency count array as the key for each string.

C. Use dynamic programming to build groups based on substring matches.

D. Sort the entire list of strings and then group consecutive strings that are equal.

Solution

1. Step 1: Understand the problem requirement

   We need to group strings that are anagrams, i.e., permutations of each other.

2. Step 2: Evaluate approaches for optimality

   Brute force comparing pairs is O(n^2 * k log k), sorting entire list doesn't group anagrams efficiently, and DP is not applicable here. Using a frequency count array as a hash map key achieves O(n * k) time.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Frequency count keys uniquely identify anagram groups [OK]

Hint: Frequency count keys uniquely identify anagrams [OK]

Common Mistakes:

• Thinking sorting entire list groups anagrams efficiently
• Using DP for grouping anagrams
• Brute force is optimal

2. Suppose the problem changes: now you want to detect if any number appears at least twice, but the array is extremely large and cannot fit into memory. Which approach is best suited to handle this scenario?

hard

A. Sort the array externally (external sort) and then scan for duplicates in a streaming fashion.

B. Use a hash set in memory as before, but process the array in chunks and merge results.

C. Use a bloom filter to probabilistically detect duplicates with limited memory.

D. Use nested loops on the entire array since it requires no extra space.

Solution

1. Step 1: Understand memory constraints

   The array is too large to fit in memory, so hash sets or sorting in memory are infeasible.

2. Step 2: Evaluate options

   External sorting is possible and practical for large data sets that cannot fit into memory. Bloom filters provide probabilistic detection but can yield false positives, which may not be acceptable depending on requirements. Nested loops are impractical due to O(n²) time complexity.

3. Step 3: Choose external sorting

   External sorting allows sorting data on disk and then scanning sequentially for duplicates, which is efficient and exact.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   External sorting handles large data sets with limited memory and provides exact duplicate detection [OK]

Hint: External sorting enables exact duplicate detection on large data sets [OK]

Common Mistakes:

• Assuming hash sets can handle huge data
• Ignoring external sorting costs
• Choosing nested loops despite inefficiency
• Overlooking bloom filter false positives

3. Suppose the data structure must support duplicate elements (i.e., multiple identical values can be inserted). Which modification to the optimal Insert Delete GetRandom design correctly supports duplicates while maintaining average O(1) insert, remove, and getRandom?

hard

A. Use a hash map from value to a set of indices in the array, update sets on insert and remove, and swap-delete as before

B. Store counts of each value in a hash map and keep a list of unique values only, ignoring duplicates in the array

C. Use a linked list instead of an array to store elements and a hash map for counts

D. Disallow duplicates by checking presence before insert, same as original design

Solution

1. Step 1: Understand duplicate challenge

   Duplicates mean one value maps to multiple indices; a single index in pos is insufficient.

2. Step 2: Modify data structures

   Use a hash map from value to a set of indices to track all positions; update sets on insert/remove; swap-delete still works by updating sets accordingly.

3. Step 3: Verify O(1) operations

   Set insert/remove are O(1) average; array swap-delete remains O(1); getRandom picks random index from array.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Tracking multiple indices per value enables duplicates with O(1) ops [OK]

Hint: Map values to sets of indices to handle duplicates [OK]

Common Mistakes:

• Using counts only loses position info
• Ignoring duplicates breaks getRandom correctness
• Using linked list loses O(1) random access

4. Suppose the input array can contain duplicate numbers and you want to find the longest consecutive sequence length allowing repeated elements to be counted only once. Which modification to the optimal hash set approach correctly handles duplicates without inflating the sequence length?

hard

A. Sort the array and count consecutive numbers, skipping duplicates during the scan.

B. Use the hash set approach but iterate over the original array instead of the set.

C. Use a hash map to count frequencies and multiply sequence length by frequency.

D. Use the hash set approach as is, since duplicates are automatically ignored by the set.

Solution

1. Step 1: Understand duplicate impact

   Duplicates can inflate counts if not handled properly.

2. Step 2: Evaluate modifications

   Iterating over original array or multiplying by frequency inflates length. Using set alone ignores duplicates but does not handle sorted consecutive counting with duplicates properly.

3. Step 3: Correct approach

   Sorting and skipping duplicates during linear scan correctly counts longest consecutive sequence without inflating length.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Sorting + skipping duplicates ensures correct consecutive count [OK]

Hint: Sorting + skip duplicates handles repeated elements correctly [OK]

Common Mistakes:

• Iterating over original array causing duplicates counted multiple times
• Multiplying length by frequency inflates result
• Assuming set alone handles duplicates correctly

5. Suppose the input strings can contain uppercase letters and non-alphabetic characters. Which modification to the optimal frequency counting approach correctly handles this scenario?

hard

A. Use a hash map to count frequencies of all characters without assuming a fixed alphabet.

B. Ignore non-alphabetic characters and count only lowercase letters using the fixed-size array.

C. Sort both strings and compare them after converting to lowercase.

D. Use a fixed-size array of length 26 and convert all characters to lowercase before counting.

Solution

1. Step 1: Identify limitation of fixed-size array

   Fixed array of size 26 only works for lowercase 'a'-'z'; uppercase and other chars cause index errors or incorrect counts.

2. Step 2: Use hash map for general characters

   A hash map can dynamically store counts for any character, handling uppercase and non-alphabetic safely.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Hash map handles arbitrary character sets correctly [OK]

Hint: Fixed arrays only work for known small alphabets [OK]

Common Mistakes:

• Assuming lowercase only
• Ignoring non-alphabetic chars silently
• Using fixed array with uppercase chars