LeetCode 347 - Top K Frequent Elements

2026-04-06

medium　array

Given an integer array nums and an integer k, return the k most frequent elements within the array.The test cases are generated such that the answer is always unique.You may return the output in any order.

Example 1:

Input: nums = [1,2,2,3,3,3], k = 2

Output: [2,3]

Example 2:

Input: nums = [7,7], k = 1

Output: [7]

Constraints:

1 <= nums.length <= 10^4.-1000 <= nums[i] <= 10001 <= k <= number of distinct elements in nums.

• 1 <= nums.length <= 10^4.
• 1000 <= nums[i] <= 1000
• 1 <= k <= number of distinct elements in nums

Solution 1:

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # Brute-force solution
        # First, use a hash map to record the frequency of each element.
        # Second, iterate k times. In each iteration, scan the hash map to find the 
        # current maximum frequency element that hasn't been chosen yet.
        
        # Time Complexity: O(k * n), where n is the number of unique elements. 
        # Counting frequencies takes O(n), and finding the max k times takes O(k * n).
        # Space Complexity: O(n), to store the hash map and the set of chosen numbers.
        frequent_hashmap = {}
        for num in nums:
            if num in frequent_hashmap:
                frequent_hashmap[num] += 1
            else:
                frequent_hashmap[num] = 1

        result_list = []
        choosed_number = 0
        choosed_num = set()
        while choosed_number != k:
            current_max_value = 0
            current_max = 0
            for key, value in frequent_hashmap.items():
                if key in choosed_num:
                    continue
                if current_max_value <= value:
                    current_max_value = value
                    current_max = key
            result_list.append(current_max)
            choosed_num.add(current_max)
            choosed_number += 1

        return result_list

Solution 2:

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # Sorting Approach
        # First, use a hash map to record the frequency of each element.
        # Second, turn the hash map into a list of tuples, then sort it by frequency in descending order.
        # Finally, slice the top k elements and return their keys.
        
        # Time Complexity: O(n log n), where n is the number of unique elements. 
        # Counting frequencies takes O(n), and sorting the elements takes O(n log n).
        # Space Complexity: O(n), to store the hash map and the list of tuples.
        frequent_hashmap = {}
        for num in nums:
            if num in frequent_hashmap:
                frequent_hashmap[num] += 1
            else:
                frequent_hashmap[num] = 1

        result_list = [(key, value) for key, value in frequent_hashmap.items()]
        result_list = sorted(result_list, key= lambda x: -x[1])
        result_list = [key for key, value in result_list[:k]]
        return result_list

Solution 3:

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # Bucket Sort Approach (Optimal O(n) Solution)
        # First, count the frequency of each number using a hash map.
        # Second, create an array of lists (buckets) where the index represents the frequency.
        # Finally, iterate through the buckets from right to left (highest frequency to lowest) 
        # and collect the numbers until we reach k elements.
        
        # Time complexity: O(n), since we iterate through the list and the buckets a constant number of times.
        # Space complexity: O(n), to store the hash map and the bucket array.
        
        frequent_hashmap = {}
        result_list = []
        
        # 1. Count frequencies
        for num in nums:
            if num in frequent_hashmap:
                frequent_hashmap[num] += 1
            else:
                frequent_hashmap[num] = 1
                
        # 2. Create buckets where index = frequency
        frequent_bucket = [[] for _ in range(len(nums) + 1)]
        for key, value in frequent_hashmap.items():
            frequent_bucket[value].append(key)

        # 3. Gather the top k elements from the highest frequency buckets
        for bucket in reversed(frequent_bucket):
            for value in bucket:
                result_list.append(value)
                # Early return as soon as we collected k elements!
                if k == len(result_list):
                    return result_list
        
        return result_list

Solution 4:

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        return [num for num, count in Counter(nums).most_common(k)]