I think Using bucket sort we can solve this problem in O(N) time complexity. Where we need to take the frequency of occurrences as index and append the corresponding numbers to that index.
Oh my god the way I got this question as part of my meta interview last year and I used min heap, yet the interviewer seemed confused on why I used it. Didn’t make it to next round :(
So you didn't know to explain that it was because lower time complexity? You have to understand that some problems have lots of solutions. If you don't show that your solution is superior, then it might just look like you did something overly complex for no reason.
Your calculation is wrong. Min/Max heap insertion: average time complexity: O(log n), do it for worst case (all unique numbers): O(n log n). Which might be a little faster than sorting. In addition if k=n (worst case) then it takes O(k log n) to pop elements. You got: O(n (log n + log k)) instead of O(nlogn). What am I missing?
Wait so here is how I think this works. Kth top elements can ever only be as large as n as you cannot have more top elements than exist in the list. Since k is at most the size n we can say in the worst case the algorithm is O(2logn) or O(logn)!
Yeah but you do realise big O is for the worst case. A lot of sources get this wrong but technically there are other ways to talk about best and average cases. So in terms of big O, the big O time complexity of bucket sort is still n squared. The average case is n
@@Krokodil986 well, we are sure about that. We have integer values from 1 to c, and each bucket represent it's own integer, so there are c buckets in total each with it's unique element. O(n + c). In this problem values are the number of times an element appears in the array. So they are not greater then n. c < n. O(n + c) = O(n + n) = O(n). Hope I'm making sense.
Since problem allows returning top k frequent elements in any order, better solution would be to use quickselect after hashmap step, then total complexity would stay linear on average Alternatively, you can build a second hashmap from frequency to list of numbers with given frequency and probe it with frequencies in range n..1, it will also give you O(n) solution for the second part.
1 idea sort array, nlogn 2 idea hashmap + top k storing something like sorted array of k elements, its n*k 3 idea is hashmap + heap, heap can store top k for log k so its n log k
4 idea is hashmap which is length of the array which where the index acts as the freq count and you store each value with that freq in it. that means you can scan once to generate tye counts and then move through the map from the end to fink k most frequent
Isn't it possible to solve it using simple traversing with reverse every number and check using the count function if it is equal to k if the number is equals to k we store the value and then we traverse and if the number is smaller than the number we have found equal to our cat number we do not do any traversing or any count function on that but if the number is greater than or number that has the cat time repetition then we check the count frequency of the number
This solution purely depends that your frequencies are sorted in ascending order because if your first key had frequency of 2 and last had frequency of 2 then your solution will fail as heap will return wrong numbers
@@mohamedfarid7742 Yes, but k can vary. So it makes sense to include it in the time complexity. You can't just ignore it and pretend its O(n logn). That does not make sense. That is like having 2 different arrays as input and saying time complexity is O(n^2) since their sizes are equal in the worst case, instead of saying O(nm). So yes, in the worst case for the problem, it's still O(n logn), but for the worst case for any particular k, its O(n logk), which will be much faster if k
@@mohamedfarid7742 no? Isn't K independent of n here? K represents the "top x" numbers. So if we're finding the top 2 most frequent like here, k=2. If we were finding the top 3 most frequent. k=3. Pretty sure it's independent of n here unless I'm missing something
In the description says the answer is unique. So while k is 2, the array can on only be like [ 1, 2, 4, 5, 4, 2] and not be like [ 1, 2, 4, 5, 1, 4, 2]
@@GregHogg Your vids are sometimes showing up on my feed so maybe I got those questionable ones. This one with a bit off calculations, just like TF2Shows mentioned. And the other where you presented linear solution with arrays that does not work in certain cases - unfortunately dont remember the specifics. I also don;'t assume you are perfect but when it comes from LeetCode it should fairly well tested.
Master Data Structures & Algorithms For FREE at AlgoMap.io!
Great. No longer/slower version of this video? :)
I think Using bucket sort we can solve this problem in O(N) time complexity. Where we need to take the frequency of occurrences as index and append the corresponding numbers to that index.
Min Heap i.e (Priority queue) also works on sorting, so using Min Heap the time complexity is still gonna be O(nlogn).
He keeps heap of size 2 only. So it's O(n)
o(nlogn + nlogk)
It’s O(n log k) the heap will have a max of k elements (2 in the video)
Got it. Heaps are the solution to everything
😂
Either that or a hashmap, if not that then both 😂
🤣🤣
They are pretty awesome 😎
Using bucket sort is also a solution. Use bucket sort but take instances of numbers as the key and occurences as the value.
Oh my god the way I got this question as part of my meta interview last year and I used min heap, yet the interviewer seemed confused on why I used it. Didn’t make it to next round :(
he must be used to either the brute for e solution or the hashmap bubble sort method
So you didn't know to explain that it was because lower time complexity?
You have to understand that some problems have lots of solutions. If you don't show that your solution is superior, then it might just look like you did something overly complex for no reason.
Rough.
Your calculation is wrong.
Min/Max heap insertion: average time complexity: O(log n), do it for worst case (all unique numbers): O(n log n). Which might be a little faster than sorting. In addition if k=n (worst case) then it takes O(k log n) to pop elements.
You got: O(n (log n + log k)) instead of O(nlogn). What am I missing?
Wait so here is how I think this works. Kth top elements can ever only be as large as n as you cannot have more top elements than exist in the list. Since k is at most the size n we can say in the worst case the algorithm is O(2logn) or O(logn)!
You completely misunderstood the solution. I don't know where to begin.
I agree with @TF2Shows. You can build a heap from an array in O(n), but removing the top k elements would still be O(k*log(n))
@@Andy-nt8tqif you build heap of size k then it will be klogk.
@@Andy-nt8tq if the k = n then you remove zero elements from the heap
also, you can solve this in O(n) time with a bucket sort, it just costs extra memory, tradeoffs
Yeah but you do realise big O is for the worst case. A lot of sources get this wrong but technically there are other ways to talk about best and average cases. So in terms of big O, the big O time complexity of bucket sort is still n squared. The average case is n
Yeah, and you could also use quickselect.
@@Krokodil986it's actually O(n + c), not O(n^2)
@@arsenypogosov7206 that's only if you are sure each bucket represents a unique value, which it won't be here
Otherwise it's O(n^2)
@@Krokodil986 well, we are sure about that. We have integer values from 1 to c, and each bucket represent it's own integer, so there are c buckets in total each with it's unique element. O(n + c).
In this problem values are the number of times an element appears in the array. So they are not greater then n. c < n. O(n + c) = O(n + n) = O(n).
Hope I'm making sense.
Since problem allows returning top k frequent elements in any order, better solution would be to use quickselect after hashmap step, then total complexity would stay linear on average
Alternatively, you can build a second hashmap from frequency to list of numbers with given frequency and probe it with frequencies in range n..1, it will also give you O(n) solution for the second part.
In C++ Map is already sorted, you can change the compare function to be greater than and just do the 2nd portion
map is sorted by the keys not the values.
1 idea sort array, nlogn
2 idea hashmap + top k storing something like sorted array of k elements, its n*k
3 idea is hashmap + heap, heap can store top k for log k so its n log k
4 idea is hashmap which is length of the array which where the index acts as the freq count and you store each value with that freq in it. that means you can scan once to generate tye counts and then move through the map from the end to fink k most frequent
@@mark1A100even better, don’t use a hashmap and use an array of lists to avoid collisions
Hash map -> stack with max k elements with min freq element at top
Why not just iterate the hashmap and store the top two frequencies as you traverse? O(n) for building the hashmap + O(n) for traversing the hashmap
K can be anything not just 2, so traversing through may keys won't give you the top k elements
Isn't it possible to solve it using simple traversing with reverse every number and check using the count function if it is equal to k if the number is equals to k we store the value and then we traverse and if the number is smaller than the number we have found equal to our cat number we do not do any traversing or any count function on that but if the number is greater than or number that has the cat time repetition then we check the count frequency of the number
❤ unbelievable 😮
This solution purely depends that your frequencies are sorted in ascending order because if your first key had frequency of 2 and last had frequency of 2 then your solution will fail as heap will return wrong numbers
But aren't the heap operations O(log n)?
Isn't the complexity of the second solution also be O(n log(n))?
The "n" refers to the size of the heap. So since the heap is never bigger than "k", we get O(n logk). Be careful with what you refer to as "n".
k can be equal to n if each element appear only once, so the worst case is still the same
@@mohamedfarid7742 Yes, but k can vary. So it makes sense to include it in the time complexity. You can't just ignore it and pretend its O(n logn). That does not make sense.
That is like having 2 different arrays as input and saying time complexity is O(n^2) since their sizes are equal in the worst case, instead of saying O(nm).
So yes, in the worst case for the problem, it's still O(n logn), but for the worst case for any particular k, its O(n logk), which will be much faster if k
@@mohamedfarid7742 no? Isn't K independent of n here? K represents the "top x" numbers. So if we're finding the top 2 most frequent like here, k=2. If we were finding the top 3 most frequent. k=3. Pretty sure it's independent of n here unless I'm missing something
Why wouldnt you pull the elements off the hm where the frequency is k
Optimal solution would be to use bucket sort
Correct!
I think hash map is overkill. Like why would you need heap of you already have that map. You can go through it and extract top k elements anyway
You could indeed sort the dictionary although that's n log n
You should try k most frequent words
leetcode 692, a similar idea with an added condition
Thanks, I will actually try that and might end up making a short about it! I love question suggestions. Cheers!
bucket sort will be O(N)
Indeed it will be!
Now that one I get it right away
Hm what if there are 3 frequent elements ?
In the description says the answer is unique. So while k is 2, the array can on only be like [ 1, 2, 4, 5, 4, 2] and not be like [ 1, 2, 4, 5, 1, 4, 2]
Isn’t this a max heap?
Counter(nums).most_common(k)
You know your python!
It's 50/50 if the video is actually correct or not. You need to make sure you are correct in those vids
Easy for you to say when you’re wrong 100% of the time.
@@arsheyajain7055 Easy to say when you get your knowledge from resources with wrong calculations or even wrong solutions
@@tarsala1995 get a life.
I think I've been wrong precisely once. So like 119/120 at this point or so. I apologize if I'm ever wrong lol not perfect and don't pretend to be
@@GregHogg Your vids are sometimes showing up on my feed so maybe I got those questionable ones. This one with a bit off calculations, just like TF2Shows mentioned. And the other where you presented linear solution with arrays that does not work in certain cases - unfortunately dont remember the specifics. I also don;'t assume you are perfect but when it comes from LeetCode it should fairly well tested.
Bro we get it you love hashmaps
Oh yeah I do
This guy will be the reason you don’t get that interview at meta 😂
Ouch
I feel so weird for liking these too much.
Hehe
Is coding relevant in this AI era?
connor
Where's the code
yikes. just do a O(n) scan of the hash map.
That's not O(n).
@@chillfill4866You're right. it's O(k) better than O(k log_k) with the heap.
I came to the same conclusion. Finding max element in hashmap will be O(n). Same for top two elements
That is O(nk). Doing a O(n) scan k time...?
@mujtabarehman5255 I thought k is always 2 in this task. Now i realize it's a parameter too, so linear scan is no good for big k
I swear it's always hashmaps/heaps
Pretty common, yeah! Haha
Ooh copilot
why u sounds like squidward ?
Why you types wrong?
bro is repeating questions 10times for the views💀 toxic content
Don't listen to this guy 😅