Top K Frequent Words - Priority Queue Approach (LeetCode)

[@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!

[@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 :)

[@darthvader_]

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

[@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 } }

[@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)?

[@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

[@manojrajasekar6035]

Fantastic one Michael. Keep doin more :)

[@AlgosWithMichael]

Definitely, thank you for watching!

[@silverbullet_6]

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

[@AlgosWithMichael]

No problem 👍

[@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));

[@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!

[@manjunathbhadrannavar5165]

My que is, why use a priority queue? because we just need to return top k from a map of key value pairs, sort using a custom comparator and return top k values, simple 🤷‍♂

[@GochiCity]

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

[@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)

[@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 👍

[@oven5997]

Thanks for sharing, great explanation

[@AlgosWithMichael]

My pleasure!

[@franklinshih9169]

great explanation omg thank you

[@wendycheng6856]

Great explanation! Pretty Clear!

[@AlgosWithMichael]

Glad it was helpful!

[@AnuragBaidyanath]

Great explanation michael!

[@AlgosWithMichael]

Glad it was helpful!

[@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

[@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

[@ArghyaBhattacharyaNITA]

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

[@sumitrakumarishaw2885]

Thanks from India

[@indiansoftwareengineer4899]

Thanks Michael.

[@AlgosWithMichael]

Thank you!

[@sputnikone3724]

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

[@chiragchandak9554]

amazing work brother

[@AlgosWithMichael]

Thank you so much 😀

[@Руслан-х7и2э]

thank you man, i understand)

[@codeduel]

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

[@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.

[@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 😀

[@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?

[@codeduel]

No. It will be O(n)

[@christeenathomas6108]

please solve this problem using python3

[@AlgosWithMichael]

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

[@venkataraman2716]

do you have python 3 code using same approach

[@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?

[@woodylucas]

Is that comparator class similar to JavaScript sort method?

[@AlgosWithMichael]

Yes, I believe so

[@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)

[@Alex7nt]

@@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

[@soulboy2223]

perfect!

[@AlgosWithMichael]

thanks!

[@NguyenCuong-sg2kg]

How about use Trie

[@AlgosWithMichael]

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

[@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