Hello and welcome to a new lesson today we're going to solve the problem that we want to find the case largest element in an array. For example, here we have this first example 321564. Imagine we want to find the second largest element in this giving array. How do we do that? Of course we need to somehow sorted it. So we can sort this giving a re descending lee. So it becomes 654321. And then the second largest element is five year. It is a very simple setup but in an interview there is a number of things to consider and to clarify with your interviewer. So first as we see this giving away is can be sorted or unsorted and in this question we are given an unsorted array also um with the like array of integer or integral problems. We can consider if there's any negative numbers in this question, um We can consider only the positive ones but it may not affect our solution. Thirdly we need to consider if there could be duplicate duplicate numbers in this story for this question. Yes. We can have duplicate members. For example, here Let me have my second example which is as you see 32312. There's a number of duplicate numbers like 32 and five. So in this case you need to clarify with your inter river what should we do because for example we want to return the first largest number but do we count the duplicate numbers or we treat all the duplicate numbers as the same in this question. We will count each duplicate numbers. For example for this example to If we sort descendant li we get 655433221. How to get the first largest number. We just can't buy the position. So for this example the answer is gonna be for we will count the five twice or like count the numbers um whatever they appear in the array we don't consider like the duplicate. Okay so that's the setup And natively one can come up with a brutal force solution. Let me just drop some nose down on the top. So our first solution is gonna be a brutal force in an interview. You can communicate this brutal fourth way with your interviewer but do not implement that. You need a more optimal solution to do good in the interview. So for brutal force we can simply sort the whole array just like what we did with the examples then we can find the corresponding index and return the answer was the time complexity for this. The time will be your complexity of the sorting algorithm which is in C plus plus, log log in. And also like same with other languages. It's gonna be a log. So can we do better, Logan seems already good but we can actually do better because we are only interested in the case largest element which means we don't have to keep track of or like um for the numbers that are for sure smaller not in the case largest elements. We can ignore that. So first we can come up with a solution, you're seeing a hit or in C plus plus is actually a priority itude. So what's the idea behind this? We can have a minimum hip where we keep the size of the hip as side. Okay, so we only track the K. Element and we want the minimum K elements or like the maximum the largest K element. We thought we put this largest K element in this hip. But this hip is a minimum hip. So what it means is that the top element is the smallest number of this K largest elements. So the top of the minimum hip, it's gonna be our solution which is the case largest. So take a moment to think about this and let's implement our function. Of course we gonna have the input as the vector and we need to take a number and let's implement the minimum Q. The minimum hit the simplest. Plus we are going to use the priority queue and have a greater than because the default is a max hip and we will go over all the numbers if the hip is not filled, we will put elements simply into the hip. Otherwise if the hip is full, we will only update or like put the current element into this hip is this current element is greater than the element in the hip. When we do such comparison we use the minimum hip top element. So this top represents the smallest element in this hip. If our N. Is greater than this element, we can put into that to mix up our largest element hit of course to replace an element, we need to pop the smallest element and then we push that into the Finally this is a very simple solution. Finally we're gonna return the top of the heap which as we discussed, will be the case element case largest element. So what is the time complexity of this one? Well, you need to look into your function. We do a n. four look. So it's gonna be has a multiplier to our term complexity. And then in each follow up we cannot do like a push or a pop and push function for this push or pop function in the hip. It's gonna be in the time complexity of all. Block the size of the hip. And because we maintain our size of the hip sk it's gonna be low Okay for this pop and push function. So over all. We our time complexity for this solution it's gonna be N times log K. This is the time. And then let's find out the space. It is far straightforward. We use only a hip and the side is K. So the space complexity is just O. K. So let's try out our solution and do several test cases. Let let me just call this function and our men and see the result is right. Let's compel and let's run it. The Girl five For I, the second largest is five as we expected. And then for the second example we got four. We're just also correct. So this is our first optimum. Um well optimum solution. And let's uh there's also another way right now we are looking at time complexity and low okay. But actually we could do better. We could do all of end for the average time complexity and how to do that. We are going to solve it with quick selection which is kind of similar to quick sort. The idea behind the creek select is that let me first find some where propriety it. So the creek slag is gonna partially sort we are already so we are only interested in we will have a pivot position and we are only interested that the elements before the pivot is smaller than pivot and the element after the pivot is larger so that we know the pivot element is in its correct solution. A position but we don't care the orders of the other elements. How does this quick select connected to our solution? We will find we will compare if the pivot number is in a position that give us the case largest number. So how to do this. Let's look at an the first example here and let's go over into my comments here for our first, agree we have this 321564. Imagine we want the case largest, for example we want the second largest one. And um well if we sorted, it's ascending li what should be the index for the second largest? It's gonna or like let's look at um this sorted, So if we found the second, if we want the second largest, which is five, if we saw that assembly or why assembly? Because you really um we do quick sort ascending li um You could do descending lee too, but like you're really we do ascending lee. So um like if you remember the quick sword structure, you can easily reduce this two other questions. So we like you really to ascending Lee and and like change other things around this. Looking at this array for the second largest, we gonna find the index for if we sorted ascending li I hope you see this. So let's let's put it in the comment here. Actually, If we sort ascending Li We got 123456. If we want the second element, Second largest is five. So we want to find what's the position of the second largest, it's gonna be The index is from zero. Right? So we got 01 234. So the second largest element is actually at position four. How do we represent this mathematically this index is actually The size of your three -K. So the size of your over here is six and K. is two. So 6 -2 give you four which is the petition we are looking for. So we are just going to Do the quick selection and one our pivot is at the position we are looking for, we can return the pivot positions element. For example, here we got this unsorted input, we want to find the second largest, so we find the index for sorted ascending li for the pivot point will usually pick it randomly. So for example here we pick three as the period point and then we are going to put three in its correct position. So in this 32 and one are smaller than three. So at the end of the position we're going to put three here after two and one but before the other element, What's the position of the 3? This pivot number is at position 012 which is not the position for. We are looking for the position for is actually the right of our pivot number. So we're going to do the quick select again on the right um for this quick select is actually um a corporate Ryker version into that. So we will see we will call this quick select like um in a Ryker shin format. So right now we're only look at 564 the right of way. And we randomly pick a pivot so they would pick five and then we want to pick put five in the correct position which will be in the middle of four and six like this And let's track the position of five so it's 01234. Is this a position for which is what we're looking for? So this is the answer, five is our answer. So let's implement this quick select. So first we gonna have the same like signature as before we input the numbers as the worry and we have the case after that we will get the site of this array and um this random like seed thing is for later on what we do position and randomly find a pivot and then we're gonna call quick select so this quick select will return our answer and what's the input. Of course we need the ovary and then this is the left index and this is the right index Which is -1. And we also need the position that we are looking for. As we said it is a minus K. Because as we mentioned previously we need to like recursive li um recursive lee called quick select. So when they just happened right here to indicate the rent. So the next step will be implement this quick select let's get our signature here. It's the same as we discussed. For quick select we have to consider some educates first. Okay There could be just only one element which means left is equal to right? So what should we return as the answer because there's only one element. We will just return the this element because we don't have other tourists right? For quick select first we need to pick a pivot index and then we will do partition. Bye partition will mean that we get this pivot point in the correct position. So first let's find our pivot indexed for this solution. We're gonna randomly choose accurate. So um we are using this rent function in C plus plus. I know there's like more advanced random like random machines in C plus plus in modern C plus plus but for the sake of interview we can just use this random as last line of code right down so our private index first it's gonna be in the range of left and right and how to like randomly pick number in a rank. See the comment here with the rent multi color range and then Plus men if you're going to understand this you can just remember this. It's very useful when you are doing a random number from a range. So next we will go to do our partition now we can just um have another function for this partition for petition. Of course we need a range and we need this pivot point position we will implement this petition um later. But first that has our logic written down for comparing our target position with the pivot position. Yes it happens to be. The pivot is at our dessert position. We will return this pivot number. This is our solution. Otherwise if our target position is actually smaller than the pivot we will search on the left side. So the left branch left pointer is unchanged. That we Move the right pointer to just one position before the pivot index because we already know that the pivot doesn't work. So we exclude that. Similarly. We if the target is greater than the pivot we will search on the right breakfast. This part is done. Let's go ahead and implement our partition function. We have the function signature here. So how do we do partition? It's important to make sure that our pivot member is somewhere safe that we don't mess around the pivot number so that we will lose track of the pivot index. So first let's record the value of the pivot and move it to the end and c plus plus when you want to swap to Values or like two elements in in vector you can use this swap function from the library, you were just passing Um the this two elements and this is the only syntax you can do that. So right now the pivot is moved to the end of our a very or like our window for petition. That is safe for now. And we also want another pointer that points to the left of our ranch. So what is the purpose of this for this position is always gonna be assigned a number that is smaller than the pivot. This is a reserved slot for a smaller number. And we are going to move the smaller numbers. The number is smaller than the pivot to the left or like assign it to the current position. So we go through our gray, we live out the right because right is pivot right now. We don't need to move that for now. We don't want to touch that out though. So we compare each number with a pivot. If the number is smaller than the pivot we will put that into the current reserved slot and we do a swap. So the original number will be put into the ice location. And we increase our current pointer because like the current reserve slot is taken. So we want to move one after by the end of this iteration, all elements smaller than the pivot are at are all at the left of current because we do this current class plus after we swept. So right now the current pointer should point to a whatever the current pointer should point to a larger number than the pivot. And the the last step is we're gonna move the pivot to the place to the right place. As we said recovering friend now points to somewhere that is larger than the pivot. So we can just swap the current number with the pivot number which is currently at the right position like um the end of the rent after this. The current will be um at the end which the current number is larger than the pivot. So it's in a good position and the pivot is at a position that all the elements before the pivot is smaller than the pivot. So we say that the pivot is at its correct position if the whole array is sorted but we don't actually sort like all the elements which will save us some time. As you will see later when we analyze the time complexity. So this is for the partition. Well I think we're pretty much finished this little complexities. So going back to our main function lattes called Dysfunction For our two samples. We're expecting to get 25 and 24. Let's compile and let's run disk. Yeah. So as you see the answers are correct. Let's analyze the random complexity so forth. This quick select notice that each time well we do the partition um there can maximum lee be um if we say the site is in there could be maximum and pivot point and it's time we are not doing repetitive work so we are shrinking our range for this petition. Uh and those ranges are like um not not duplicated. So the average time for this. Quick select it's gonna be all of n because this quick select the important part for this great select is the partition function and we can just look at the partition function to see the complexity of this partition function if time were just going over the whole array. So the partition functions complexity is o of N. However, in the worst case uh like our time um we're not shrinking the range of partition effectively, like every time we just shrink The rent for the partition by one, which means we will have an quick Celac function um card and then for each quick select inside we are doing partition is also O of N. So like the worst case, worst case scenario is gonna be all of in this into the square. So like average case you're shrinking the rent for partition effectively although each partition takes all of end time you are not doing in terms of partition, you are maybe doing like one or like two times so you could see the average is just um or of multiple multiples of n. But as we just said in the worst case scenario we were going to do in terms of this partition and each takes all and time. So the worst is into the square, I hope I'm clear on this. It's not um figure out a way to leave a comment for me and I think um we could um explain this more if this doesn't sound very clear to everyone by like drawing a graph or something. Yes, so this is for the runtime complexity and we also need to consider the space complexity in an interview. So for this race it's gonna be all of what, because we don't have any additional structures to store anything. So this is simple and someone asked me for this question if you need to um have this quick select solution um as somehow like optimum solution, um like can I have the priority queue solution and still pass the interview? Well, I think you um it really depends, but I would say most of the time if like you are not um facing a really hard or bar braising interview, then the pirate IQ Q solution should be good if you got it correctly and um you got all the stats like clarification and you're thinking out loud, everything looks good. Then the priority kill solution is good to go. But it could be also a plus if you discuss the quick selection method with the interviewer and that's briefly give the idea like how to implement this because you may not have the time to implement this quick selection so make sure you've got the idea and I think you are good to go so that that's the end of this course, I hope you enjoy it. And and the feedback is welcome. Thank you