Find the k'th Largest or Smallest Element of an Array: From Sorting To Heaps To Partitioning

[@anthonyesquire9830]

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!

[@BackToBackSWE]

"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 :)

[@damodarmahawar9748]

I6

[@Sarah-re7cg]

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

[@sourabhk2373]

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.

[@BackToBackSWE]

thanks - this guy

[@CodeSuccessChronicle]

@@BackToBackSWE haha

[@addiegupta]

"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.

[@BackToBackSWE]

yeah

[@sarojinigarapati95]

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

[@BackToBackSWE]

thanks

[@vedantiyangar151]

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.

[@BackToBackSWE]

Haha, nice to hear, I mean, as humans we are all siblings. Anyway, glad they are helping you. - Ben

[@gyrogojo]

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.

[@BackToBackSWE]

sure

[@jiazhengguo5493]

the best channel for preparing coding interview

[@BackToBackSWE]

I know. Give me 2 more years. KZbin is 😴😴😴 on me.

[@colorfulcodes]

Facts.

[@BackToBackSWE]

@@colorfulcodes hahaha

[@amishagupta990]

Your understanding of the fundamental concepts is phenomenal and rare to find.

[@BackToBackSWE]

thanks

[@kumarchandan9685]

Among other KZbinrs, 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!

[@abhishek-n-chaudhary]

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!

[@BackToBackSWE]

Yeah haha, this is fire. Thanks haha

[@roman_mf]

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. ;-)

[@advertronicssystems8377]

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

[@chuckchen2851]

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!

[@SocajowaRS]

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]

thanks haha, I don't remember what I say in like all my videos

[@SocajowaRS]

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

[@BackToBackSWE]

@@SocajowaRS nice

[@PoulJulle-wb9iu]

cuz u noob

[@johnvanschultz2297]

This is the best explanation of quick select I have found online. Thank you for this video.

[@mr.mystiks9968]

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.

[@BackToBackSWE]

yuh

[@helloiam2mas]

Hey man, you have the best algo + ds explanations and walkthroughs on the entire internet. Bar none. Was a wahoo but go terps lol.

[@BackToBackSWE]

thanks! yeah uva is perty

[@ricardoorellana1168]

Ben, it's amazing the amount of knowledge you have on CS fundamentals, I am learning a lot, thank you!

[@BackToBackSWE]

haha, thanks

[@francocamborda5076]

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.

[@BackToBackSWE]

thanks for the detailed analysis haha

[@Pooja-xu4lp]

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.

[@BackToBackSWE]

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.

[@utsavprabhakar2205]

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

[@BackToBackSWE]

sure and you can just google stuff, no specific resource

[@mriKsuN]

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

[@shyammuppidi2092]

@@mriKsuN i just saw some line explaining the code not the actual code.

[@uman9235]

@@shyammuppidi2092 github.com/bephrem1/backtobackswe/blob/master/Sorting%2C%20Searching%2C%20%26%20Heaps/KthLargestElement/KthLargestElement.java

[@rohanangajala548]

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?

[@shubhampareek2378]

This is my 2nd or 3rd comment ever on KZbin. But all I wanna say is: "I wish there was a provision of giving more than one like". Thanks a lot.

[@BackToBackSWE]

Hahahahhahaha, this vid was fire, not sure if I can drop more like it. Let's see haha

[@jameshuddle4712]

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)

[@brainstorming1369]

You know that feeling when it just clicks. You and NeetCode always get me there. Thanks for all your hard work

[@TheSridharraj]

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.

[@adityasaxena3903]

Dude, your explanation! Absolute magic. Better than the paid courses!

[@BackToBackSWE]

thanks

[@navyakalra6774]

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!

[@BackToBackSWE]

thanks and sure and thx

[@deepraj279]

I am never going to forget quicksort because you taught me how to actually use it. Beautiful explanation

[@BackToBackSWE]

ye

[@殷源源]

Thanks from China.I liked several videos of you since I met your channel yesterday. Really appreciate the details and the way you present.

[@growingwithtech]

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.

[@BackToBackSWE]

What was the recurrence I solved?

[@growingwithtech]

You solved for the best case i.e., T(n)=T(n/2)+(n-1)

[@BackToBackSWE]

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

[@growingwithtech]

Exactly!! Thanks for the clarification

[@SinghFlex]

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.

[@BackToBackSWE]

