DSA Walkthrough - 05

Intro

• There will be an array with bunch of repeated integers.
• We need to find the frequently repeated integers based on the given k value

First approach

• The approach is pretty simple, we use the hashmap again and store the integer with their count
• This is how i indeed approached the problem, this being the first step of the problem, i had trouble understand the next part where i have to find the top K elements.
• What i did was to return it as list from the hashmap and indeed i did this which is totally stupid and incorrect return list(hsh[key],i)
• I understand if u feel im dumb by seeing the above approach i did (im dumb indeed)
• Forgot to mention that i even tried sorting the hashmap but what i didnt see is that i sorted them by key which was the next forward step towards my dumb approach!

Solution

• As I discussed earlier, the solution goes in 2 steps.
• First step: This is how we store the given integers from the array to the hashmap
• Second step: Now, Inside the hashmap what we do is-- Sort them by value not the key.
• After sorting, we use the classic way to access the top K frequent elements by [:k]
• The important part of this problem is the key line of the sorting sorrt = sorted(hsh, key=hsh.get, reverse=True)
• We reverse the hashmap because the array of the values will be from higher to lower so we sort them lexicographically.

Code

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        hsh = {}
        for i in nums:
            if i not in hsh:
                hsh[i] = 1
            else:
                hsh[i] +=1
        sorrt = sorted(hsh, key=hsh.get, reverse=True)
        return sorrt[:k]

Conclusion

Didnt think much for this problem but i didnt like that sorting part either because i was dumb enough to not do it myself.