💬 Discord
Sign In
NeetCode #98LC-347MediumArrays & HashingBlind 75NC 150NC 250
← Back to All Problems

#98 · #347 · Top K Frequent Elements(前 K 个高频元素)

📌 Problem Statement & Constraints

Given an integer array nums and an integer k, return the k most frequent elements in any order. Constraints: 1 <= nums.length <= 10^5, k is in the range [1, number of distinct elements]; the answer is guaranteed unique.

💡 Core Algorithmic Approaches

  1. First build a frequency map with Counter -- this is unavoidable and costs O(n).
  2. Option A (optimal): bucket sort by frequency. The maximum possible frequency is n, so create n + 1 buckets and place each value into buckets[freq]. Then walk buckets from high to low, collecting until you have k values. This is O(n).
  3. Option B: a min-heap of size k keyed by frequency, giving O(n log k).
  4. Option C: heapq.nlargest(k, counter, key=counter.get) -- concise and O(n log k).
  5. Note the answer is unique, so no tie-breaking rule is needed.

💻 Benchmark Python3 Implementation

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        from collections import Counter
        freq = Counter(nums)
        n = len(nums)
        buckets = [[] for _ in range(n + 1)]      # index = frequency
        for value, f in freq.items():
            buckets[f].append(value)
        res = []
        for f in range(n, 0, -1):                 # scan high frequency first
            for value in buckets[f]:
                res.append(value)
                if len(res) == k:
                    return res
        return res


# Heap variant: O(n log k) time, O(n) space, shorter code
class Solution2:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        import heapq
        from collections import Counter
        freq = Counter(nums)
        return heapq.nlargest(k, freq, key=freq.get)

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n) with bucket sort: counting is O(n), filling buckets is O(distinct), and the descending scan stops as soon as k values are collected. The heap variant is O(n log k).
💾 Space Complexity
O(n) for the frequency map and the bucket array. The heap variant uses O(distinct) for the map plus O(k) for the heap.

⚠️ Interview Pitfalls & Follow-ups

  • sorted(freq.items(), key=lambda kv: -kv[1])[:k]: correct but O(n log n). Mention it, then offer bucket sort or a heap to show you know the trade-off.
  • Sizing the bucket array as max(freq.values()) + 1: also works, but n + 1 is simpler and always safe since no frequency can exceed n.
  • Using a max-heap of all distinct values: it is O(n log n) and defeats the purpose of the heap size limit.
  • Assuming ties must be broken deterministically: the problem guarantees a unique answer, so you do not need a tie-break rule.