Kth Largest Element in an Array
Вставка
- Опубліковано 3 лис 2018
- For business inquiries email partnerships@k2.codes SOCIAL
----------------------------------------------------------------------------------------------------------------
Support me on Patreon: / kevinnaughtonjr
Follow me on Twitter: / kevinnaughtonjr
Follow me on Instagram: / programeme
Follow me on GitHub: github.com/kdn251
My Desk Setup
Desk - bit.ly/3jfY195
Chair - amzn.to/2O9TM3r
Monitor - amzn.to/3rcSHGa
Webcam - amzn.to/2NUmwgi
Desktop - amzn.to/3tiySPL
Laptops - amzn.to/3aRoN3Z
iPad - amzn.to/2LlJzzJ
Keyboard - amzn.to/3jfbxdd
Mouse - amzn.to/36ElWtT
Wrist Rest - amzn.to/3trrHF4 (pls don't buy this)
Mouse Pad - amzn.to/2Myz2lt
Microphone - amzn.to/3atNyTA
Lamp - amzn.to/3jjfZYp
Headphones - amzn.to/3tvr0KU (new model)
Headphone Hook - amzn.to/3tr8uTC
Blue Light Glasses - amzn.to/3cDVUdK
Wireless Charger - amzn.to/39LY1uu
Keyboard cable - amzn.to/2O5p2R5
Mic arm - amzn.to/3cECZj8
Audio interface - amzn.to/36HdWIi
Cloudlifter - amzn.to/36VO6kf
Laptop dock - amzn.to/2O2DsBw
Motherboard - amzn.to/3rkiWuA
Solid state - amzn.to/3rk5vuo
CPU cooler - amzn.to/3tnwwPA
CableMod - amzn.to/3tqbtM8
CPU - amzn.to/3auG1ns
Power supply - amzn.to/3trsAxo
RAM - amzn.to/39JZcuf
Designing Data-Intensive Applications - amzn.to/2YK4ek1
Clean Code - amzn.to/3txqfB5
Meditations - amzn.to/3cDa4fi
MUSIC
----------------------------------------------------------------------------------------------------------------
A0000012.WAV by bsd.u - / a0000012wav Discord: bit.ly/K2-discord - Наука та технологія
![Kth LARGEST ELEMENT IN AN ARRAY - SOLUTION EXPLAINED [PYTHON]](http://i.ytimg.com/vi/AzDs7qV1ugA/mqdefault.jpg)
What problem / topic should I cover next?
subsets II
I'll check it out thanks for the suggestion!
Yes please make video on generating all substring, subsequences, permutations as well as those of given length (k given)...
Helpful video as always!
Also what should be my strategy for solving LeetCode problems? Can you suggest me on that?
I'll try to do some of those, thanks for the suggestion!
I beg to differ, the runtime is not O(N). You are right that we are simply inserting N elements to the heap, but under the hood inserting an element calls the heapify() method to move the newly added element to its correct position (in order to maintain the min/max heap integrity). Each insertion with its subsequent heapify call is O(logN). So we are more or less back to O(NlogN). Am I missing something?
This is a perfect video that prepares you for right before your interviewer asks you "okay, good... now can you do better?"
Quick Select is one of the ways the interviewer might be looking for.
I recently went to an interview and the interviewer expected to write QuickSelect. Then I found out that in average QuickSelect run in time O(n).
@@theschoolofalgorithms thanks!
That's really fantastic approach! . At first I was in confusion how Minheap play role here, then your explanation really made me think into power of Heaps.
Runtime should be O(nlogk)
using merge sort and get k index (leng-k)
Worst case is when k == n. Then it is similar to build a heap. Amortized time complexity for such a case is O(n).
@@mercuriallabs9 Why amortized complexity is O(n)? k is between 0 and n, and the mean is n/2, which is still in the order of n
@@Derek-np7ke K isn't a constant. we can only assume that K < n where n is the number of elements inside the array.
@@Derek-np7ke k actually can increase and decrease in size so its not a constant
Like one the comments previously mentioned, this is n log(k) which I guess (if I am not wrong) is upper bounded by n log(n) since k could be at most n. And there is a O(n) algorithm for this problem which is called quick select algorithm.
Yep you're totally right and yeah I think technically what you mentioned about the upper bound being nlogn is correct as well!
If I'm not wrong the worst case complexity of quick select is O(n^2) with an average case of O(n).
@@nerdydarkknight yes, that's correct
@@nerdydarkknight There is a "median of medians" algorithm that technically avoids the worst case O(n^2) and runs in linear time. So the quick select algorithm can be made to run in linear time as well, even for the worst case.
@@stablesort can you explain please in more depth?
Great video kevin. Just to bring up something I think you might have misspoken. The runtime went from O(NlogN) down to (Nlogk), which is better if and only if k < N (which it is). And space went down from O(N) to O(k).
Inserting into a heap is logN time, and since our heap is never bigger than K, this becomes a logK operation. We do this N times, so Nlogk.
Initially I was wondering how min-heap can be used here but later you explained it very well. I think adding an additional check to insert only elements greater than the minimum element in the heap can avoid unnecessary insertion of the elements and can further improve the performance of this algo. It won't improve it asymptotically though.
Thank you so much Kevin For your explanations . It really helped me alot . Very Nice way of teaching.
Hi Kevin, thanks for the videos, you rock, and all these videos help me more than anything. Can you create a playlist with the hardest Google interview questions that we need to focus on? I will go to onsite interview next Thursday and I will let you know if I can crack it! Cheers mate.
Thanks for your videos, can you please do some problems on dynamic programming. That will help immensely
best part of your videos is that you keep everything short!!
Awesome video, but I believe (as others have mentioned) the build heap step is O(nlogk) instead of O(n). However, there is a O(n) buildHeap approach which always add to the end of the heap and percolate down. so the total for build heap this way will be: (0 * n/2) + (1 * n/4) + (2 * n/8) + ... + (h * 1) which is bound by the O(n). It's just Java's PriorityQueue's `add` interface does not guarantee this buildHeap implementation.
2 Apple interviews coming up Tuesday/Wednesday. Would love to run a mock and get some advice before.
What is the result? Are you in company now?
Thanks for the video Kevin!
As a couple of others have mentioned, there is an O(n) algorithm, linear time selection or quick select. But I've only learned the algorithm on a theory level but struggle implementing the algorithm itself. As a hypothetical, if this question was asked during an interview, is it okay to give the heap solution instead of the other algorithm? If I don't think I can implement the algorithm within the time frame, should I even mention the O(n) algorithm?
Once again, fantastic video/series! Rather than asking for a specific problem, I'm more curious on how you're able to immediately recognize the solution to these problems. There are some [otherwise trivial] problems that I will get absolutely stumped on, and will check the problem discussions for the solution and realize that I would have never come to such solutions on my own (which leads to me getting discouraged and stepping away).. Would you mind explaining (or making a video) on what to look for in a questions' description when determining the approach to the problem?
Hey Dom, these questions are hard, don't beat yourself up!!! It's so normal to struggle with these questions and I often do, especially when I first started. I think recognizing possible solutions to these questions definitely comes easier as you practice. Chances are if you solve one question, there's 5 other questions that you'll be able to use the same approach for. Otherwise in general, if I don't have an idea right away, I try to systematically go through data structures and think..."can a stack be useful here...no...ok, can a binary search tree be useful here" etc. I hope this helps!
@@KevinNaughtonJr Thanks for the reply! You're right, just gotta find the time to practice more. It does definitely seem that some questions have the exact same approach, and are just worded differently. Systematically going through the data structures is a really cool approach and I'm going to start doing that now whenever I don't know where to start on a problem. Thanks again!
Anytime Dom lmk if there's anything else I can do to help and good luck! :)
There is an O(n) Algorithm using Kth other statistics which is basically built as nth_element() in cpp.
I would make a clear difference between the possible solutions:
1) Time: O (n log (n)) - (sorting and then accessing the n-k element)
2) Time: O(n log (k)) - using min heap
3) Time: O(n) - using quick select algorithm
More details and in depth explanation can be found here:
ua-cam.com/video/hGK_5n81drs/v-deo.html
I have to add that 2) solution (using min heap) it depends how the heap is built.
If the heap is built using "sift down" approach then the time complexity will become O(n)
If the heap is build using "sift up" approach, then the time complexity is O(nlogn)
Hi Kevin,
I'm preparing for my Google on-site (APM role) right now, and your videos are super helpful! I would love to have a chat (via phone/video) with you if possible. :) A huge thanks to you again!
Hey Soundarya, yeah let's do it! Shoot me an email and let's find a time to talk! kdn251@nyu.edu
hey did you get into Google?
follow up lol
follow up in 2022,
Kevin, How can I setup a call with you?
Just curious to see that, if we use max-heap here instead of min-heap, the complexity will be O(n^2).
When we will insert the k+1th element, we will have to remove the minimum element from the maxheap which will actually take O(n) time rather O( logn).
Hi Kevin, Thank you for easy solving this problem and great explanation. I have an interview in google in some days if you give me some advices.
Can you solve this using quick sort partitioning method? Thats more efficient and would love to see that solution
This question is related to order statistics. Making a video on that might be more helpful. That covers this question to the core.
I don't know much about order statistics but I think it's just what the question is asking i.e. find the kth largest element in a set of numbers. If I did know more about it maybe I would make a video :)
Hey kevin, the heapify run time is O(n) but in the worst case you have to pop everything from the heap with O(logn) for each operation, so this means the worst case time complexity is O(nlogn).
Also just adding numbers to a heap doesnt make it O(n).. its only O(n) if you properly do bottom-up heapify.. which if you did .. using a max heap would be ideal since you only need pop k
i have my first round of google interview in first week of november. Please advice if doing your playlist of easy leetcode and medium leetcode will suffice or shall i go ahead with hard ones as well ?
So what did you find out..
Is it ok to use PriorityQueue or Arrays.sort in actual interview? Would they expect us to implement heap from scratch?
Hi Kevin,
I'm your new fan from VietNam. Thanks for all your amazing video.
Isnt't the runtime O(n logk). We are basically calling heapify on every insert for a max heap height of log(k). And also, doesn't this now become similar to heapsort? Isn't heapsort generally slower than quicksort?
thanks a lot for these videos, will definitely see you someday in NYC office or in case you visit India someday then let us know.
Can i use max heap of size n and pop out the topmost element k-1 times while heapifying the rest of the heap (size of the heap keeps reducing just like in heapsort algorithm )and finally return the root (k th iteration) ??
That would take k*log n time if I'm not wrong ,better than n*log k because k
But to create the heap you will take complexity O(n) even if you heapify instead of bubbling
So really it is n + k log (n)
But I like your approach
I'm sorry if I make a mistake in judging the time complexity ,but won't it be O(ArraySize*log (k)) . Nonetheless, there is an algorithm that can do this in O(N) time, which always finds the approximate median and partitions the array. My questions is when I was implementing the said algorithm, I didnot take into account the case of duplicate numbers. What should I do for that, if you can help me ? Anyway thanks if you read my comment. I will also try your implementation.
Hey, can we use a priority queue and insert all elements to it and pop k-1 times ? Is it a bad solution?(c++)
The usual follow up is what if the input can't be fit in the memory ?
hey Kevin, Please share details of this airplane seating arranagemnt
A seating arrangement was to be designed for airplane management system which had an arrangement like [][]-[][][][]-[][] ( Pass way after the second and sixth seat ). It had three rows of such an arrangement.
A group can have members ranging one to four and no person in the group must be booked with a seat alone.
Write a code to allocate seats in such a manner that if the number of seats to be booked was
Four : Together in the middle positions or allocated in pairs .
Three : Only in the middle positions of the seating arrangement.
Two : Only in pairs in the available location.
One : If any unfilled position is available or in a position in sequence which is empty.
I think a better approach would be to go with quicksort algorithm.
We take an element and find its position in the array in O(n) time.
Then if the element's position is K we return the element.
If the element's position is less than K we do the same thing for the subarray greater than K else we do it again for subarray less than K until we reach the position of K.
Divide and Conquer approach.
Time Complexity : O(n) { Maximum iterations would be 2n}
Space complexity : O(1) { In place }
Hi Kevin, Thanks for your videos!
Any chance you would do a video for question 543 - diameter of binary tree?
I tried to figure out the solution, but didn’t get it throughout. If you have another awesome analogy (like the movie theater) it would be great 😅
Thanks a lot!
Hi Kevin, I'm currently preparing for my job interviews. I've covered almost all the aspects of DSA required. Can you please help me brush up on my skills? Thanks
It would be fantastic if you could do some graph questions from leetcode Kevin. Thank you!
Anytime I hope you enjoyed the video! I'll see what I can do about more graph problems in the future!
Wow, thats a nice little tip there. Replace sort with minHeap which brings down the time to O(n) right there. Awesome!
The runtime is actually O(nlogk) i mispoke sorry about that. nlogk because we have to go through n elements placing at most k of them into a heap I hope that makes sense if it doesn't lmk and I can explain further :)
Kevin Naughton Jr. Ah, then the difference is negligible. Not more efficient than sort, correct?
@@vigneshse it's a bit better, but it does depend on what k is (so technically it can degrade to O(nlogn) if k = n). Sorting will be O(nlogn) (or N^2 depending on the sorting algorithm used) regardless of the value of k
I WROTE ALL THIS CODE THINKING I WAS SOME SAINT AND THIS GUY FINISHES IT IN 2 LINES. O K. Buddy. I forgot about sorting
it should not be O(n). Removing from heap is logarithmic. As you keep K elements in the heap it is going to be log(k). So overall solution is O(n+ (n-k)* log(k)) , not O(n). Inserting into heap is constant so we only take removal of the elements into account. And why not Quick sort selection algorithm which takes ~ n on average ?
Kevin , what if array has duplicate numbers ? will it work ?
Can u expain the quick select algo?
Can someone explain me why would the kth largest number would be at root of the minHeap ? I am new to this and I thought we have to use maxHeap for the question.
But this heap approach runtime is around 4ms when I tried it in leetcode. When I use normal approach (Arrays.sort) runtime is 1ms. How can you say this is effective
Did not discuss the quickselect algorithm.
You said you were using a heat but it looks like you’re using a priority queue object. I don’t know what either one of those things are. What is that in JavaScript?
A max/min heap is a priority queue just based on value! I don't think javascript has a heap library :(
1:58 return nums[nums.length - k +1]; no?
I think we should use maxheap right. Will minheap be used here?
No
Just like sorting, adding the array elements to a priority queue would be O(n log n) time complexity. I give you that it is a cooler solution.
Hey Ronald! I believe you can actually build a heap in O(N) time where N is the number of elements you are inserting into the heap. The runtime becomes O(NlogN) normally because you remove all the elements from the heap (because the heap has to heapify with every removal). I think in the code I provided the runtime would actually be O(NlogK) because we are restricting the size of the heap to be at most K at any point in time. I hope that makes sense I'd love to hear your thoughts! :)
@@KevinNaughtonJr I mean, an insertion is log n time and you have n elements to insert. I don't see how it is linear. You are not just adding elements to the array, they have to be correctly placed after inserting them at the end of the array, or it would not be a min or max heap. Maybe we are talking about different things?
@@ronaldmackee3401 Nah I think we're talking about the same thing and it's hard to understand my tone because it's just a message but I don't want you to think I'm trying to prove you wrong or be mean or anything, but I believe building a heap is O(N) time. It's kinda mind blowing and you can look it up but from what I understand the general idea is that yes it takes O(logN) time to insert into a heap but the 1st insertion is constant time (because there are no elements in the heap...the 2nd insertion almost takes constant time...same for 3rd, 4th, 5th, etc...you eventually reach a point where it's it starts looking less like constant time and more like logN time so the runtime to build the heap is O(N) here's a link that will involve math but might help: stackoverflow.com/questions/9755721/how-can-building-a-heap-be-on-time-complexity (when I first learned about this it blew my mind). LMK your thoughts!
@@KevinNaughtonJr I see what you're saying, but let's consider that O(n log n) refers to the worst case, i.e., you have an initial array that is sorted in descending order (the code doesn't know, right?), and then you start populating a min heap from that array, so every insertion but the first has to be heapified up. Let's agree that Big O notation always refers to the worst case. That is pretty much my whole point.
@@ronaldmackee3401 Big O def is always worst case and I totally agree with your logic that it sounds like it would make it O(NlogN) but according to math I don't think that is a tight asymptotic bound (which I could reason with the math but not sure i can :( ). I'll have to do some more reading and hopefully I can understand it better then. It definitely seems like building a heap should be O(NlogN) but according to a ton of resources online it can be done in O(N)
Hi Kevin,
Your videos are very helpful and I am watching them on a regular basis.
I have google interview lined up next month, so just wanted to check if we can sync sometimes for a quick chit chat to make myself well prepared for the google?
Regards,
-Vikas
Thanks Vikas and congrats that's amazing!!! Check out my Patreon page I have a few different options that I think could help you prepare for your Google interview!
Could also negate the value, and then pop till that many in and then un-negate the value.
Wouldn't the last minHeap.remove() actually delete the Kth element? I am confused at the last line.
remove and return to removed element
I think solving this via a heap is very smart. I'm curious how this would be solved in Swift since Swift doesn't come with a pre-defined Heap like data structure (would have to write it custom or import some code). Any ideas?
Ok I found this: codereview.stackexchange.com/questions/145877/quickselect-algorithm-in-swift seems nice!
There is a better solution with quick select.
Is it? I thought the worst case for quick select is O(n^2)?
@@yathuarulnanthy5822 Yes, but the average case is faster, so it depends on what is more important for the person implementing it
@@yathuarulnanthy5822 so worst case happens on rare occasions ("more likely to get struck by lightning" according to the Cornell algo class on coursera) that is why it is safe to use it because it is more likely to get O(n) since we need to shuffle the array.
Also these videos were very useful to help me prepare for a few phone screens and an on-site at Goldman Sachs and at Amazon. I am having an on-site in two weeks with Goldman Sachs as well and am pretty sure I have to write code in that interview as well. Is there any resource that could be of help or even a time to mock interview so I can be more prepared
Hey Garen thanks so much I'm happy to hear that the videos have been helpful! I believe there are a few sites that offer mock interviews I also offer them on my Patreon if you're interested! www.patreon.com/KevinNaughtonJr
Really helpful
Thanks Abhinav!
Quick select algorithm works faster than this. Runtime is O(n)
I have an interview at Google in two weeks 😱😱😱... would love to do a mock interview session with you...
That's awesome congrats on getting the interview with Google! If you're interested in doing a mock interview check out the "Onsite" tier on my Patreon: www.patreon.com/KevinNaughtonJr
A asked about this problem in a forum because there were several solutions from different sources. Seems QuickSelect, Heap, and median of medians are all workable, but median of medians has the best performance. en.wikipedia.org/wiki/Median_of_medians. Is there a reason to use a heap instead of a median of medians?
Update: I have an answer, seems median of medians has extra overhead and the "real world" solution is QuickSelect. Kinda confusing when there are so many answers to one question.
Hey Karl, thanks for the comment. You're right it can be confusing when there are so many answers to a single question. Because of that I think it's always a good idea to try and lay out 2 or 3 approaches for a problem (to your interviewer) and pick one while explaining that specific solution's benefits. Some things to consider might be...runtime, space complexity, readability, scalability, etc.
This code will not work when we want to retrieve k=1. Please sugest
superb bro
can we do it from the QuickSelect Algorithm ? right ?
I was asked question to design a RDBMS database design schema for a UPI transactions system(my problem statement). I couldn't come up with relationships and table attributes correctly. Can you PLEASE MAKE A VIDEO ON DESIGNING DATABASE SCHEMA FOR A GIVEN PROBELM STATEMENT IN AN INTERVIEW ENVIRONMENT------PLEASEEEE🥺🙏
Actually the heap takes n*log(n) rutime, even with Fibonacci Heap. Quick select is faster
Hi Kevin, I have a google interview in 3 days. Could you please help me with few topics to focus on? I watched your playlists. Thanks in advance!
Hi, i am watching your videos to prepare my interview can you share me any good sample resume as it helps me since ny resume is getting rejected in many companies
good shortcut! In C++ I would just use nth_element ;-)
Hey Kevin can you help me prepare for the Google interview I am practicing quite a few algorithm
The runtime of this is actually O(nlogk) because you are inserting values in a heap of size k and insertion in a heap has O(logk) time. Do you know the space complexity of this algorithm?
Do you think interviewers would expect people to get the O(n) for this problem? It's much better, but way less obvious than the other approaches. Gotta use pivots and a divide and conquer approach. Worst case would be extremely rare with random pivots.
I honestly don't think they'd expect the O(n) solution. I agree I think it's not obvious at all and kinda overkill
That's where the preparation come in, better implementation is what separate the candidates!
@@mandeepgoyat934 I definitely think it depends on the question, but it can never hurt to do better :)
you need to solve it using partition, not sort/heap
The runtime of this is not O(n), for each element you are inserting and deleting from a heap of size k, and since insertions and deletions of a heap of size m is log(m), the runtime is O(n*logk)
Hey Praneeth, good catch you're totally right I misspoke!
@@KevinNaughtonJr I believe there is a O(n) solution though! It involves using the quickSort partition method, do you think Google would expect the O(n) solution or would the O(nlogk) solution be enough? Thanks! :)
I think you're right! Honestly, I really think if you got the O(nlogk) solution I think you're in great shape, but if you can offer an O(n) solution it can only help :) thanks for the comments!
@@KevinNaughtonJr Awesome!! I have an onsite next week haha! I actually just emailed you with a few questions about the interview, I've been grinding through your videos all day today! :)
haha happy to hear that thanks man! That's amazing congrats!!! Keep working hard it always pays off! I'll take a look at your email now :)
Hi Kevin,
I have a big interview coming in my way, i have roughly 30 days of time. For the same i have couple of questions , if you can help me on those that will be great -
1. How should i prepare ?
2. How to build problem solving approach like how would i know for any question that it should be solved with this approach or that approach.
3. Also, what i face more frequently is that lets say for any problem i was not able to solve it and then i looked at solution and understood very well and again after some days lets say 10 days if i try to solve the same problem, i get stuck.
How to tackle these, please help
mandeep kharb hey Mandeep if you’re preparing for an interview I’d recommend joining the interviewing service I created it’ll help teach you the most common topics and questions thedailybyte.dev/?ref=kevin I’d recommend joining the annual plan if you can. I also offer tons of other services like mock interview on my Patreon page if you think that could help you too! www.patreon.com/KevinNaughtonJr
Can you please implement this in Python? And, I will appreciate it if you any advice for me as I'm preparing for an interview with Google for TSE position!
I definitely can't off the top of my head but if I had to guess it's probably even easier in Python! I'd be happy to give you some advice maybe we can chat in the Discord channel if you're willing to join? Here's the link to join: www.patreon.com/KevinNaughtonJr
why bro stopped doing this 😭
hey where do you work? Big N?
yea he work at UA-cam making videos lol
this code for following example gives incorrect ans
Input:-
nums :- [3,2,1,5,6,4,10,11,12,13,15,15]
k:- 2
Output :-
15
which is logically incorrect because 2nd largest number should be 13 and not 15.
can someone do this implementation using priority_queue stl in c++?
Dude, this is wrong. Insertion into a heap is O(log(k)). Not O(1). It's O(nlogk).
class Solution
{
public int findKthLargest(int[] a, int k)
{
if(k>a.length)
{
return -1;
}
if(a==null || a.length==0)
{
return -1;
}
PriorityQueue minH=new PriorityQueue();
for(int i=0;ik)
{
minH.remove();
}
}
return minH.peek();
}
}
Hi Kevin
Your videos are great and have helped me a lot. I have sent you an email in hopes of connecting with you for further help. Thank you for the great videos!
Hey Farwa! Anytime thank you so much for the support! I'm emailing you back right now :)
@@KevinNaughtonJr Got it and responded back :)
@@farwaiftikhar2403 Awesome :) I just sent you an invite to the Discord server!
Its still worst case n log n if k is the size of the array
Adding to a heap is not O(n) it is O(log n) because it is inserted in the bottom of the tree and it has to traverse the tree upward
Hi, I have a interview lined up for one of the biggest company and I need your help in finding out answer to a design problem, whats the best way to reach you? (email id pls?)
Hi.. Can you please do a video on Leetcode Question 332. Reconstruct Itinerary.. Thank you
The way you had written the code is not good at all. U are doing repetitive work. The problem that I see is that first you are inserting an item into the heap which takes logn time and then checking if heap size extends k or not. If extends,then again u are removing the top item,means after k successful insertion,you are adding one item and then removing it again !!
The best way to optimize this that you should have segregated into two loops
priority_queue pq;
for(int i=0;i
And guys that is what happens when you don't quite know what you're talking about.
Time complexity is wrong.
Arrays.sort() ??
Java 98.26% faster / 1 ms
class Solution {
public int findKthLargest(int[] nums, int k) {
Arrays.sort(nums);
return nums[nums.length-k];
}
}
He is cute