347.Top_K_Frequent_Elements(Medium).md

347. Top K Frequent Elements (Medium)

Date and Time: Aug 19, 2024, 21:40 (EST)

Link: https://leetcode.com/problems/top-k-frequent-elements/

Question:

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2

Output: [1, 2]

Example 2:

Input: nums = [1], k = 1

Output: [1]

Constraints:

• 1 <= nums.length <= 10^5

• -10^4 <= nums[i] <= 10^4

• k is in the range [1, the number of unique elements in the array].

• It is guaranteed that the answer is unique.

Walk-through:

1. Use count{} to store all the elements with their count.

2. Fill frequency buckets freq[[]] to store {count: element}.

3. We loop over from the back of freq to append element into res, until len(res) == k. Notice that, it will skip empty array, so we don't need to worry about these cases.

Python Solution:

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # Count the frequency of every element
        # Use freq[[]] in range [1, len(nums)] to save the same count frequency elements
        # Traverse the count_list backward to append the most count elements until k

        # TC: O(n), n = len(nums), SC: O(n)
        count, freq = {}, [[] for _ in range(len(nums)+1)]
        res = []
        for n in nums:
            count[n] = count.get(n, 0) + 1
        for i, c in count.items():
            freq[c].append(i)
        # Traverse backward to append elements from most count to least count into res[]
        for i in range(len(freq)-1, -1, -1):
            # Get all the elements with the same frequency
            for j in freq[i]:
                res.append(j)
                if len(res) == k:
                    return res

Time Complexity: $O(n)$
Space Complexity: $O(n)$

Python Heap Solution:

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # Count each element with their counts
        # Use minHeap to sort the counts
        # Add the elements into res[]

        # TC: O(nlog k), n=len(nums), SC: O(n)
        counts = {}     # {"num": counts}
        for i in nums:
            counts[i] = counts.get(i, 0) + 1
        # Save counts with num into minHeap
        minHeap = []
        for i, c in counts.items():
            heapq.heappush(minHeap, (-c, i))
        # Add num into res
        res = []
        while len(res) < k:
            res.append(heapq.heappop(minHeap)[1])
        return res

Time Complexity: $O(nlog\ k)$, heap maintains at size k, each push() or pop() leads to $O(log\ k)$. And the heap operations are performed n times.
Space Complexity: $O(n)$