⏰ Time complexity: O(n log k), where n is the size of nums and k is size of min heap.

Count the frequency of elements in O(n) using a hashmap.
O(n log k) for using min heap
O(n + k) using bucket sort.

🧺 Space complexity: O(n), for the hashmap and additional data structures.

Method 4 - Bucket Sort 🏆

Intuition

We can use array of linked list, where we can bucketize the numbers based on there frequency. The bucket index will be frequency, values will be number added to that bucket. Number of buckets will be = n + 1. Why? Because what if all the element occur once, then it is n; Also, 0 for 0 frequency case. This helps in avoiding edge cases, where we need to sometimes do index-1 etc.

Approach

Build the frequency map.
Create an array of lists (the "buckets"), of size N+1. The index of this array represents a frequency.
Iterate through the frequency map. For each number, add it to the list at the bucket index corresponding to its frequency. (e.g., a number appearing 3 times goes into buckets[3]).
Iterate through the buckets array backwards, starting from the highest possible frequency (N). Collect the numbers from the buckets until you have k elements.
Return the collected elements. This approach has a linear O(N) time complexity.

Code

[{"language":"Java","code":"class Solution {\n\n    public int[] topKFrequent(int[] nums, int k) {\n        Map<Integer, Integer> counts = new HashMap<>();\n        for (int n : nums) {\n            counts.put(n, counts.getOrDefault(n, 0) + 1);\n        }\n\n        List<Integer>[] buckets = new List[nums.length + 1];\n        for (int i = 0; i < buckets.length; i++) {\n            buckets[i] = new ArrayList<>();\n        }\n\n        for (int num : counts.keySet()) {\n            buckets[counts.get(num)].add(num);\n        }\n\n        List<Integer> ansList = new ArrayList<>();\n        for (int i = buckets.length - 1; i >= 0 && ansList.size() < k; i--) {\n            if (!buckets[i].isEmpty()) {\n                ansList.addAll(buckets[i]);\n            }\n        }\n\n        int[] ans = new int[k];\n        for (int i = 0; i < k; i++) {\n            ans[i] = ansList.get(i);\n        }\n        return ans;\n    }\n}","lang":"java"},{"language":"Python","code":"class Solution:\n    def topKFrequent(self, nums: list[int], k: int) -> list[int]:\n        counts = collections.Counter(nums)\n        n = len(nums)\n        buckets = [[] for _ in range(n + 1)]\n\n        for num, freq in counts.items():\n            buckets[freq].append(num)\n\n        ans = []\n        for i in range(n, -1, -1):\n            if buckets[i]:\n                ans.extend(buckets[i])\n            if len(ans) >= k:\n                break\n\n        return ans[:k]","lang":"python"}]

Complexity

⏰ Time complexity: O(n) each to count frequencies, populate the bucket and collect the top k frequent elements.
🧺 Space complexity: O(n) for the frequency map and bucket.

Follow-up Solution (Tie-breaker: Larger Number First)

If two elements have the same frequency, return the larger element first. This affects both sorting and heap approaches.

Method 1 - Sorting

Sort by frequency descending, then by value descending.

Code

[{"language":"Python","code":"class Solution:\n    def topKFrequent(self, nums: List[int], k: int) -> List[int]:\n        freq = Counter(nums)\n        # Sort by frequency descending, then value descending\n        pairs = so

Related Tags

Continue Practicing