Good day. I don't ever comment. However, I just wanted to say that all your videos are really helpful to both me and many others. I respect the level of time and effort you put into these video and how many people you are helping. What most tutors/lecturers don't understand is that even you help that ONE child at the back of the class, they might just end up being able to build the next big startup. This being just because of the extra effort people like you put. Of course the material is NOT easy. However, I respect and thank you for both me and many others who are really struggling or just want enrichment. So hopefully you can keep it up and just know that there is at least someone who benefits from your effort (probably many though). Channels like these are hard to come by. So please keep up the good work. You will never know who it may help!
"even you help that ONE child at the back of the class" I resonate with that the most. The problem with lectures is that it is always tens of people anywhere in the classroom that are confused but don't speak up because a lecture is a hard environment to be a real, inquisitive, student in. (this is why whenever I get a youtube comment I try to say..."keep asking questions" because if a student is afraid to ask...they lose the very curiosity that makes a great lesson...you know that quote....'the teacher and the student make the teaching' or something like that) Thank you for your comment. It is a lot of work and every week I have to tell myself to keep doing this (but I mean...I want to make it sustainable eventually with products I'm building right now, etc...at that point I won't need motivation because this will hopefully be a sustaining business) This comment served as my weekly energy renewal :)
As the student in the back, thank you. I think it’s videos like these that really make me want to also help students out since we’ve all been there. I feel a great level of gratitude
Huge respect to this guy. The way he phrased his sentences, like " We are doing more work than we need to" , these will help you and move you in the direction of optimizing your solution. Thanks for the videos my dude.
I don't usually comment but this is the best explanation for quick select algorithm ever ! All of your videos are amazing and easier to understand than many other resources online. Thank you so much !!
Man, you're like a brother to me. I've learnt so much from your simple videos that I couldn't from my college years. Thanks a lot. I am considering binge watching your whole channel.
Among other TH-camrs, your way of explaining the thought process besides logic (which other coding channels usually lack) is right at the top. Awesome content. Thank you good sir!
Check out the free DSA Mini-Course 👉backtobackswe.com/five-day Table of Contents: Shameless Self Promotion & Useless Talking 0:00 - 0:45 The Problem Introduction 0:45 - 2:20 Approach #1: Just Sort The Array & Count K Back 2:20 - 3:50 Approach #2: Heap Based Approach 3:50 - 5:02 Min Heap Approach Walkthrough 5:02 - 7:41 Seeing How We Can Improve Further 7:41 - 9:51 We Realize What We Need To Do 9:51 - 10:43 Where Will The k'th Largest Element End Up? 10:43 - 13:19 Approach #3: Walking Through A Partition Step 13:19 - 16:58 Approach #3: The Deep Deep Deep Understanding 16:58 - 20:43 Analysis: Looking At The Recurrence 20:43 - 24:53 Analysis: Solving The Recurrence 24:53 - 27:14 Analysis: Our Final Result 27:14 - 28:11 Wrap Up (and space complexity) 28:11 - 29:54 Comments: 27:35 -> What we just solved is the recurrence for the Best Case where we choose a pivot that is the median in the partitioning space and the resulting input gets split perfectly in half. This is not a rigorous Average Case analysis but it approximates what will generally happen very well so that we can see why the asymptotic complexity will be O(n). (and it is also Ω(n)...so therefore the runtime is Ө(n)). The code for this problem is in the description. Fully commented for teaching purposes.
I really like how in-depth your videos are. Comparing to many other channels where people either go lightning fast or just gloss over the details, your step by step handholding and the big O analysis rock! I know what is next on my bingewatch list. ;-)
I also never ever comment videos, and I never ever subscribe, specially when somebody asks me to subscribe. Nevertheless, your videos show a couple things: 1) A great amount of effort to condense the information to what's truly needed 2) An intuitive explanation 3) Barely any overhead in the video itself 4) Charisma when teaching 5) The importance of sharing knowledge For this I am very thankful, subscribed and if you open a Patreon or alike, willing to contribute to your cause. Kudos.
Great Video. The way you walked us through the problem and ended up at the average linear time solution was brilliant. Appreciate you taking time out to make such videos.
Excellent vids. Good sense of humor. Clear explanations. Two things: I have seen the partitioning solution *after* the date you posted this, but have never come across it before -- or seen references in videos prior. Is this your solution? Incredible! The other thing: when referring to a "good" pivot, you are of course thinking quicksort. This is different. If I have a million item array and I want the 20th largest, the best first pivot should be just smaller than the 20th largest. You *read* a million elements, and if they're larger, you *swap* them. So if your pivot is (for instance) 999900, you only do the swap like 100 times. This is good for speed. And then your next search is finding your k-spot in a list of 100 items. See how much faster that goes? Instead of n + n/2 + n/4 ... it's more like n+200. YMMV Hope you like this twist HALF as much as I enjoyed discovering "your" partitioning solution. It was a delight! (there *is* a general case and there *is* a quick pivot-finding algo)
11:50 is literal gold, I never thought of representing K and N in that way visually. It makes accessing K and thinking about how to index into it manageable. Freaking awesome.
@@BackToBackSWE Again appreciate this video, I swear I was struggling all day to try to understand this algorithm, and I watched your video, then your quicksort video, and then whiteboarded some examples on paper and finally got it. Thanks a ton.
Reading up on quickselect thru leetcode solutions wasn’t effective at all for me but this video is simply brilliant. Realizing that we don’t have to perfectly sort EVERY integer is the first thought that tells us a heap is overkill, then using a pivot from quicksort to partially sort ONLY the half of the array we care about (and split the array further with each pivot) is the second thought that makes sorting FASTER possible. Really going into depth on how we conceptualize quick Select is what’s more valuable than the code itself. Explaining it this way is sure to blow the interviewer’s mind as it shows the raw thought process being formed from simple observations.
One of your best videos when it comes to an explanation. It's clearly visible that you have put your heart and soul while explaining deeper logic. What an honest effort, may you get all the success you wish for!
I just went through just once. Its been looong that i dont even remember what is quick sort. but with this video i just understood quick sort as well as how and where to apply quick sort. Good work buddy.
Benyam, you are a gem of teacher and person. This is by far the best way to make me think. Thanking is not enough but thank you. Specially for keeping it for free, many of us could not have stumbled upon this or be able to afford this level of video. Please do keep up and more love from India. Btw, the donation option doesn't work in India yet and i'm sure your fans like me in India would like to contribute in some capacity.
It's awesome that you showed the entire thought process, including the well-worth detour of heap solution. Also the time analysis part is eye-opening. Unlike the merge sort, we avoided the sorting in partitions, leaving only the n/2^i as the leading term in big O, which adds up to O(n). Thanks for going into all the details, it really pays off as a better learning outcome!
I am a programming newbie and I am learning a lot from your channels. Just one observation, from your python code, where there is a while loop (while left
The distinction between: i. T(N) = T(N / 2) + O(N) ii. T(N) = *2* T(N / 2) + O(N) took me by surprise! _sigh_ stupid me I've been watching some of your lectures for a while. I've gotta say, you're a really good teacher. Keep up the good work! :)
@@BackToBackSWE yes any element can be the pivot ..But since we have to make a search space from L to R , so its better to choose last element, just an opinion:)
29 minutes of explanation multiple levels of complex thought involved both in math and computer science so much so that trying to explain it gets you kicked out of buildings .... LeetCode - Problem difficulty = Easy
Could you provide the order that we should follow to watch those videos? Because the beginning of the video shows that you've already covered the sorting methods, but it is the 2nd video in this "Sorting, Searching, and Heaps" playlist, so I got a bit confused by which one to start. Thanks for teaching, and your videos are really easy to understand and get to the point!
Hey, I'm rapid fire responding to comments (I got behind 250 after 2 weeks) I'd answer this but in a hurry, so sorry I recommend no specific order, just work on what you are weak on ...at one point in time I could answer everything ugh - ben
I think you could have just said, in the complexity analysis part, that the sum from i = 0 to something of (1/2)^i, is strictly less than the sum from i=0 to infinity of (1/2)^i = 2, and so you end up with the answer being less than 2n - log(n), therefore it is linear complexity.
You're awesome!! Appreciate all your efforts that you put in to explain a problem, the thought process, solution, time complexity analysis. Huge respect for you!
Makes such great sense... you do amazing work. Thanks... Finding the big of the work.. I still totally suck at that .... thanks for doing great work for us all
I have watched so many videos till now and still you are the best. Man you make these concepts feel so easy and your videos are damn amazing and very easy to understand. Thank you so much and also its available for free loved them man
The explaination was too simple but the complexity analysis was little complicated to understand. However the code implementation was so easy t understand that this problem looks easy for me. Thanks a lot :)
@Back To Back SWE what do you think about what if you first build_heap in O(n) then rather than going for largest-MIN HEAP and smallest-MAX HEAP...... we can actually go largest-MAX HEAP and smallest-MIN HEAP delete k elements 1 by one from build_heap Array that way complexity will be klog(n).
Buddy, I think you have calculated the average case time complexity. What happens if pivot doesn't manages to split the array in halves, and the pivot happens to be one of the extremes. In that case, the worst case time complexity would be T(n)=T(n-1)+(n-1), which evaluates to O(n^2), which is even worse than heap-based approach. But anyways, I liked the way you think.
@@growingwithtech Ah, yeah, rewatched it, yes the worst case is O(n^2). I analyzed the best case (where we assume a 50/50 split), and it follows near the same reasoning as the average case (where we assume a 75/25 split) which also bounds to O(n). More on the average case: web.stanford.edu/class/archive/cs/cs161/cs161.1138/lectures/09/Small09.pdf Thanks for the question
for choosing the pivot int choosenPivotIndex = rand.nextInt(right - left + 1) this should be enough to pick a random index correct, why we need to add left for this. Please help me to understand
One question on the heap solution: are we supposed to implement the heap bottom to top before solving problems in real interview (in case that's the solution we come up with)? Just thinking it'd be quite hard to do heavy and bug-free implementations under gunpoint.
When using a heap for this particular problem, isn't it faster to build a heap in O(n) and then call heappop k times? Building a heap and calling heappop k times is O(k*log(n)) while your approach is O(n*log(k)), and I believe asymptotically O(k*log(n)) < O(n*log(k)) right? Awesome video and thanks!
What if we use a max heap for kth largest element. 1. Creation of max heap for n elements will take O(n) time. 2. Perform extract_max k-1 times will take O(k log(n)) time. So total time complexity = O(n)+O(k logn) = O(n). Am I correct with this one?
Could you please make a video on - finding kth smallest element in a row wise and column wise sorted array? How to extend the heaps solution to that question ? (I saw your - Search A 2D Sorted Matrix video and it was awesome.. I wanted to know how heaps can be used in that scenario) Thanks :)
Great video! I was curious to know what the case would be if the array had non-unique integers also? In that case would the QuickSort type algo still work ? Nice one.
@@BackToBackSWE could you please do a video on this using binary search since the question i encoutered was doing this in constant space and the array cant be modified. Also, I am always confused in binary search and in some other questions, why do we take left
This partitioning is linear time only when we can ensure the pivot is proper right? but when we measure an algorithm's time complexity, do we not go by the worst case? And when we choose the pivot to be the worst(largest element), we would lose the entire left partition and thus losing the actual answer too in some cases right? Please clarify if am I missing something
I am not certain why you are using a min-heap If you are interested in the largest item. A max-heap will have the largest item at the top which gives you easy access. if you are interested in the smallest then a min-heap will have the smallest at the top. But here we are given k'th largest or k'th smallest which can be anywhere within the heap so using a min or max heap will not matter much
The pivot just defines the value we partition against. We split in half (in a best case) since that is most optimal and if a good pivot is choosen then that will happen.
Back To Back SWE thx for quick reply. I was just making an assumption that the first pivot is the highest index and you keep searching towards to left partition..
![BOWKYLION - วิงวอน (ex-change) [Official MV]](http://i.ytimg.com/vi/cLdnZWDaO-w/mqdefault.jpg)
Good day. I don't ever comment. However, I just wanted to say that all your videos are really helpful to both me and many others. I respect the level of time and effort you put into these video and how many people you are helping. What most tutors/lecturers don't understand is that even you help that ONE child at the back of the class, they might just end up being able to build the next big startup. This being just because of the extra effort people like you put. Of course the material is NOT easy. However, I respect and thank you for both me and many others who are really struggling or just want enrichment. So hopefully you can keep it up and just know that there is at least someone who benefits from your effort (probably many though). Channels like these are hard to come by. So please keep up the good work. You will never know who it may help!
"even you help that ONE child at the back of the class" I resonate with that the most. The problem with lectures is that it is always tens of people anywhere in the classroom that are confused but don't speak up because a lecture is a hard environment to be a real, inquisitive, student in. (this is why whenever I get a youtube comment I try to say..."keep asking questions" because if a student is afraid to ask...they lose the very curiosity that makes a great lesson...you know that quote....'the teacher and the student make the teaching' or something like that)
Thank you for your comment. It is a lot of work and every week I have to tell myself to keep doing this (but I mean...I want to make it sustainable eventually with products I'm building right now, etc...at that point I won't need motivation because this will hopefully be a sustaining business)
This comment served as my weekly energy renewal :)
I6
As the student in the back, thank you. I think it’s videos like these that really make me want to also help students out since we’ve all been there. I feel a great level of gratitude
Huge respect to this guy. The way he phrased his sentences, like " We are doing more work than we need to" , these will help you and move you in the direction of optimizing your solution. Thanks for the videos my dude.
thanks - this guy
@@BackToBackSWE haha
"We're doing more work than we need to " that is a very clever way to think about a solution's quality while solving a problem.
yeah
I don't usually comment but this is the best explanation for quick select algorithm ever ! All of your videos are amazing and easier to understand than many other resources online. Thank you so much !!
thanks
Man, you're like a brother to me. I've learnt so much from your simple videos that I couldn't from my college years. Thanks a lot. I am considering binge watching your whole channel.
Haha, nice to hear, I mean, as humans we are all siblings. Anyway, glad they are helping you. - Ben
the best channel for preparing coding interview
I know. Give me 2 more years. TH-cam is 😴😴😴 on me.
Facts.
@@colorfulcodes hahaha
Your understanding of the fundamental concepts is phenomenal and rare to find.
thanks
Among other TH-camrs, your way of explaining the thought process besides logic (which other coding channels usually lack) is right at the top.
Awesome content.
Thank you good sir!
Check out the free DSA Mini-Course 👉backtobackswe.com/five-day
Table of Contents:
Shameless Self Promotion & Useless Talking 0:00 - 0:45
The Problem Introduction 0:45 - 2:20
Approach #1: Just Sort The Array & Count K Back 2:20 - 3:50
Approach #2: Heap Based Approach 3:50 - 5:02
Min Heap Approach Walkthrough 5:02 - 7:41
Seeing How We Can Improve Further 7:41 - 9:51
We Realize What We Need To Do 9:51 - 10:43
Where Will The k'th Largest Element End Up? 10:43 - 13:19
Approach #3: Walking Through A Partition Step 13:19 - 16:58
Approach #3: The Deep Deep Deep Understanding 16:58 - 20:43
Analysis: Looking At The Recurrence 20:43 - 24:53
Analysis: Solving The Recurrence 24:53 - 27:14
Analysis: Our Final Result 27:14 - 28:11
Wrap Up (and space complexity) 28:11 - 29:54
Comments:
27:35 -> What we just solved is the recurrence for the Best Case where we choose a pivot that is the median in the partitioning space and the resulting input gets split perfectly in half. This is not a rigorous Average Case analysis but it approximates what will generally happen very well so that we can see why the asymptotic complexity will be O(n). (and it is also Ω(n)...so therefore the runtime is Ө(n)).
The code for this problem is in the description. Fully commented for teaching purposes.
A big thank you for this video. Also, could you please tell me good resources from where I could practice time complexities of recurrance relations
sure and you can just google stuff, no specific resource
@@BackToBackSWE I don't see the code in the description, I've tried to make this algo in code myself but it's not working out.
@@mriKsuN i just saw some line explaining the code not the actual code.
@@shyammuppidi2092 github.com/bephrem1/backtobackswe/blob/master/Sorting%2C%20Searching%2C%20%26%20Heaps/KthLargestElement/KthLargestElement.java
I really like how in-depth your videos are. Comparing to many other channels where people either go lightning fast or just gloss over the details, your step by step handholding and the big O analysis rock! I know what is next on my bingewatch list. ;-)
I also never ever comment videos, and I never ever subscribe, specially when somebody asks me to subscribe. Nevertheless, your videos show a couple things:
1) A great amount of effort to condense the information to what's truly needed
2) An intuitive explanation
3) Barely any overhead in the video itself
4) Charisma when teaching
5) The importance of sharing knowledge
For this I am very thankful, subscribed and if you open a Patreon or alike, willing to contribute to your cause. Kudos.
thanks for the detailed analysis haha
Great Video. The way you walked us through the problem and ended up at the average linear time solution was brilliant. Appreciate you taking time out to make such videos.
sure
Excellent vids. Good sense of humor. Clear explanations. Two things: I have seen the partitioning solution *after* the date you posted this, but have never come across it before -- or seen references in videos prior. Is this your solution? Incredible! The other thing: when referring to a "good" pivot, you are of course thinking quicksort. This is different. If I have a million item array and I want the 20th largest, the best first pivot should be just smaller than the 20th largest. You *read* a million elements, and if they're larger, you *swap* them. So if your pivot is (for instance) 999900, you only do the swap like 100 times. This is good for speed. And then your next search is finding your k-spot in a list of 100 items. See how much faster that goes? Instead of n + n/2 + n/4 ... it's more like n+200. YMMV Hope you like this twist HALF as much as I enjoyed discovering "your" partitioning solution. It was a delight! (there *is* a general case and there *is* a quick pivot-finding algo)
11:50 is literal gold, I never thought of representing K and N in that way visually. It makes accessing K and thinking about how to index into it manageable. Freaking awesome.
thanks haha, I don't remember what I say in like all my videos
@@BackToBackSWE Again appreciate this video, I swear I was struggling all day to try to understand this algorithm, and I watched your video, then your quicksort video, and then whiteboarded some examples on paper and finally got it. Thanks a ton.
@@SocajowaRS nice
cuz u noob
This is the best explanation of quick select I have found online. Thank you for this video.
Reading up on quickselect thru leetcode solutions wasn’t effective at all for me but this video is simply brilliant. Realizing that we don’t have to perfectly sort EVERY integer is the first thought that tells us a heap is overkill, then using a pivot from quicksort to partially sort ONLY the half of the array we care about (and split the array further with each pivot) is the second thought that makes sorting FASTER possible. Really going into depth on how we conceptualize quick Select is what’s more valuable than the code itself. Explaining it this way is sure to blow the interviewer’s mind as it shows the raw thought process being formed from simple observations.
yuh
One of your best videos when it comes to an explanation. It's clearly visible that you have put your heart and soul while explaining deeper logic. What an honest effort, may you get all the success you wish for!
Yeah haha, this is fire. Thanks haha
I just went through just once. Its been looong that i dont even remember what is quick sort. but with this video i just understood quick sort as well as how and where to apply quick sort. Good work buddy.
Benyam, you are a gem of teacher and person. This is by far the best way to make me think. Thanking is not enough but thank you. Specially for keeping it for free, many of us could not have stumbled upon this or be able to afford this level of video.
Please do keep up and more love from India.
Btw, the donation option doesn't work in India yet and i'm sure your fans like me in India would like to contribute in some capacity.
Dude, your explanation! Absolute magic. Better than the paid courses!
thanks
Thanks from China.I liked several videos of you since I met your channel yesterday. Really appreciate the details and the way you present.
Keep it up man, I really think this channel will be well known very soon.
working on it
You know that feeling when it just clicks. You and NeetCode always get me there. Thanks for all your hard work
It's awesome that you showed the entire thought process, including the well-worth detour of heap solution. Also the time analysis part is eye-opening. Unlike the merge sort, we avoided the sorting in partitions, leaving only the n/2^i as the leading term in big O, which adds up to O(n). Thanks for going into all the details, it really pays off as a better learning outcome!
No one can ever match your style of explanation. Super !
thanks
Hey man, you have the best algo + ds explanations and walkthroughs on the entire internet. Bar none. Was a wahoo but go terps lol.
thanks! yeah uva is perty
I am never going to forget quicksort because you taught me how to actually use it. Beautiful explanation
ye
I am a programming newbie and I am learning a lot from your channels. Just one observation, from your python code, where there is a while loop (while left
Keep Making Videos please....a humble request from your regular student..you are truly a great teacher
ok, say no more, I got u
The distinction between:
i. T(N) = T(N / 2) + O(N)
ii. T(N) = *2* T(N / 2) + O(N)
took me by surprise! _sigh_ stupid me
I've been watching some of your lectures for a while. I've gotta say, you're a really good teacher. Keep up the good work! :)
Thanks. Yeah, former bounds to linear time, latter bounds to n*log(n)
Ben, it's amazing the amount of knowledge you have on CS fundamentals, I am learning a lot, thank you!
haha, thanks
I like the way you walked through your thought process.
Why do we get largest from min heap? The root of min heap is smallest, so isn't it more beneficial to use a max heap?
This man is better than 90% of my cs department at explaining these concepts
14:00 you choose first element as pivot and swap it to the last , rather than doing this directly choose the last value as pivot.
Any number can be the pivot? Why the last?
@@BackToBackSWE yes any element can be the pivot ..But since we have to make a search space from L to R , so its better to choose last element, just an opinion:)
29 minutes of explanation multiple levels of complex thought involved both in math and computer science so much so that trying to explain it gets you kicked out of buildings ....
LeetCode - Problem difficulty = Easy
lol
Could you provide the order that we should follow to watch those videos? Because the beginning of the video shows that you've already covered the sorting methods, but it is the 2nd video in this "Sorting, Searching, and Heaps" playlist, so I got a bit confused by which one to start. Thanks for teaching, and your videos are really easy to understand and get to the point!
Hey, I'm rapid fire responding to comments (I got behind 250 after 2 weeks) I'd answer this but in a hurry, so sorry
I recommend no specific order, just work on what you are weak on
...at one point in time I could answer everything ugh - ben
I think you could have just said, in the complexity analysis part, that the sum from i = 0 to something of (1/2)^i, is strictly less than the sum from i=0 to infinity of (1/2)^i = 2, and so you end up with the answer being less than 2n - log(n), therefore it is linear complexity.
You're awesome!! Appreciate all your efforts that you put in to explain a problem, the thought process, solution, time complexity analysis. Huge respect for you!
thanks and sure and thx
This is my 2nd or 3rd comment ever on TH-cam. But all I wanna say is: "I wish there was a provision of giving more than one like". Thanks a lot.
Hahahahhahaha, this vid was fire, not sure if I can drop more like it. Let's see haha
Amazing explanation!This has really helped me understand how partitioning works , and the details that i have missed .
great to hear
Its amazing how easy your explanations are
Makes such great sense... you do amazing work. Thanks... Finding the big of the work.. I still totally suck at that .... thanks for doing great work for us all
BRO... you also need to share your upper push body workout. You are in great shape
hahahahaha
I have watched so many videos till now and still you are the best. Man you make these concepts feel so easy and your videos are damn amazing and very easy to understand. Thank you so much and also its available for free loved them man
After watching so many videos this video helped thanks a lot brother
sure
Mannn you are the kinggg❤️❤️
A day before the exam on data structures i saw this video.. N this question was on the exam 🙂🙂
hahaha nice
The explaination was too simple but the complexity analysis was little complicated to understand. However the code implementation was so easy t understand that this problem looks easy for me. Thanks a lot :)
cool
Thank you for all videos ! Very understanble !
Glad you like them!
Huge respect to this guy! Thanks a lot, these videos are amazing!
@Back To Back SWE what do you think about what if you first build_heap in O(n)
then rather than going for largest-MIN HEAP and smallest-MAX HEAP......
we can actually go largest-MAX HEAP and smallest-MIN HEAP
delete k elements 1 by one from build_heap Array that way complexity will be klog(n).
Congratulations your final dialogue of happiness in everyone's life earned you a subscribe. Aight imma make my chemistry major roommate subscribe too.
wut
you are too good Ben! your videos are very helpful. please keep making them.
haha ok, I will, as long as I'm a live
You have the best explanations I have ever seen. Definitely earned a sub.
welcome, you are loved
Buddy, I think you have calculated the average case time complexity. What happens if pivot doesn't manages to split the array in halves, and the pivot happens to be one of the extremes. In that case, the worst case time complexity would be T(n)=T(n-1)+(n-1), which evaluates to O(n^2), which is even worse than heap-based approach. But anyways, I liked the way you think.
What was the recurrence I solved?
You solved for the best case i.e., T(n)=T(n/2)+(n-1)
@@growingwithtech Ah, yeah, rewatched it, yes the worst case is O(n^2).
I analyzed the best case (where we assume a 50/50 split), and it follows near the same reasoning as the average case (where we assume a 75/25 split) which also bounds to O(n).
More on the average case: web.stanford.edu/class/archive/cs/cs161/cs161.1138/lectures/09/Small09.pdf
Thanks for the question
Exactly!! Thanks for the clarification
for choosing the pivot int choosenPivotIndex = rand.nextInt(right - left + 1) this should be enough to pick a random index correct, why we need to add left for this. Please help me to understand
to compute the range of numbers?
Your explanations are so easy to understand.Thanks a lot🙌🙌
Very good teaching style. Thanks for the tutorial!
sure
as a math lover I really enjoy your explanations, thanks man
One question on the heap solution: are we supposed to implement the heap bottom to top before solving problems in real interview (in case that's the solution we come up with)? Just thinking it'd be quite hard to do heavy and bug-free implementations under gunpoint.
Clear Explanation... Thanks a lot for taking the time and effort to make these videos. Good Vibes and Blessings from CS Students.
thansk and ye
U are awesome 👌 ...u are helping many students 🤜🤛
sure
This is very good, man! Very good!! Thanks for teaching!!!!
haha thanks
you are great!
keep the good work.
Greetings from Mexico.
Thank you so much for such in depth explaination! The video content is gold! Love and support from India!😀
When using a heap for this particular problem, isn't it faster to build a heap in O(n) and then call heappop k times? Building a heap and calling heappop k times is O(k*log(n)) while your approach is O(n*log(k)), and I believe asymptotically O(k*log(n)) < O(n*log(k)) right? Awesome video and thanks!
I knew the answer to that question 8 months ago - right now I cannot confidently answer. I have to refresh myself on the complexities of heapsort.
But building the whole heap will take O(n*log(n)) time and then you would have to pop it k times resulting in O(n*log(n)) + O(k*log(n))
@@navdeepredhu4081 Building a heap is actually O(n)
@@brianko4285 You are correct. I always thought it was n*logn for some reason.
Can you please make another video for the same question using "median of median" approach which has linear time for worst case as well.
I officially love you and I love this channel. You save me!!!!
great
The Greatest of All Time
ye
Always love your enthusiastic when explaining, down to the smallest detail. Keep up the good work. I wish i've chosen CS major
thanks & u can always do whatever. life is long in years.
studying for my algos final rn thank u so much
Ben you are a genius. Thank you so much you made this problem so easy!!!. Appreciate you for your efforts and time :D
Love your channel!!
I seem smart but I'm not. And nice - sure - and thanks!
17:32 is the aha moment of this video, give me a lot of understanding, there is no way to give him 1000 likes
nice
Awesome Explanation 🙏🏻 Thanks a lot
sure
What if we use a max heap for kth largest element.
1. Creation of max heap for n elements will take O(n) time.
2. Perform extract_max k-1 times will take O(k log(n)) time.
So total time complexity = O(n)+O(k logn) = O(n).
Am I correct with this one?
not sure? I'm rapid fire responding to comments rn, I'll cover this question in this site coming out soon: twitter.com/thebigoguide
That would be O(n + k logn). You can't just ignore k, which could be as larges as n.
Keep it up!!
I read all your reply to the public comments that are brilliant& interesting.
And I wait for your reply...!!
lol most are basic
This channel is fuuuuuckin amazing man. Sorry for cursing but I had to.
thanks and ur good
Could you please make a video on - finding kth smallest element in a row wise and column wise sorted array? How to extend the heaps solution to that question ? (I saw your - Search A 2D Sorted Matrix video and it was awesome.. I wanted to know how heaps can be used in that scenario)
Thanks :)
I can't due to time constraints sadly
Thanks !! Can you do topological sort (leetcode course schedule problem)
sure and probably not
Great video!
So much effort that you've put into it!
ye, change da world, my final message
Great video! I was curious to know what the case would be if the array had non-unique integers also? In that case would the QuickSort type algo still work ?
Nice one.
Yeah Quicksort of course would work, I'd have to think on this, it is 1 am rn & just got back from working a 12 hr day, brain is cooked
@@BackToBackSWE could you please do a video on this using binary search since the question i encoutered was doing this in constant space and the array cant be modified.
Also, I am always confused in binary search and in some other questions, why do we take left
yes it works. try it out on leetcode. Testcases include non-unique lists as well.
Thanks man
If I ever have to pay for coding interview preparation platform, it'd be back to back swe
This partitioning is linear time only when we can ensure the pivot is proper right? but when we measure an algorithm's time complexity, do we not go by the worst case? And when we choose the pivot to be the worst(largest element), we would lose the entire left partition and thus losing the actual answer too in some cases right? Please clarify if am I missing something
next level vid bro
yes
your explanation skills on point how do you grown like that
not sure
Great video and any plan for box stacking DP ?
thanks and no
you are suberb, I always recommend your video to those who ask for help...
thx
For sure the algorithm is not consuming any extra declared space, but yet taking up O(logn) space in the function stack on an average case :-)
This was the first question interviewer asked me 🥳
nice
Overpowered John!Great work;)
lol thx
@@BackToBackSWE he he @johnlegend aka all of me! Gr8 work byddy
very nice explanation of each and every point....
I am not certain why you are using a min-heap If you are interested in the largest item. A max-heap will have the largest item at the top which gives you easy access. if you are interested in the smallest then a min-heap will have the smallest at the top. But here we are given k'th largest or k'th smallest which can be anywhere within the heap so using a min or max heap will not matter much
Your videos are awesome dude, keep it up.
thx and ok
this was an awesome tutorial man ! thanks !
thanks and sure
Man! You the man!
thx
men you are genius. well explained
ye
For partitioning, why input size cut in half every stage? Isn't Input size still adjusted to n-1 based on the pivot??
The pivot just defines the value we partition against. We split in half (in a best case) since that is most optimal and if a good pivot is choosen then that will happen.
Back To Back SWE thx for quick reply. I was just making an assumption that the first pivot is the highest index and you keep searching towards to left partition..
this is a gem, thanks for share it
sure
No can't watch this after I'm drunk...I need to come back all fresh in the morning.
Lol🤣
haha
I code better after drinking, it keeps me focus..
Why there is no code in the description??? You said 5 times look that code, but where is it??
The repository is deprecated - we only maintain backtobackswe.com now.