Neetcode 150 - Top K Frequent Elements

1. Sorting

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count = {}
        for num in nums:
            count[num] = count.get(num, 0) + 1

        arr = []
        for num, cnt in count.items():
            arr.append([cnt, num])

        # Sort the count
        arr.sort()

        res = []
        while len(res) < k:
            res.append(arr.pop()[1])

        return res

  • Idea: Sort and find top k frquent count.

  • Time complexity: O(NlogN).

  • Space complexity: O(N).

2. Min-Heap (Remove the smallest element first, keep largest element)

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count = {}
        for num in nums:
            count[num] = count.get(num, 0) + 1

        heap = []
        for num in count.keys():
            heapq.heappush(heap, (count[num], num))
            if len(heap) > k:
                heapq.heappop(heap)

        # Keep top k max heap
        res = []
        for i in range(k):
            res.append(heapq.heappop(heap)[1])

        return res

  • Idea: Instead of the the height of the tree to N, only keep it to k.

  • Time complexity: O(NlogK)

  • Space Complexity: O(N + K)

3. Greedy (Bucket Sort)

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count = {}

        # Can be full the same items
        freq = [[] for i in range(len(nums) + 1)]

        for num in nums:
            count[num] = count.get(num, 0) + 1

        for num, cnt in count.items():
            freq[cnt].append(num)

        # Find k most frequent items
        res = []
        for i in range(len(freq) - 1, 0, -1):
            for num in freq[i]:
                res.append(num)
                if len(res) == k:
                    return res

  • Idea: [1, len(nums)], store count -> [item1, item2,…] array.

  • Find the top k max frequent items here.

  • Time complexity: O(N).

  • Space complexity: O(N)

Last Updated On October 22, 2025