Any number can be the pivot? Why the last?

[@SinghFlex]

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

[@factsheet4930]

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.

[@kaustubhtrivedi5403]

Keep it up man, I really think this channel will be well known very soon.

[@BackToBackSWE]

working on it

[@OP-yw3ws]

Its amazing how easy your explanations are

[@kiwixuerong7383]

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!

[@BackToBackSWE]

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

[@redherring27]

Congratulations your final dialogue of happiness in everyone's life earned you a subscribe. Aight imma make my chemistry major roommate subscribe too.

[@BackToBackSWE]

wut

[@ankuragarwal4014]

Keep Making Videos please....a humble request from your regular student..you are truly a great teacher

[@BackToBackSWE]

ok, say no more, I got u

[@dzeng16251]

great stuff man, I love how well you teach and explain this stuff

[@tapasu7514]

No one can ever match your style of explanation. Super !

[@BackToBackSWE]

thanks

[@stk1526]

Amazing explanation!This has really helped me understand how partitioning works , and the details that i have missed .

[@BackToBackSWE]

great to hear

[@AJ3000_]

This man is better than 90% of my cs department at explaining these concepts

[@pushpendrasingh1819]

BRO... you also need to share your upper push body workout. You are in great shape

[@BackToBackSWE]

hahahahaha

[@DarshanSenTheComposer]

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]

Thanks. Yeah, former bounds to linear time, latter bounds to n*log(n)

[@rupadosapati7628]

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

[@BackToBackSWE]

to compute the range of numbers?

[@tedytedy8918]

Mannn you are the kinggg❤️❤️ A day before the exam on data structures i saw this video.. N this question was on the exam 🙂🙂

[@BackToBackSWE]

hahaha nice

[@ashutoshtiwari4398]

I like the way you walked through your thought process.

[@PankajThakur-tc1dw]

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

[@Endlessvoidsutidos]

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

[@BackToBackSWE]

lol

[@mubarakoyeyinka8520]

Thank you for all videos ! Very understanble !

[@BackToBackSWE]

Glad you like them!

[@reneeliu6676]

No can't watch this after I'm drunk...I need to come back all fresh in the morning.

[@marlegagaming1274]

Lol🤣

[@BackToBackSWE]

haha

[@mohneeshgarg8706]

I code better after drinking, it keeps me focus..

[@brianko4285]

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!

[@BackToBackSWE]

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.

[@navdeepredhu4081]

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

[@brianko4285]

@@navdeepredhu4081 Building a heap is actually O(n)

[@navdeepredhu4081]

@@brianko4285 You are correct. I always thought it was n*logn for some reason.

[@uditswaroopa5809]

After watching so many videos this video helped thanks a lot brother

[@BackToBackSWE]

sure

[@shiveshbharti5442]

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

[@pavan7959]

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?

[@BackToBackSWE]

not sure? I'm rapid fire responding to comments rn, I'll cover this question in this site coming out soon: twitter.com/thebigoguide

[@tsunghan_yu]

That would be O(n + k logn). You can't just ignore k, which could be as larges as n.

[@laksh5228]

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

[@qwarlockz8017]

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

[@chuckchen2851]

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.

[@vansh2k6]

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

[@BackToBackSWE]

cool

[@nirajchowdhary7372]

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

[@BackToBackSWE]

I seem smart but I'm not. And nice - sure - and thanks!

[@KeshariPiyush24]

Can you please make another video for the same question using "median of median" approach which has linear time for worst case as well.

[@BullishBuddy]

This is very good, man! Very good!! Thanks for teaching!!!!

[@BackToBackSWE]

haha thanks

[@adityasoni1207]

Huge respect to this guy! Thanks a lot, these videos are amazing!

[@badal1985]

you are too good Ben! your videos are very helpful. please keep making them.

[@BackToBackSWE]

haha ok, I will, as long as I'm a live

[@akankshasharma148]

Your explanations are so easy to understand.Thanks a lot🙌🙌

[@Ambs_2024]

Very good teaching style. Thanks for the tutorial!

[@BackToBackSWE]

sure

[@vanducnguyen346]

Always love your enthusiastic when explaining, down to the smallest detail. Keep up the good work. I wish i've chosen CS major

[@BackToBackSWE]

thanks & u can always do whatever. life is long in years.

[@EspoirMurhabazi]

