There’s also an O(n) solution using counting sort on an array of size n where the indices are counts and the values are lists of the elements with those counts; then append from the highest to lowest counts till we hit k
@@MohammedAli-pb1fgthere a few misconceptions here. If you consider hashmap insertion to be O(1), then inserting everything into the map is O(n). However, the process of iterating over each map pair and inserting into the heap is O(nlog(k)). Its not hard to see that n < nlog(k). Therefore, O(nlog(k)) dominates and is the correct runtime under these assumptions. 2nd, hashmap insertion is actually O(n) and not O(1) . So the algorithm is technically O(n^2).
![Summer Walker - Heart Of A Woman [Official Lyric Video]](http://i.ytimg.com/vi/SFddctbZzw8/mqdefault.jpg)
Prepare for coding interviews for FREE at AlgoMap.io!
I appreciate this series of shorts, after watching a few of these, I decided I'm better off in UI/UX and graphic design. Thank you!
😂
There’s also an O(n) solution using counting sort on an array of size n where the indices are counts and the values are lists of the elements with those counts; then append from the highest to lowest counts till we hit k
Loop through the keys and look for values of the keys that are equal to the k element then return [1,2]
first solution i got correct
Me too
I was about to comment the same thing :)
In python we can use coutner to return the count of each element and then comvert that into list sort it and print last two index
That’s less efficient. You need to loop through every time for every unique element in that solution rather than one loop where you manually count
Why not max heap it is more efficient in terms of complexity?
k log n instead of
n log k
Because k
Shouldn't the time complexity be k log n?
Why cant we just iteratethe map entry set and return key for value 2. Time Complexity will be O(2n)
Hello today we are going to solve a problem:
First off we allocate memory.
Second off: we allocate even more memory.
Yay!
Why not just sort since using heap is basically a form of sorting and the time complexity is nlogn anyways
O(n)
I meant nlog k is better than nlogn k
It’s just counter ?
you didn't give the complexity of the optimal solution :(
With how useful hashmaps are i think that it shouldnt be allowed. It makes everything hash worthy
never used a hashmap, I do real programming instead
nlogk?
Yeah, I thought it was klogn
No O(n) ..cause inserting ,updating any element in hash map take 0(1) time...total space will be O(no. Of distinct number in arrays)
@@MohammedAli-pb1fgthere a few misconceptions here.
If you consider hashmap insertion to be O(1), then inserting everything into the map is O(n). However, the process of iterating over each map pair and inserting into the heap is O(nlog(k)). Its not hard to see that n < nlog(k). Therefore, O(nlog(k)) dominates and is the correct runtime under these assumptions.
2nd, hashmap insertion is actually O(n) and not O(1) . So the algorithm is technically O(n^2).
These stuff is so useless to learn I can’t believe they are still around