Top K Frequent Words - Priority Queue Approach (LeetCode)

Here is a step by step explanation of a priority queue based question called Top K Frequent Words asked at many top tech companies!
Check out my interview prep platform for learning the patterns!
📢 Interview Prep Platform: algoswithmichael.com
🎧 Join the community Discord: / discord
💰 Support me on Patreon: / michaelmuinos
🔗Follow me on LinkedIn: / michael-muinos
📂Follow me on Github: github.com/MichaelMuinos

[@darthvader_]

Michael, you are a savior! I happened to solve this question earlier but the explanation you gave helped a lot!

[@Metachief_X]

Hey bro, god bless you. i was struggling with this problem for a couple hours.... studying hard for my next interviews... you rock! keep making videos :)

[@jacquelinepassehl425]

This video was amazing and really helped me in preparing for technical interviews! thank you so much for this, you just got a new subscriber :D

[@AlgosWithMichael]

Thank you for the support!

[@manojrajasekar6035]

Fantastic one Michael. Keep doin more :)

[@AlgosWithMichael]

Definitely, thank you for watching!

[@franklinshih9169]

great explanation omg thank you

[@CostaKazistov]

Nice walkthrough and the solution. Here is Kotlin version: class Solution { fun topKFrequent(words: Array, k: Int): List { val result = mutableListOf() val comparator = Comparator { a, b -> if (a.value != b.value) b.value.compareTo(a.value) else a.key.compareTo(b.key) } val queue = PriorityQueue(comparator) words.groupingBy { it }.eachCount().forEach { queue.offer(it) } while (result.size < k && queue.isNotEmpty()) result.add(queue.poll().key) return result } }

[@wendycheng6856]

Great explanation! Pretty Clear!

[@AlgosWithMichael]

Glad it was helpful!

[@user-cl2db4uo5d]

thank you man, i understand)

[@AnuragBaidyanath]

Great explanation michael!

[@AlgosWithMichael]

Glad it was helpful!

[@oven5997]

Thanks for sharing, great explanation

[@AlgosWithMichael]

My pleasure!

[@silverbullet_17]

Thanks bro i Almost forgot about the @override method.❤️

[@AlgosWithMichael]

No problem 👍

[@snowy-ur9qq]

Thanks for the clear explanation! I have a follow-up question about time complexity - since each of the n entries in the map is added to the queue (and polled only if the queue size exceeds k), shouldn't the time complexity be O(n*logn)?

[@indiansoftwareengineer4899]

Thanks Michael.

[@AlgosWithMichael]

Thank you!

[@chiragchandak9554]

amazing work brother

[@AlgosWithMichael]

Thank you so much 😀

[@sumitrakumarishaw2885]

Thanks from India

[@animatedzombie64]

N time for map insertion, Nlogk for actual heap insertion because it heapifies on every insertion, and finally Klogk for reversing the list. so N + Nlogk + Klogk => NlogK upperbound.

[@Bubdiddly]

Thank you this is what I was wondering

[@soulboy2223]

perfect!

[@AlgosWithMichael]

thanks!

[@amberlala2163]

I think that using lambda expression to initialize the priority queue is more concise. ^-^

[@AlgosWithMichael]

Very true, I just didn't want to use that way in case people had not seen lambda syntax before.

[@z41n70]

For those wondering how to do the lamba version: PriorityQueue pq = new PriorityQueue((a, b)->map.get(a)-map.get(b)==0?b.compareTo(a):map.get(a)-map.get(b));

[@tomladdus9264]

What would you do if your standard library does not have a Priority Queue? For example, Swift, if this is asked by Apple, does not have a PQ as part of the standard library. Would they expect you to write one on the spot?

[@AlgosWithMichael]

I think what they would do is just say to assume you have a Priority Queue implementation already written

[@KCML036]

how come we don't take comparing the string lexicographically part into the Big O? Wouldn't that be worst case length of the maximum string. Say max string length is m then wouldn't the big O be n*(m*logk)

[@bz9031]

Hi, I have a question. Why do we have to use map.Entry in this case? Could we simply use map.keySet()?

[@AlgosWithMichael]

You could also use a keySet 😀

[@sputnikone3724]

What is the purpose of using a minheap here? Why not use a maxheap instead and then pop the top K ones?

