Leetcode - 347. Top K Frequent Elements

Medium

Dec 22, 2025

#hashmap

#frequency

347. Top K Frequent Elements

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]

Example 3:

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

Output: [1,2]

Constraints:

1 <= nums.length <= 105
-104 <= nums[i] <= 104
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.

Notes

Intuition

Bucket sort by frequency. Since the maximum frequency is n, we can use an array where index represents frequency and values are the elements with that frequency. Scanning from highest to lowest frequency gives us the top k elements.

Implementation

First, count frequencies with a hashmap. Then create a frequency array of length n + 1 (indices 0 to n), where each index is a list of elements with that frequency. Iterate backward through this array, collecting elements until we have k items.

Edge-cases

Multiple elements can share the same frequency, so each bucket is a list. When collecting results, iterate through all elements in each bucket before moving to the next lower frequency.

Time: O(n) — frequency counting and bucket iteration
Space: O(n) — hashmap and frequency buckets

Complexity

Solution

from typing import List

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        map = {}
        for num in nums:
            if num in map:
                map[num] += 1
            else:
                map[num] = 1

        freq_table = [[] for _ in range(len(nums) + 1)]
        for num in map:
            freq = map[num]
            freq_table[freq].append(num)

        ans = []
        for i in range(len(freq_table) - 1, -1, -1):
            for j in range(len(freq_table[i]) - 1, -1, -1):
                ans.append(freq_table[i][j])
                if len(ans) == k:
                    return ans


        return ans



if __name__ == "__main__":
    # Include one-off tests here or debugging logic that can be run by running this file
    # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
    solution = Solution()