[Neetcode/Greedy, Hash Map, Sort] Top K Frequent Elements

https://neetcode.io/problems/top-k-elements-in-list?list=neetcode150

NeetCode

 

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        m ={}
        ans =[]
        for i in nums:
            if i in m:
                m[i]+=1
            else: m[i] = 1

        l = sorted(m.keys(), key=lambda num: m[num], reverse=True)
        for u in range(k):
            ans.append(l[u])

        return ans

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        freq_map = {}
        for num in nums:
            freq_map[num] = freq_map.get(num, 0) + 1

        sorted_keys = sorted(freq_map.keys(), key=lambda x: freq_map[x], reverse=True)

        return sorted_keys[:k]

 

 

freq_map[num] = freq_map.get(num, 0) + 1

Count how many times each number appears:

• If num already exists in freq_map, get its count and add 1.
• If not, get() returns 0, and you set it to 1.

We add +1 to keep track of how many times each number appears.
.get(num, 0) ensures the first time we see the number, we start from 0.

 

✅ Example:

nums = [1, 2, 2, 3, 3, 3]
# freq_map becomes: {1: 1, 2: 2, 3: 3}

 

sorted_keys = sorted(freq_map.keys(), key=lambda x: freq_map[x], reverse=True)

• Sort the keys (unique numbers) by their frequency, from highest to lowest:
  • lambda x: freq_map[x] sorts by each number’s frequency.
  • reverse=True means most frequent comes first.

✅ Example:

sorted_keys = [3, 2, 1]  # if freq_map = {1:1, 2:2, 3:3}

 

return sorted_keys[:k]

• Return the first k elements from the sorted list.
• These are the k most frequent numbers.

✅ Example:

k = 2
# return [3, 2]

---

🔍 What is .get() in Python dictionaries?

.get() is a dictionary method that allows you to safely retrieve a value for a given key, with an optional default value if the key doesn't exist.

 

✅ Syntax:

dictionary.get(key, default_value)

• key: the key you’re trying to access.
• default_value (optional): the value to return if the key is not found.
  • If omitted, None is returned by default.

📌Example:

m = {'a': 2, 'b': 5}

print(m.get('a'))         # ➜ 2
print(m.get('c'))         # ➜ None (since 'c' is not in the dictionary)
print(m.get('c', 0))      # ➜ 0 (returns default value instead of None)