_347. Top K Frequent Elements.md

347. Top K Frequent Elements

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : June 13, 2024

Last updated : July 01, 2024

---

Related Topics : Array, Hash Table, Divide and Conquer, Sorting, Heap (Priority Queue), Bucket Sort, Counting, Quickselect

Acceptance Rate : 63.33 %

---

Solutions

• m347 v1 O(n log n).py
• m347 v2 O(n).py

Python

m347 v1 O(n log n).py

# Prompt follow up: Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # O(n)
        cnt = Counter(nums)

        # O(n log n)
        keys = sorted(cnt.keys(), reverse=True, key=lambda x: cnt.get(x))

        return keys[0:min(k, len(keys))]

m347 v2 O(n).py

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # O(n)
        cnt = Counter(nums)

        # O(n) reversal worst case
        revCnt = {}
        maxx = 0
        for key, val in cnt.items() :
            maxx = max(maxx, val)
            if val in revCnt :
                revCnt[val].append(key)
            else :
                revCnt[val] = [key]

        # O(n) worst case k == n
        output = []
        while maxx >= 0 and k > 0 :
            if maxx not in revCnt or not revCnt[maxx] :
                maxx -= 1
                continue
            output.append(revCnt[maxx].pop())
            k -= 1

        return output