{ }DevToolsDaily
ToolsInterview
Problems
New
CheatsheetsChat
New
BlogPricing
Ctrl + K

Top K Frequent Elements – Solution & Complexity

Interview solutions
/
Top K Frequent Elements

1. Understand the Goal

  • Identify the required output and the state that changes.
  • Use the examples to rule out tempting but incorrect interpretations.

2. Choose the Core Pattern

  • This problem is best exposed by Bucket values by frequency and scan buckets from high to low.
  • Maintain only the state needed for the next operation.

3. Build the Algorithm

  • Process each state once when possible.
  • Record state before scheduling dependent work to avoid duplicates.

4. Check Edge Cases

  • Verify the smallest input, impossible cases, and repeated values where allowed.
  • Keep output ordering deterministic.

5. Final Solution and Complexity

  • Time complexity is O(n).
  • Space complexity is O(n).
def top_k_frequent(nums: list[int], k: int) -> list[int]:
    counts = {}
    for number in nums: counts[number] = counts.get(number, 0) + 1
    buckets = [[] for _ in range(len(nums) + 1)]
    for number, frequency in counts.items(): buckets[frequency].append(number)
    answer = []
    for frequency in range(len(nums), 0, -1):
        for number in buckets[frequency]:
            answer.append(number)
            if len(answer) == k: return answer
    return answer

FAQ

See also

Practice Top K Frequent Elements online (run code in the browser)Kth Largest Element in an Array solution (medium)Contains Duplicate solution (easy)Find Median from Data Stream solution (hard)Majority Element solution (easy)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsContact Us © Monkey SkatesHave kids?