{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Top K Frequent Elements – Solution & Complexity

Interview solutions
/
Top K Frequent Elements

Solution Walkthrough

  1. Step 1: Understand the Goal

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

  2. Step 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. Step 3: Build the Algorithm

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

  4. Step 4: Check Edge Cases

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

  5. Step 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
Learn the Arrays & Hashing pattern: recognition cues, invariant, and ordered practice →

FAQ

See also

Practice Top K Frequent Elements online (run code in the browser)K Closest Points to Origin solution (medium)Kth Largest Element in an Array solution (medium)3Sum solution (medium)Contains Duplicate solution (easy)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?