[@venkataraman2716]

do you have python 3 code using same approach

[@HarshySZN]

So the reason we create a min heap for getting MAX k values is to reduce the amount of elements we store in the heap. If we do a max heap then we will continue to keep storing values we are not going to use. Interesting

[@BlumChoi]

if k=1 and I have n unique strings, than the sorting suggested in the video will take O(nlog(n)), wouldn't it?

[@Ikhideifidon]

No. It will be O(n)

[@mohammadyahya78]

Thank you very much. I still don't understand the comparator and why you said frq1-freq2 while word2.compareTo(word1) and not word1.compareTo(word2) please?

[@SheikhSadiruddin1]

You want to remove the less frequent words and those that have greater alphabetical ordering.

[@VinodKumar-vd9ou]

Bro, nice video but i think storing words in Map is not a good idea in case we have huge number of string files, Trie could be a better approach for efficient storage and also you can store counts at leaf node of trie.

[@priyanshumohanty5261]

I think based on the constraints specified in the question, this sure is a good method. Besides, tries can be trickier

[@woodylucas]

Is that comparator class similar to JavaScript sort method?

[@AlgosWithMichael]

Yes, I believe so

[@sofiayz7472]

I know it's going to be a very dumb question but why frequency1-frequency2?

[@AlgosWithMichael]

Not a dumb question at all! It is because we need to sort the lesser frequencies first. So for example, lets say frequency1 is 2 and frequency2 is 4, this would do 2 - 4 = -2. Since it is a negative number, we are saying word1 is less than word2 in sorted order.

[@sofiayz7472]

@@AlgosWithMichael Thank you so much for your reply! You are absolutely a great teacher!I just subscribed to your channel and can't wait to learn more from you!

[@AlgosWithMichael]

No problem! Thank you so much for watching my content, I really appreciate it 👍

[@Ikhideifidon]

The last return of the Comparator isn’t safe. The code may give the wrong answer when there is overflow. For instance, when comparing a large negative value to a large positive value, the difference may be more than the largest value that can be stored in an integer, Integer.MAX_VALUE

[@NguyenCuong-sg2kg]

How about use Trie

[@AlgosWithMichael]

I'm not sure if a Trie would improve the complexity

[@jeffreylee911]

why don't we do this in correct order directly instead of reversing it in the end?

[@AlgosWithMichael]

2 months late on this response lol sorry did not see it. The reason why is because when we insert into our priority queue, we are inserting the words in reverse alphabetical order, we want it in alphabetical order for the final result

[@jeffreylee911]

@@AlgosWithMichael But still helpful! Thanks a lot!

[@namisha6883]

@@AlgosWithMichael Why are we not counting complexity of reverse sorting in the end, which is O(N Log N) and certainly greater than O(N* log k)

[@alienwareCL]

@@namisha6883 reverse is not NlogN, you do N/2 operations to reverse cause u swap a[i] with a[length - i]. And since N/2 < NLOGK the timr complexity mantains in nlogk

[@leomonz]

Why can’t you do word1.compareTo(word2)?

[@AlgosWithMichael]

Because you only sort by the word strings if the frequencies are the same

[@obaid5761]

@@AlgosWithMichael i think he meant why it's the other way around

[@satheshbm92]

Yes I have the same question. Why can't we use word1.compareTo(word2) in the comparator?

[@AlgosWithMichael]

Oh I see. You still can't flip them, you would get different results if you did word1.compareTo(word2). I just tried now and failed multiple test cases :/

[@uvedkhan1]

@@AlgosWithMichael Thats the question, why is like that?

[@ArghyaBhattacharyaNITA]

"Love isn't supposed to come before 'I" '. That my friend, is a heavy truth :)

[@christeenathomas6108]

please solve this problem using python3

[@AlgosWithMichael]

Yea, if enough people want python instead of java I can do that

[@KanagaveluSugumar]

I dont think we need to reverse it. Need to change word1.compareTo(word2) ? By the way your videos are more helpful. Thank you!

[@pramodsharma4508]

The problem was asked at a google interview with input size of 1 trillion

[@AlgosWithMichael]

Oof Google be asking hard questions :p

[@VadimFilin]

Lol, implement PriorityQueue in C or Go at first. Dislike