17:32 is the aha moment of this video, give me a lot of understanding, there is no way to give him 1000 likes

[@BackToBackSWE]

nice

[@zdaghost]

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]

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

[@utsavprabhakar2205]

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

[@utsavprabhakar2205]

yes it works. try it out on leetcode. Testcases include non-unique lists as well.

[@zdaghost]

Thanks man

[@gssnhimabindu8831]

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

[@BackToBackSWE]

I can't due to time constraints sadly

[@bharathik6479]

Clear Explanation... Thanks a lot for taking the time and effort to make these videos. Good Vibes and Blessings from CS Students.

[@BackToBackSWE]

thansk and ye

[@arunprakash1101]

I am puzzled! Just by using Priority Blocking Queue, We can solve it in 0(n) Complexity, right? Why to rely on the Re-implementation of the QuickSort algorithm again? Please correct me if I am wrong ! public int findKthLargest(int[] nums, int k) { // TODO Auto-generated method stub PriorityBlockingQueue pq = new PriorityBlockingQueue(); for (int n : nums) { pq.add(n); if (pq.size() > k) { pq.remove(); } } return pq.remove(); }

[@BackToBackSWE]

That structure has operations underneath that likely add complexity? Not sure never used it

[@arunprakash1101]

@@BackToBackSWE PriorityBlockingQueue solves the problem in O(n)! But using Quick select is even more efficient, I am able to increase the performance of my code more than 80 percent!! Cool! Kudos to your efforts !!

[@jyotisingh8183]

Hello sir, can you please tell me in heap approach for kth largest or Kth smallest element we used minheap or maxheap respectively, but on what bases we're removing smallest element from minheap and largest element from maxheap. I want to know the implementation like how we're comparing elements inside both heap so that we could remove smallest or largest element. Thank you.

[@BackToBackSWE]

Are you asking about how the heap works internally? Or at what capacity ejections happen?

[@jyotisingh8183]

@@BackToBackSWE Sir I mean that suppose for Kth largest Element we use Priority Queue and create a variable let's say large. Now I'll do large.add(arr); Next as you said to check if large.size ()>k then remove(); so how my large variable know which element is smallest? Same in the case of Kth smallest element how my variable know which element is largest so that we remove it.

[@BackToBackSWE]

@@jyotisingh8183 Ah, so the point is we remove the largest items so that only the k smallest are left over. If I have [1, 2, 3] and I want the 2 smallest, I will not want 3 to be in there. So when capacity hits 3, the largest item in the heap (3) leaves.

[@jyotisingh8183]

@@BackToBackSWE yeah sir I got the logic but how my variable know that I have 3 which is largest then remove it? There should be some condition which checks which is largest or smallest element is there in heap to remove it if heap.size()>k.

[@BackToBackSWE]

@@jyotisingh8183 It is a max heap so it is designed to keep the max element at the top to be removed.

[@evgeniifeygin1030]

thanks a lot. one question only. You say "the code is in the description". I have searched in the Description - there is neither code or link to it. So where to find the code ?

[@thanga2317]

Great video and any plan for box stacking DP ?

[@BackToBackSWE]

thanks and no

[@Mrwiseguy101690]

You have the best explanations I have ever seen. Definitely earned a sub.

[@BackToBackSWE]

welcome, you are loved

[@graphicsRat]

Why not maintain an array of the two largest elements and store the (index) to the smallest of the maximum elements, traverse the input array and replace the second largest element. That's just one traversal of the array and no sub-problems. This is very similar to your initial solution, or am I missing something?

[@BackToBackSWE]

I don't remember the first approach I presented in the video and can't fully visualize what you are describing? Maybe make an example?

[@graphicsRat]

@@BackToBackSWE I'm mistaken.The appraoch I had in mind has an insertion problem which you also pointed out.

[@footerrykim]

For partitioning, why input size cut in half every stage? Isn't Input size still adjusted to n-1 based on the pivot??

[@BackToBackSWE]

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.

[@footerrykim]

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

[@shnerdz]

would heapifying the entire array then extracting min/max k times be faster or slower than the heap approach you gave? O(n) + O(klogn)

[@BackToBackSWE]

Not sure to be honest. O(k*lg(n)) vs. O(n*lg(k)) would have very similar tail behaviors since they are basically the same function (just with the n and k swapped). We could solve for the exact average case for that approach and then compare them using the concrete amounts...that would be the best and most sure thing to do. But yeah, I'm not 100% on that.

[@ihmpall]

Thanks !! Can you do topological sort (leetcode course schedule problem)

[@BackToBackSWE]

sure and probably not

[@netopedia8733]

Awesome Explanation 🙏🏻 Thanks a lot

[@BackToBackSWE]

sure

[@frustated_fool]

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

[@harsha20jun]

Question !! How is this a constant space. This recursion we will have method stack, so I think it is O(Log N).

[@BackToBackSWE]

Where did I say constant space? And worst-case space is O(n) if partitions are really skewed and O(log(n)) if partitions are relatively even.

[@harsha20jun]

@@BackToBackSWE What was that at 28:39?

[@BackToBackSWE]

@@harsha20jun Oh, yeah, not including space used by the call stack it is O(1), should've been clear

[@mr.mystiks9968]

Back To Back SWE but when would the interviewer ever be ok with you excluding the call stack? by that logic, recursion is a cheesy way to always getting o(1) space for every recursive algorithm. can i traverse a tree recursively in constant space? Of course not, that makes no sense and if you ignored the stack space, the interviewer would think you don’t know that

[@BackToBackSWE]

@@mr.mystiks9968 yeah, ur right

[@TCErnesto]

as a math lover I really enjoy your explanations, thanks man

[@wanderlustsiddhi]

Thank you so much for such in depth explaination! The video content is gold! Love and support from India!😀

[@markokafor7432]

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

[@dhyeyparekh4994]

very nice explanation of each and every point....

[@ryoyamamoto6488]

This channel is fuuuuuckin amazing man. Sorry for cursing but I had to.

[@BackToBackSWE]

thanks and ur good

[@sinaanyounus5449]

studying for my algos final rn thank u so much

[@umeshmg1658]

Hey can you please suggest me, in which order to watch your videos? I'm watching them in random order

[@BackToBackSWE]

just watch what you are weak on I guess

[@ivanleon6164]

you are great! keep the good work. Greetings from Mexico.

[@andrews2945]

Your explanations and visuals are always on point, thanks again. No flame, just thought it was funny, but did you have a stroke @ 20:57 😆

[@BackToBackSWE]

sure, and my bad

[@lokeshs9449]

Keep it up!! I read all your reply to the public comments that are brilliant& interesting. And I wait for your reply...!!

[@BackToBackSWE]

lol most are basic

[@chanish163]

U are awesome 👌 ...u are helping many students 🤜🤛

[@BackToBackSWE]

sure

[@al.e123iis7]

Using Lists... int[] store = { 3,2,1,5,6,4}; int k = 4; //set ur k List queue = new ArrayList(); for(int i =0; i< store.length ; i ++) { if( queue.size() ==k+1) { // this is our "heap" int min= 10000; for( int num : queue) {// get the smallest number if(num< min) min = num; } int index= queue.indexOf(min); //and well kick it out queue.remove(index); queue.add(store[i]); //dont forget to add the current i number if( i == store.length -1) { //at end loop will terminate without getiing rid of the last one min= 10000; //so repeate same code for( int num : queue) { if(num< min) min = num; } index= queue.indexOf(min); queue.remove(index); } } else { queue.add(store[i]); //add to out list heap } } // fourth largerst thus get the min of the the 4 int largest =2000000; for( int p : queue) {// get the min of the heap our answer if( p < largest) { largest = p; } } System.out.println(largest);

[@BackToBackSWE]

ok

[@branzalleyne472]

Why is this algorithm O(n) when quicksort itself is O(nlogn) ? Doesn't this algoritm essentially just perform quicksort but eliminate half of the list each time?

[@BackToBackSWE]

It is a partial sort. The recurrence is T(n) = T(n/2) + O(n). This class of recurrences bounds to the order of linear time. I think I did math in the video to concretely show the operations?

[@JoseSagrero1]

Thank you for your videos! You're an awesome for making them.

[@BackToBackSWE]

thx

[@jacklin708]

Did I miss something? I thought the min heap is used to keep smaller element on the top. So in the video, we should use Max heap for k largest element.

[@NGBigfield]

Great video! So much effort that you've put into it!

[@BackToBackSWE]

ye, change da world, my final message

[@amanduhduh]

After you eliminate the left side of the search space, do you sort the remaining right side?

[@BackToBackSWE]

You call the recursive subroutine on the right side.