Top K Frequent Elements

347. Top K Frequent Elements

Medium

Return the k most frequent elements from an integer array.

ArrayHash TableDivide and ConquerSortingHeap (Priority Queue)Bucket SortCountingQuickselect

View Problem

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.

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^5
• -10^4 <= nums[i] <= 10^4
• 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.

Try It Yourself

TypeScript

function topKFrequent(nums: number[], k: number): number[] {
    // Your solution here
}

Go

func topKFrequent(nums []int, k int) []int {
    // Your solution here
}

Solution

Click to reveal solution

Count frequencies and sort by frequency to get the top k elements.

TypeScript Solution

function topKFrequent(nums: number[], k: number): number[] {
  const count: Record<number, number> = {};

  for (const num of nums) {
      count[num] ||= 0;
      count[num]++;
  }

  const sorted = Object.entries(count).sort((a, b) => b[1] - a[1]);

  return sorted.slice(0, k).map(([key, _val]) => Number(key));
}

Time:O(n log n)

Space:O(n)

Go Solution

// TODO: Add Go solution

Time:O(n log n)

Space:O(n)

Algorithm:

1. Create a frequency map to count occurrences of each number
2. Convert the map to an array of [number, frequency] pairs
3. Sort the pairs by frequency in descending order
4. Take the first k elements and extract the numbers
5. Return the result array

Time Complexity: O(n log n) due to sorting Space Complexity: O(n) for the frequency map and sorted array

Optimized Approach (Bucket Sort - O(n)): For better time complexity, you can use bucket sort:

function topKFrequent(nums: number[], k: number): number[] {
    const count = new Map<number, number>();
    
    // Count frequencies
    for (const num of nums) {
        count.set(num, (count.get(num) || 0) + 1);
    }
    
    // Create buckets where index = frequency
    const buckets: number[][] = Array(nums.length + 1).fill(null).map(() => []);
    
    // Place numbers in buckets based on their frequency
    for (const [num, freq] of count.entries()) {
        buckets[freq].push(num);
    }
    
    // Collect top k elements from highest frequency buckets
    const result: number[] = [];
    for (let i = buckets.length - 1; i >= 0 && result.length < k; i--) {
        result.push(...buckets[i]);
    }
    
    return result.slice(0, k);
}