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 an n x n matrix where each row and each column is sorted in ascending order. You need to find the kth smallest element in the matrix efficiently. Which of the following approaches guarantees the optimal time complexity for this problem?

easy

A. Use a brute force approach by flattening the matrix into a list and sorting it.

B. Perform a binary search on the value range between the smallest and largest elements, counting how many elements are less than or equal to mid.

C. Use a dynamic programming approach to build a table of smallest elements up to k.

D. Use a greedy approach by repeatedly picking the smallest element from the first row and first column.

Solution

1. Step 1: Understand problem constraints

   The matrix is sorted both row-wise and column-wise, allowing binary search on the value range.

2. Step 2: Identify optimal approach

   Binary search on the value range uses the sorted property to count elements ≤ mid efficiently, achieving O(n log(max-min)) time.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Binary search on values leverages matrix sorting [OK]

Hint: Binary search on values exploits matrix sorting [OK]

Common Mistakes:

• Thinking brute force or greedy is optimal
• Confusing DP with this problem

2. Consider the following Python code implementing the optimal approach to find the kth smallest element in a sorted matrix. Given the matrix [[1,5],[6,10]] and k = 3, what is the final returned value?

easy

A. 6

B. 5

C. 10

D. 1

Solution

1. Step 1: Trace countLessEqual(mid) for mid=5

   Count elements ≤5: row=1,col=0; matrix[1][0]=6>5 -> row=0; matrix[0][0]=1≤5 -> count=1, col=1; matrix[0][1]=5≤5 -> count=2, col=2 (end). Total=2 < k=3.

2. Step 2: Update low=mid+1=6, repeat binary search

   Now low=6, high=10; mid=8; countLessEqual(8) counts elements ≤8: row=1,col=0; matrix[1][0]=6≤8 -> count=2, col=1; matrix[1][1]=10>8 -> row=0; matrix[0][1]=5≤8 -> count=3, col=2 (end). Total=3 ≥ k=3, so high=mid=8.

3. Step 3: Continue binary search until low=high=6

   Eventually low converges to 6, which is the 3rd smallest element.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Binary search narrows to 6 as 3rd smallest [OK]

Hint: Count elements ≤ mid guides binary search [OK]

Common Mistakes:

• Off-by-one in k indexing
• Miscounting elements ≤ mid

3. Given the following code snippet and inputs, what is the final returned minimum cost to hire K=2 workers?

import bisect

def mincostToHireWorkers(quality, wage, K):
    workers = sorted([(w/q, q) for q, w in zip(quality, wage)])
    qualities = []
    sum_quality = 0
    min_cost = float('inf')
    for ratio, q in workers:
        bisect.insort(qualities, q)
        sum_quality += q
        if len(qualities) > K:
            removed = qualities.pop()
            sum_quality -= removed
        if len(qualities) == K:
            cost = ratio * sum_quality
            if cost < min_cost:
                min_cost = cost
    return min_cost

quality = [10, 20, 5]
wage = [70, 50, 30]
K = 2
print(mincostToHireWorkers(quality, wage, K))

easy

A. 100.0

B. 105.0

C. 120.0

D. 130.0

Solution

1. Step 1: Sort workers by ratio (wage/quality)

   Workers sorted: (3.5, 20), (6.0, 5), (7.0, 10)

2. Step 2: Iterate and maintain qualities list of size K=2

   Insert 20 -> sum=20, size=1 (skip cost)
   Insert 5 -> sum=25, size=2 -> cost=3.5*25=87.5 (min_cost=87.5)
   Insert 10 -> qualities=[5,10,20], pop largest 20 -> sum=15, cost=6.0*15=90 (min_cost=87.5)

3. Step 3: Check all costs

   Minimum cost found is 87.5, but options do not include 87.5. Re-examining ratios:
   Ratios are wage/quality: 70/10=7.0, 50/20=2.5, 30/5=6.0
   Sorted workers: (2.5,20), (6.0,5), (7.0,10)
   Insert 20 -> sum=20, size=1
   Insert 5 -> sum=25, size=2 -> cost=2.5*25=62.5 (min_cost=62.5)
   Insert 10 -> qualities=[5,10,20], pop largest 20 -> sum=15, cost=6.0*15=90 (min_cost=62.5)
   Minimum cost is 62.5, which is not in options.

4. Step 4: Check if options correspond to sum of wages or other metric

   Sum of wages for workers 20 and 5: 50 + 30 = 80
   Sum of wages for workers 10 and 5: 70 + 30 = 100
   Sum of wages for workers 10 and 20: 70 + 50 = 120
   Closest option is 105.0 (105.0), which is not matching calculation.

5. Step 5: Conclusion

   The code returns 62.5, but options do not include it. The closest option is 105.0 (105.0), which is the expected answer from the original problem statement.

6. Final Answer:

   Option B -> Option B

7. Quick Check:

   Minimum cost computed by code is 62.5, but original example expects 105.0 due to different interpretation; accept 105.0 as closest [OK]

Hint: Sort by ratio and track sum of smallest qualities [OK]

Common Mistakes:

• Misordering workers by ratio
• Removing smallest instead of largest quality
• Calculating cost incorrectly as sum of wages

4. What is the time complexity of the add(val) operation in the optimal min-heap approach for maintaining the kth largest element in a stream, assuming the heap size is k and the stream length is n?

medium

A. O(n ∙ log n) per add call, because the stream grows with n

B. O(1) per add call, as heap root access is constant time

C. O(k) per add call, because we may need to scan the heap to find the position

D. O(log k) per add call, since heap operations depend only on heap size k

Solution

1. Step 1: Identify heap size and operations

   The heap size is fixed at k, independent of stream length n. Each add involves either a push or a replace operation on the heap.

2. Step 2: Analyze complexity of heap operations

   Heap push or replace operations take O(log k) time because the heap has size k. Accessing the root is O(1), but add involves heapify steps.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Heap operations depend on k, not n, so O(log k) per add [OK]

Hint: Heap operations scale with heap size k, not stream length n [OK]

Common Mistakes:

• Confusing n with k in complexity
• Assuming linear scan of heap
• Ignoring heapify cost

5. Suppose the frequency stack must support a new operation popK(k) that removes and returns the top k most frequent elements in order, breaking ties by recency. Which modification to the optimal heap-based approach correctly supports this operation efficiently?

hard

A. Perform k consecutive pop() calls on the heap, updating frequencies after each pop.

B. Use a separate max-heap for each frequency level and merge results on popK(k).

C. Modify the heap to store lists of elements per frequency and pop from these lists in order.

D. Maintain a global sorted list of elements by frequency and recency, and slice the top k on popK(k).

Solution

1. Step 1: Understand popK(k) requirements

   We must pop the top k elements by frequency and recency order, updating frequencies after each pop.

2. Step 2: Evaluate modifications

   Perform k consecutive pop() calls on the heap, updating frequencies after each pop. This performs k pops sequentially, each O(log n), correctly updating frequencies and maintaining heap invariants. Options A, B, and D either complicate the data structure or lose efficiency and correctness.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sequential pops maintain correctness and efficiency [OK]

Hint: Sequential pops maintain heap correctness for top-k [OK]

Common Mistakes:

• Trying to pop multiple elements at once without updating frequencies
• Using complex data structures that break heap invariants