hey everyone welcome back to the channel I hope you guys are doing extremely well so this is another video from the Strivers A2Z DSA course just in case you're for the first time here this is world's most in-depth course on DS algo why do I say that you can go across internet you can buy any of the paid courses none of them will be covering DS algo in such depth we will be covering 456 modules and we will be solving 400 plus problems in this DS algo course so when you end this course you can actually clear any of the DS algo rounds in any of the interviews in any part of the world so till now we have covered till step 3.1 fourth problem and in this video we will be covering these five problems just in case you want to directly jump to any of the particular problem the time Stamps will be there you can directly jump over but let's get started with the first problem which is left rotate an array by one place so if you have seen our previous video you know that we always start from brute then we go to better and then we go to Optimal given that the brute and better exists for that problem and this is the way you should always tell in an interview why because in an interview your thought process should be visible to the interviewer because it's you who will be driving the interview so make sure you follow this particular stepbystep optimization of approaches because it does leave a very positive impact on the interview now coming back to the problem left rotate the array by one place what does it mean so given an array you have to left rotate it yes you have to left rotate it by one place so if I have this array and you have to left rotate it by one place so one place so one element will go and rotate it so basically this one will go to the end because you rotate it and everyone will move a bit because you're rotating it so it'll be like 2 3 4 5 so this is what rotation means if I'm talking about left rotation so I have rotated the array and this will be my final array now for this problem this is a very easy problem so you can directly jump to the optimal solution instead of going like to the proo where you take another array and store the answer in another array it's not required for this problem you have to solve the problem in the given array itself like you cannot use any new array make sure you solve the problem in the given array itself now since it has been clearly stated that you have to just rotate it by one place hence the problem is very simple after that we will be increasing the difficulty of the problem but as of now let's understand how do you left rotate by one place now I know one thing if I have to talk about left rotation let's visualize what happened in the final array in the final array this is the only guy that went to the last the first guy is the only guy that went to the last and apart from that what happened the two moved here the three moved here the four moved here the five moved here it's like they moved one place they moved one place ahead so moving them one place ahead should not be a big deal but we need to store this one so assume I say temporary equal to array of zero and over here temporary will be stored as one because array of Z is one now what I say is okay I'm standing here this two ideally since it is left rotated by one should go at the zeroth index so I'll place it here so it's like saying okay if I'm at I index I'll place it at one index before and then again I'll move the a index and I'll see place it at one index before which is again the IUS one and then again I'll move the I index and I'll say place it at one index before so this will be placed here then I'll move here and I'll say place this five at one index before so this will be placed once I've done this the iteration will be over once the iteration is over the last place is having five as of now we need to take this one and place it at the last place and the one is stored in temporary variable so you take this temporary and put it into the last index so this will take one hence the array will get modified to this after left rotating it by one place now let's talk about the implementation how how will you implement it can I say this is nothing but the first index and this is nothing but the N minus one index so thereby what you can do is you can say for I like At first what you can do is you can always do temporary of array of zero and then you can start from one and you can go on till I N minus one so you can run a loop till n minus one and then you can say this ayat guy will go to i - one so array of IUS one will store array of I once this Loop is completed that means this will be completed and at the end of the day at this position which is nothing but array of n minus one whatever we stored in temporary we take it and we will place it over here as simple as that if I have to discuss the time complexity what will the time complexity yes a simple beo of n pass because we are running this Loop for n times thereby the time complexity is p of n are we using any extra space no thereby the space complexity is p of one why because we are doing everything in the given array itself so we can see that we are not using any extra space but yes we are modifying the array so the space used to solve the problem is B of n because we're using an array to solve the problem yeah that array is already there but we using it so if someone says what is the space used in your algorithm then it becomes B offen because you definitely are using this array but it is already created but you're using it in your algorithm but if someone says what is the space that you like what is the extra space that you're using and the extra space is be of one but in for the algorithm we definitely are using this so understand the shuttle difference if someone says in the algorithm you should always take the space that you are being used like that's being used and if someone says what's the extra space then you can say B go fun so there's a shuttle difference whenever you go to an interview always clarified tell them that sir the extra space is so whenever you go to an interview always clarify this tell them sir or ma'am the extra space that I'm using is we fun but in order to solve this problem I'm using this array so if you have to take space into consideration for the algorithm particularly I will say I'm using this are so thereby a b go of n space is being used yes it's already given to me but I'm using it in order to solve it so this way you tell to the interview so that every concept of yours is Crystal clearly presented to the interview and he is impressed this is how you should drive the interviews got it so if you want to solve this problem the problem link will be in the description so I've written the exact same code and I'm submitting this problem and it is running absolutely fine so you have solved this problem now if this problem comes up in an interview the followup question very likely will be the next one which is left rotating an array by D places till now you have solved a problem where you did left rotate the array by one place now I am telling you okay one is easy what if I give you two what if I give you three what if I give you four can you left rotate an array by certain number of places so that certain number is d d can be anything in a problem so you have to design an algorithm so that the algorithm works for any given number of places that is what the followup question will be so let's try to solve this followup problem so let's understand the problem statement it states you to left rotate the array but this time by D places assume for this given example array we have D equal to 2 so it stating that left rotated by two places so this two elements should be left rotated and these elements should be moved by two places this is what you mean by left rotation so if I do that the resultant array will be 3 4 5 6 7 and then 1 and 2 so this one and two kind of moves here and then moves here and these will move two places ahead so this is what the resultant array will be after you have left rotated the array by D places D over here is two D could have been three yes D could have been three as well in case of three what would have been the answer yes obviously in that case 1 2 3 would have been left rotated and they would have been moving by three places ahead so in that case the answer would have been 4 5 6 7 and then 1 2 3 so that's the answer for D equal to 3 now what if yes what if like let's count the size of the array it's like one sorry my bad 1 2 3 4 5 6 7 s is the size of the AR imagine I asked you can you rotate this yes you rotate this by seven places so if you actually rotate this by seven places it will again come back to the same place it will again come back to the same place so rotating it by seven places will bring it back to the same place so if I ask you can I rotate it by eight places if you do a rotation by eight places can I break eight down to seven rotations plus one rotation can I I can so can I see that Hey listen on seven rotation it comes back to the original array and then you just have to do one rotation on it Mak sense so if it is nine rotation can I break it down to 7 + 2 and say okay on seven rotation it will be the original array again and then you just have to do a mega two rotation on the array does make sense if I tell you D equal to 15 can I write 15 as 7 + 7 + 1 stating that on two seven rotations on two seven rotations the array will be back to its original and then you just have to do one rotation and that will sum up to 15 rotations so can I see multiple of seven rotations can be done and it will always bring you back to the original array I repeat multiple of seven rotations will always bring you to the original array the remaining is what you need to do so can I see whatever AR is given to you sorry whatever D is given to you doesn't matter the number of rotations you have to do will always be D modular whatever is the size of the AR can I say this if it's given like 20 doesn't matter I'll just have to do six rotations because 20 module of 7 will be six which means you have to do seven two times and the remaining six so you actually have to just do six rotations and if you have any number of rotations which is lesser than the size of the array it's very simple if I say six it means this will go here it's like 1 2 3 4 5 6 and this will go here that is the meaning of six rotations so anything lesser than seven is very easy to solve that's why we will always do a modular of n because end rotations like on multiple of end rotation means coming back to the original which we do not care we care about doing the next set of steps got it so that's the first thing we have to be careful about whatever D is given to you just do a module with n and that will be solving your problem and that will be solving your problem if D is very very l so if in an interview this question comes up the first approach that you'll be telling will be the Brute Force approach now what will be the Brute Force approach over here let's go back to the previous problem in the previous problem D was one element you were being asked to rotate the array by one place so you initially took a temporary and you stored one element this one element was stored and then you yes then you did this and then you replace that one element to the last we'll do the exact same thing D was one over here so you stored one element if D is two you will be storing two elements into this temporary and then you will rotate and then you'll take the Two element and you'll put it on the back that's what we'll do let me explain so what I'll say is okay D is three so I'll take a temporary array or a temporary list whatever you can and I'll say okay let's take the first three elements very simple done so I've taken the first three I've taken the first three and I've put that into the temporary array similar to Out we uh similar to what we did in the first problem now what was the next step shifting so let's do the next job of Shifting now when I say shifting how will you shift let's write down the indexes and let's try to observe how do we shift so if I write down the indexes it's like 0 1 2 3 4 5 six and if D is three we start shifting from third index we start shifting from the third index which is the dth index so we we start from here and where do we put three let's analyze three is put to the zeroth index obviously four will come here and the fourth index is put to the first Index this one will come here and then the fifth index which is this which is six is put here so fifth index comes to Second do you see where it is coming up if this is your I index if this is your index it's always coming to I minus D place this is where it is coming to the shifting is happening in this way so what I can say is okay for shifting I can probably start from this one sorry this one which is the third index which is nothing but D and I can go until the last i++ and I can say array of because the third index guy will go to the zero IND next guy please observe this guy goes here and this will become four so it goes three places back it goes D places back so I minus D places is where the array of I will go so once you have performed this shifting how will the AR look like let's write once you performed this shifting how will the AR look like it will look like four is here five is here six is here seven is here now you still have three places where 5 6 7 is there and what do you need to put it like what do you need to put there very simple you have to take this temporary and you have to put the temporary one by one here which is like 1 2 3 quite simple so put back temporary is the last step put back temp is your last step so let's put back the temp so I can see how do I put back the temp now we need to analyze where are we putting it let's try to analyze so can I say if we shifting by three places it means if the size of the array is seven three places before it because the last three places will only be occupied if we are shifting the array by three places only the last three places will be occupied so it be like okay 7 - 3 which is basically n minus D which is basically 7 - three which is basically four so we're starting at four can I say we will start putting at the fourth index can I I can so I'll start from I'll start putting it from the fourth like n minus K and I'll go on to the last quite simple and what will we put in the array of five what will we put we'll put first one so we'll put something from the temporary we will put something from the temporary for sure now we need to figure out what's the index the easy e EST way to do this is like without any mathematical calculations or anything the easiest way is say J equal to Z and put J and then do a j++ so what will happen at first J is here because that's the zero index takes up one puts it here then J goes here takes up two puts up here then J goes here takes up three and puts in here so you put J and you increment J you put J you increment J and this will easily fill up the last three places that's one of the ways to do it but if you're going to an interview you have to show all your skills so this is the first thing you'll tell in an interview then you can say maybe we can get rid of this possible J yes let's get rid of this possible J can I deduce something which is mathematically correct I can maybe so something which I know is this element which is at the zeroth index will always go to the N minus D Index can I say this I can now can I say someone who is at the first index will always go to n minus D + 1 which is basically the next index I can now can I say someone who is here will always go to here which is apparently two places ahead which is n minus D + 2 can I say this and this is the second index so n minus D + 2 so can I say if your base index is n minus d n minus D is your base index can I say this temporary will say okay if you're standing here if you're standing at I then you just need sorry n minus D to get your base index can I say this you just need i - n- D because again I'll repeat this is n minus D + 2 and this is n minus D so if you are trying to put some something here then if you just subtract this you'll get two and you get the second guy from here quite simple maths very very simple take a pen and paper and try to do it yourself I'll repeat again the base index here is n minus D then the next index will definitely n minus D + 1 the next will be n minus D + 2 right and we're taking from 0 one2 so this is like zero this is like one and this is like two that's why wherever you are currently at just subtract the base index if you subtract first you'll get zero then you get one then you'll get two which apparently means this so you'll automatically take the temporary this is how you can easily put it back got it so quite simple first I stored everything from the temporary again to store everything from the temporary you just need to loop from 0 to D so it's like looping from I = to 0 I lesser than D and I + plus and in the list you can probably take a vector or a list in uh Java push back in V uh in Java it will be list. add array fine that's it so this is the putting into the temporary this is the step one so this is how you can put everything over there then you can easily shift and then you can easily put back the temporary array this is how you can easily do it so for the for this brute approach I have written the pseudo code so that you can code in C++ or Java but coming to a cleaner code we just take the array as the input then we take the d and then we call the left rotate function which rotates it and then we just kind like print it so let's look at the function so it takes an array it takes the size of the array takes D and the first step we make sure is we just reduce the D to something lesser than n because we know on all the multiples of n it will come back to its origal array and then we store everything into temporary then we shift it and after that we place back temporary into array quite simple so that was the cleaner code and the problem link will be in the description so what will be the time complexity so can I say the time complexity will be in order to do the step one this is taking a beo of D because we are looping through the first D elements next can I say in order to transfer like shift everything that's going to take B go of n minus d because those many elements are what you will be transferring or shifting to the front so n minus the next one putting back temporary so that's like again B go of D because you're putting back D elements so that's like B go of D and if I have to add it up it will become beo of n + D this will be the time complexity and if I ask you what is the very important one what is the extra space used extra the extra space used will be B go of B why because you're using a temporary area to store the extra elements now this is where the interview will tell you okay fine enough but I want to get rid of this extra space can you just do it and be off one extra space that's when you'll say okay maybe I'll try maybe I'll try to optimize this into an optimal solution for this a better might not exist so I'll not discuss it but this is where I'll try but this is where I'll try to optimize this into an optimal one so let's look at the optimal solution so let's talk about the most optimal solution the most optimal solution will be based on observation now this will be the resultant array after you have rotated this array by three places now something to observe this 1 2 3 yes this 1 2 3 is over here okay and this 4567 is over here so what we can do is we will say okay let's let's take the first three elements and try to rotate it sorry try to reverse it so if I reverse it it'll be 3 2 1 I've reversed it and then I'll say let's take the last four elements let's try to reverse it as well so if I reverse it it'll be 7 6 5 4 now what I'll say is okay this is the Reversed array post two reversal one is the first D the next is the n minus D elements after this if you have to get this final array what do you need to do reverse it again so if you reverse it what will happen this four will come first this five will come here this six will come here this seven will come here this one will come here this two will come here and this three will come here done and dusted yes this is super easy so I will say reverse first array to array plus d then I'll say reverse from array plus d to array plus n which is the last one and then I'll say reverse the entire array which is array to AR plus n so if I perform this three reversals if I perform this three reversals I will actually get the resultant AR I don't have to do like I don't have to take a temporary do shiftings and then copy pasting back again just three reversals first for the D elements then from D to n and then the entire and if I do this I should done and this will take me a b go of n sorry B go of D complexity because we are reversing D elements this will take me a b go of n minus D because we reversing n minus D elements this will take me a b go of n because we reversing the entire array so overall the complexity will be this plus this so D and D will strike out and the complexity will be 2 N so the time complexity slightly increased from the previous one but but the space complexity we are not using any extra space very important we're not using any extra space yes we are using the array that you can tell to the interview but we are not using anything extra we're using the given array okay that's why the space complexity over here will be vco of one got it so let's quickly code this up again the problem link will be in the description so there is a reverse function a and C++ so if you just give this it will reverse from array plus 0 like zero index to D minus one to D minus one and then you can say again reverse array plus d to array + one this means from D Index to n minus one at index then I can say again reverse array plus sorry plus Z that's means from zero index to the last index if you do this three steps it will be done and I now I can quickly run this and see if it is running yes and now you submit this it should be submitted so in case your programming language does not have a reverse function you can always write something like this which is a manual function where you take the starting index and the ending index which means you want to reverse from this index to this index and this is quite simple you can go through this it's very very simple and this will also work like if you write a manual function just because in C++ there is an STL that's why I did not write an extra function but in an interview the interview might ask you to write an additional function without using the STL so in that case you can go ahead and write a similar function which will reverse you a particular array from start to end so with this we are done with this problem as well which is left rotate an array by D places now remember there might be a follow-up question to this in an interview which is what if instead of left rotation I'll see you WR rotate the array by D places you have to come up with a solution and this will be an assignment try to think how will you WR rotate an array by D places and once you have written the code you can put that into the comment section also remember in an interview do not jump to the optimal solution directly go from brute to Optimal that will show your thought process and that does leave a very very good impact in the interview head about you okay uh let's now move on to the next problem which is moving zeros to the end so what is the problem State move all zeros to the end of the array so you will be given an array which will be consisting of some integers and it will also be consisting of some zeros now your task is to move all the zeros to the end of the array so first there will be one then there will be two then there will be three then there will be two then there will be four then there'll be five then there will be one so basically what you do is you take 1 2 3 2 4 5 1 so I took all the nonzero numbers and I put them into the front of the array once I've done that what are the remaining elements they are zeros and there are three zeros so you take all the three zeros and you put it to the end of the array right so once you've done this the modified array will look something like this and this is what the problem is asking you to do question is asked to you in an interview you should definitely start with the brute for solution and then maybe come up with a better solution if there is one and then go to the optimal one so what is the Brute Force solution if you look at the problem it states all the non-zero numbers at the front like all the nonzero numbers at the front so my mind kind of says that okay let's pick up all the non-zero numbers and store it somewhere so what I'll do is I'll start iterating in the array so I'll start from the first index and I'll say it's a non zero let's pick it up then I'll go to the next it's zero then I'll go to the next it's a non zero then I go to the next it's a non zero it's a non zero it's a zero it's a zero it's a non zero it's a non zero it's a non zero and the iteration is over once the iteration is over I can say that I have all the nonzero numbers and again you can store them in a list in an array wherever you wish to so I have all the nonzero numbers stored with me once I've done this what is my next job I know one thing for sure I have all the non-zero numbers that will go at the front so let's do it let's take let's assume this is the temporary array let's take everything let's first take one and put it here let's then take two put it here let's then take three put it here let's then take two put it here here let's then take four put it here then take five put it here then take one put it here so I have taken everything from the temporary array and put them into the front of the array once I have done that I know all the nonzero numbers are at the front if I've done that what is the next job all the remaining positions will definitely be zeros so I'll just assign them zeros done and this is how my Brute Force approach will look like first iterate store all the nonzero numbers then put all the nonzero numbers to the front and then fill the remaining places with zero so if I have to code this what I'll do is I'll probably Define a temporary which is an empty list and then I'll start iterating from the zeroth index until the nth index and I will say Hey listen if you are a non zero number which means not equal to zero then can you go and get added to the temporary and you'll add it to the temporary simple this will create your temporary array with all the non-zero numbers so I can say the step one The Brute Force approach is done what is the step two step two is very simple pick up everything from the temporary and put it into the front of the array so you will just move in the temporary array so I equal to Z and then you can go to Temporary do size because that will tell you how many nonzero numbers are there and then you can move and you can say array of I let's put it into the front array of I equal to Temporary of I so this is step two once you have done the step two all the non zero numbers will go to the front now the step three is filling up of zeros at the back so I know if temporary dot size like is the number of nonzero numbers like over here it is like 1 2 3 4 5 6 7 so it took the first seven places so the last index it took was the sixth index so you'll start filling from the seventh index go to the eth and go to the last which is the n minus one index so you start filling from the seventh index which is nothing but number of nonzero elements so you'll just start from the non-zero elements like whatever it is the number of non-zero elements and you'll go till the last and you will see in all of these places I'll just fill up zero and this is how my brute force will look like and if I have to analyze the time complexity can I say this is taking a big of n because I'm running an entire Loop can I say this will be taking imagine there is X imagine there are X nonzero numbers so this will take X and this will be the remaining portions so the remaining portions will be n minus X because if x is the number of nonzero the remaining will be n minus X so can I say the total time complexity to be B go of n plus b go of X plus b go of n minus X so - X Plus X will cancel and that will be B of 2 N will be the time complexity of this particular one and can I say the extra space again very important the extra space that I'm using will be weo of X where X is the number of nonzero numbers and that at Max can be we go off and imagine the entire array to not have a single zero then you'll end up transferring the entire array into the temporary array so thereby the this is the worst case there this is the worst case where there is no zero in an array then you will transfer the entire array into the temporary so that in that case you'll be using V go of n space so this will be the time complexity and space complexity for The Brute Force solution so in case you want to Cote The Brute Force solution and submit it the problem link will be in the description there is a reason why I'm writing the pseudo code so that you can code it in any of the languages but still if you want the Java and the python codes the link will be in the description you can go to the notes and you can check them out so the Brute Force solution is done now it's time to move to the better solution but there is no better solution so we'll be moving to the optimal solution now this is what you have to tell to the interviewer what will be an optimal solution let's analyze the thought process till now what we did was very basic we just picked up the elements and put them into the front but now we'll try to do it on like while iterating how can we do that if somehow I can take this two and put it here and somehow I can take this three and put it here somehow I can take this two and put it here and maybe somehow I can take this four and can of put it here my job should be done so we'll be trying to move the elements we will be trying to move the elements and in order to do that we are already iterating in the are remember this we are already treating in the array so what we will do is we'll try to use a two-pointer approach to move it something similar to what we did uh in this particular problem where we did remove the duplicates from the sorted array something similar now what I will say is okay Hey where's the first zero and I'll say here is my first zero and this will be pointed by J which is the right next index after zero which is this I'll point it over here now what I say is Hey listen I start from here and I check are you a nonzero number he says yes I am a non- zero number okay we have a zero here let's let's swap it so I'll do a swap so the two will go here and the zero will come here the moment you have done a swap you will say okay done now I will move to here and I'll also move the G to here so once I've moved I'll just quickly erase this so that it's clearly like it's clean done this next I'll say hey are you a non zero number he says yes I'm a non zero number I'll say Okay swap to the zero so I'll go across and again swap so three goes here zero comes here and the moment you do that I will move ahead and J will move to the next place and if you've done this let's remove this so that it's again clean next are you a nonzero number he says yes I'm a nonzero number number I'm like okay so so two goes here Zer goes here perfect and now I'll move I here and I'll move j here so J will be always at a zero J will be always at a zero and I will be simply iterating okay next I ask is this a nonzero number he says no so no swapping I moves is this a nonzero number no no slapping I moves is this a non-zero number he says yes I am a nonzero number so I'm saying you're a nonzero number okay you need to go to the zero g so he says okay I'll go so I'll go to here which is four and this will be zero perfect and the J will be moving here and the I will be moving here once I've done this I'll just clean this next five are you a non zero number he says yes and zero comes in here and then I move I here and then I move J here next one are you a non zero number he says yes so one comes here Zer goes here and I crosses the boundary the moment I crosses the boundary you stop and do you notice something all of these positive like all of these nonzero elements are in the front and all the Zer went to the last very simple and it's done and what we did was a single iteration if you carefully observe what it did was we started the iteration like we first figured out the zero and then we started the iteration and we went till the end so it's like a one iteration we did which is much better than what we were doing previously right see in the optimal solution what is my step one if I have to ask you what is my step one it's finding the first zero element so what you can do is you can probably say J is initially minus one okay and then you can start from zero and you can go on till I ++ and you say hey array of I are you zero if you're zero okay fine J store this index because this is zero and just go out no need to go ahead go out and this will make sure J is stored as the first like wherever the first zero is if J is still minus one it means there is nothing and you can just stop you can just stop if J is still minus one there is no zero and all are non zero elements so you can stop the moment you have G what's the next step we did we took a i right at the next of J and this is where we start out so I said okay I'll start from J + 1 and I'll go until here and what did we do we said hey are you a non Zer are you a non zero he said yes I am so I'll check hey if array of I are you a nonzero number if you are a nonzero number can you please swap yourself with array of I and array of J and if you have swapped if you have swapped can you just move your j++ pointer because I will always be moving no matter what you do but the moment you get a non zero number you just swap it and then you move j as well but whenever I was here and it was a zero you did not do anything it say the I always moved I always moved because J will still stay where it is so J swaps and then moves ahead quite simple step two so the step is also done so if I have to figure out the time complexity can I do it now I think I can first we moved till here assuming this to be X assuming this to be X length where the first zero was found so the step one takes you beo of X because you're doing a break where X is the first index where the zero was form then you move from here to here which is the remaining n minus x n- x l so this is like the remaining nus X where you moved so the overall complexity is this plus this where X and X goes off so the time complexity overall is V go of one sorry V go of n are we using any extra space no we using the given array yeah we we have to tell that to the interview that Hey listen I'm modifying the array because that's required but we're not using anything extra we're not using anything out of the box so this will be the time complexity and space complexity of the most optimal approach that you have to tell to the interviewer so if you want to submit the optimal solution the problem link will be in the description what I've done is I've converted the same pseudo code into a C++ code just in case you want the Java and python codes the link will be in the description for notes you can go over there and check it out and you can try submitting it as well I'm focusing on the pseudo code so that you can write it in any programming language remember this so coming back to the sheet I can say that this problem is done the next problem that we will be solving is linear search linear search is one of the e easier problems while it comes to arrays it just involves iteration if you understand iteration in an array you should be able to solve linear search now what does linear search say it says that you'll be given an array array of numbers and you will also be given a separate number now to tell me which is the first occurrence very important which is the first occurrence of this number in an array so if I have to check this is where the number occurs what is the zero based indexing again very important what is the zerob based indexing so the zero based indexing is three so you have to return three yes you have to return three which means it like the number does exist in the third index if I give you something like 10 what if the number is 10 if I scroll through the entire array like if I look at the entire array the number 10 doesn't exist that's when you return minus1 simple right very simple how will you solve this yes quick iteration on the array and check that's like I'll just go across the array you know how to wrer in the array now you just go across and you say Hey listen if at any moment array of I is equal to equal to the number I will try returning the I index because that's where the first occurrence is if they want last occurrence you start wring from the last if they want all occurence then you can always store this I in some temporary array or some list and at the end of the day you can say return minus one which means I did not find it if there is a complete iteration done and the return statement was never ever executed then you will go across and return minus one now going to the compiler again the problem link will be in the description in case you want to try it out and this is how the code will look like and again the Java and the python code will be given in the notes so you can check them out as well so with this the most easiest problem in the AR playlist is done as well and now let's go to the next problem which is finding the union and the intersection of two given sorted arrays so what is the problem statement Union of two sorted again very very important word because this will be helping us to determine the most optimal solution so Union of two sorted arrays so this is array one which is sorted in itself might have duplicates array two sorted in itself again might have duplicates so what you have to do is you have to give me an Union array what is the meaning of union so what do you mean by Union it's basically you're given two guys and you just add them up but you do not repeat anyone you do not repeat anyone it's like if you have one okay one goes you have two two goes you have three three goes you have four four goes you have five five goes then you start from here you have two but wait two is already here doesn't goes three is already here doesn't goes four is already here doesn't goes four is already here doesn't goes five is already here doesn't not goes so this is how you can easily do an Union so the union of the both arrays will be 1 2 3 4 5 imagine I just go ahead and say Hey listen I also have a six in that case the union will be 1 2 3 4 five and six quite simple because six is over here it's not here but it's okay you have to add both of them you have to add both of them and make sure there is no duplicates so this will be the answer for Union of two sort AR and this is what you have to return so so this problem comes up in an interview the first solution that you'll be telling the interviewers should be the Brute Force approach what will be the Brute Force approach what are we doing we're combining both of them but we making sure the unique elements are just there in the union array so whenever we hear something like unique something like a map or like a set comes to our head because if we just keep on throwing everyone to the set at the end of the day the set will only contain unique elements in a sorted order in a sorted order very important because you have to return the Union in sorted order as well so can I say let's take a set data structure I like why not let's take a set data structure so assume this is my set data structure which is as of now empty I'll start iterating in the first array one put that into the set one again no two goes into the set three goes into the set four goes into the set five goes into the set perfect I it in the second array two already in the set if you try to put it into the set the set will say I already have it three already in the set set will say I already have it four already in the set four already in the set five already in the set six not in the set so after iterating in both the Ares the set data structure will have 1 2 3 4 5 6 and now what you can do is you can probably take a union array and in that array the size of that array will be nothing but the size of the set which is six and you can just pick up one element pick up one pick up two and put them into the array and put them into the array that's what it will be that's how it will look like once you have done this this Union array will be the union array of two sorted arrays and this will also be in sorted order why because you're using something like set if you're using something like like if you're using C++ do not use unordered set because if you use unordered set the ordering will get distorted and if the ordering gets distorted you will not be able to maintain the sorted order got it that's why you have to use something like a set data structure got it so if I have to write the Brute Force approach it's going to be very simple we we kind of Define the set data structure and then what we do is we go across the first array as you that to have a size N1 we can go across the first array and we can say set do insert and we can say array of I assuming the first array A1 of I and then we can go across the next one which is from 0 to N2 and we can say set do insert a2. I a2i so what this will do is this will put everything into the set once you've done this you can declare the union to be of set do size quite simp again and in this what you can do is just iterate again you can use an auto iterator you can iterate in the set once you iterating in the set you can say Hey listen maybe you can keep a pointer like I equal to Z and you can say Union i++ equal to it so first time goes to the zeroth index then to the second index if you're using something like a list or a vector you can simply write Union do add or push back in that case ID and this will add it directly you don't have to maintain an index so this is how the step two looks like now if I have to discuss the time complexity of this particular Brute Force approach what will it be can I say the stes be go of N1 log N1 not N1 log n where n is the size of the set so N1 log n and over here can I say that the complexity will be n to log n again n log n where n is the size of the set which will be varying at every step so you cannot precisely say that logarithmic of something you cannot precisely determine the complexity for a set correct and now for this it's a v go of N1 + N2 at the worst case imagine the array one contains all different elements than array two then it will be everything different and all different will go into the set and if all different go into the set it will be N1 over here N2 over here so the total elements in the set will be N1 + N2 if every element is unique if every element is unique so can I say the time complexity stands at for the first insertion n log n for the second N2 log n and then a beo of N1 plus N2 at the worst case and the space complexity is we're using an external set which might end up taking N1 plus n at the worst case if all of them are unique and then we using an Union array in order to return the answer again this this is not used to solve the problem this is used to return the answer please uh specifically mention that to the interview that this N1 plus N2 space is used to return the answer I'm not using in order to solve the problem I'm just using it in order to return the answer got it this will be the time complexity and space complexity of the Brute Force approach so if you want to submit the Brute Force solution again the problem link will be in the description make sure to add hash include b/ STD because in this function snippet it was not there and this is how the code will look like in case you want the Java and python code there will be links in the description for the notes you can go over there and check it out so we done with the Brute Force approach now I will be moving to the optimal approach and we will be taking advantage of the fact that both the arrays are sorted and we will be using something like a two-pointer approach it's a very easy approach so what I will do is I will keep an eye pointer over here I will keep J pointer over here so I'll just erase these couple of lines perfect so I'll keep an ey pointer on the first element of the first array and I'll keep a JP pointer on the first element of the second array and now I will declare a union list and initially remember the list will be empty it will have a size zero it doesn't have any elements initially and now I will be like okay I'm over here and I'm over here if you have to look at the union array the first element of the Union array will be the smallest one will be the smallest one so if I have to take the smallest one who among it is a smaller one obviously one so what I'll do is I'll take the one into the Union array and I'll move the I pointer to the next index I'll move the I point to the next index now if I have to again take something into the Union array I'll definitely take one because it's still smaller than two but I say wait the last element I took into the Union array was one and Union means no repetion just unique elements like fine the last one was one so I would not take it I'm like okay I have a two I have a two so the next element I have to take it'll be two so I can take two from either so I'll take just two from the first and this two was not equivalent to this so I took it and now I'll move the I I'll move the now if I have to again take between three and between two I'll actually take two because Union always takes smaller which is at the front but this two is already here so the last element is equalent so I'll not take it I'll not take it but I will move the pointer I will move the pointer because it won't be taken because it's already there so I'll just move the pointer correct next I'll compare three and three I can take any so I'll just take the three I'll move the pointer next four and three but wait this three is already here do not take it move the pointer four and four again take one and four and move the pointer this time five and four four is already there because the last one is there so move it four is already there so move it this time compare five and five same take any one of them and move the pointer next it's over please please Focus the iteration on one of the arrays is over the iteration on one of the arrays is over if the iteration on one of the arrays is over what you will do is you will just say okay five you're already there six you're not there go so if iteration on one of the arrays is over you will you'll not compare anymore but you will iterate in the remaining portion of the other array you will iterate in the remaining portion of the other array and you will check if it's equivalent to back or not and then you'll keep on inserting into the Union so once it's done you will have your union array ready and this will be your answer got it let's code the optimal solution again the problem link will be in the description so we given this uh function sorted array where we have to return a list and we given a couple of arrays right so at first I'll do one thing I'll just figure out the size of the first array which is something like this and I'll also figure out the size of the second aray which is something like this and now I know I'll have two pointers I which will be pointing to the first index of the first array and J which will be pointing and then we will also have a list which will be the answer okay which is Union array and then at the end of the day we will be returning this particular list this is something we do now let's say we are comparing both we'll be comparing till both pointers are pointing somewhere which means we'll be comparing it till either I is lesser than N1 in the first array and J is lesser than N2 which means both of them are still somewhere in both the arrays and we say Hey listen on the first array if that's smaller than the second AR both the pointers are pointing if the first element is smaller than the other element in the other then I say okay I'll take this I'll take this but before taking I need to have a comparison if you remember when we are taking this one the union ARR already had a one so you did not take it right so I'll be like I need to compare so I'll be like okay let's take Union array what's your last El it's like back is this not equivalent to the current array I if this is not okay cool let's take it like fine I'll take it no problem and irrespective of whether you take it or you do not take it you'll move because if you take it it's fine if you do not take it that means that element is equivalent to something which is inside Union array so you will not be considering that element anymore so move but but if you're doing a DOT back the union ARR has to have something what if what if I come to a case where this is for the first time and the union array is empty then you always take the one if the union array is empty because it's the first time if it's the first time which means Union array do size is equal to zero then you sorry or you always take it so if the size is zero it means it's for the first time just take it and similarly you go to the else which means the other element is the smaller the other element in the B array is smaller if that's the case cool I'll just copy paste the same thing maybe I'll just copy paste the same thing I'll copy paste the same thing and I'll say should not be equal to B of J should not be and if it is not then I'll just push in B of J I'll just push in B of J once this is done I I'll just move the J Point quite same quite same and after this is completed I will return but wait what if while iterating this got exhausted the first array got exhausted so there must be someone left if you remember our case we completed the iteration and there were still two elements left there were still two elements left what do you that means J would be somewhere here so you need to iterate for this these remaining elements so WR it so you say okay listen if the first was exhausted J will still be there and if J is still there let's let's do the same thing I'll say Hey listen I'll do the same thing which means okay fine if you're not equivalent go in and just keep on moving and what if the second got exhausted so I will still be there there is someone still in the first and if there is someone still in the first you simply take take it without any thinking yes without any thinking you simply take it and once you've done this once you've done this you can return it so this is the remaining array that you just iterate through once you've done this you can go ahead and really let's submit I'm I'm sure that I write error free code oh yeah I do so at one go I've submitted this code and this is exactly how it will look like now if I have to ask you the time complexity of this particular code what will be the time complexity of this particular code can I see I'm iterating in some way throughout this entire somewhere iting throughout this entire and some I'm also hting throughout this entire because no matter what we do we will itate through every element no matter what we do we will beating through every element do we do anything apart from this yeah we definitely enter that into the Union array but do we iterate or do we do any fall Loops or any Loops apart from this no steps will always be like this you'll be either here either here either here either here either here either here either here so that that means it'll be of N1 plus N2 yeah there there are lot of Loops lot of these but at the end of the day if you think carefully you'll actually be visiting every element once so N1 plus N2 is the time complexity and space you can say I'm just using N1 plus N2 at the worst case if all the elements are unique and that is for returning the answer not for solving not in my algorithm using that to return tell that specifically to the interviewer and that's how your optimal solution will look like in order to Union to sorted arrays so what I can say is I'll go back to the sheet the union is done now it's time to understand the intersection of two sorted arrays so what is the problem statement State intersection of two sorted arrays again the term sorted is very important if you want to go for the optimal solution so keep that in mind okay what do you mean by intersection the element that is present in both are remember this present in both present in both so if I have to write the intersection of A and B sorted arrays so if I see one I don't see a one here so I will not take it if I see two I actually see a two over here so there has to be a corresponding match so I see a two over here so I'll take it if I see again two there is no cor like there is a two but there is this two has already been occupied like is already been matched with this so there is no corresponding two for this so I I do not take it if I see three for this three I can say I have a corresponding three so I'll take it now for this three I have another corresponding three so I'll again take it remember over here repetion of elements is allowed because you are seeing present in both next four no one five yes there is a corresponding five six there is a corresponding six as well so this will be your intersection array right so if this question comes up in an interview the first solution will definitely be a brute for solution and what will be the brute for solution we are saying that for every element there should be a corresponding element for a two there should be another two for this two there is no another two so we do not take it so we just take one two so for every element there has to be a coresponding element in the other R we'll just follow the same process we will say okay fine we'll pick up one and we will check if there's a one if there is we will take it we will pick up two and we will check if there is a two and we say we have a two so we take this two then we will say we will pick up this two and we will see if there's a two there is but this has been taken by this so he won't take it so it's like picking up one element and checking but at the same time keeping a track if someone has been used previously or not so what I know is I have to keep a track if someone has been used previously or not so what I'll do is I'll probably create a visited array I'll probably create a visited AR AR which will be marked as 0 0 0 0 0 which means they haven't been used they haven't been used as of now and now what I'll do is I'll start with the first element in the first array you can also start with the first element in the second array as well but I'll start with the first element in the first array and I'll say one are you here are you here are you here I'll just go through the entire B and I will not find a one so if I do not find a one I will end up not taking this into my intersection array and I will move forward next two are you here yes I here so I'll take this two the moment I take this two I will mark it as visitor I'll say this two has been taken by someone this two has been taken by someone fine we have one two who found its corresponding two in the other array now I'll move ahead when I move ahead I have a two and I'll see for a two I see a two but it's taken now I see a three so since it's a sorted array I'm sure that Beyond this there will be no two so I stop I sto I'll be like I did not find next three let's check two no three yes yes let's take three and at the same time see you are taken you are taken let's go ahead three again two again two no not equal to three three yes equal but but but taken this guy is already committed so I'll not take him next oh he's not committed and that's three so let's take this three and Mark it as one next four now when we have four do we have a four four four four no do we need to check for the next no it's a sorted array so if five like till five you did not get it beyond that everything will be greater than five so no need to check it next five five will'll get it here so take five and you'll mark it six six you'll get it here so you'll take it and Mark it and the iteration is over once the iteration is over you will have your answer array yes you will have your answer array and once you have your answer array that will be the brute force method got it so if I have to write the pseudo code what I'll do is I'll say N1 is the size of the a array N2 is the size of the B aray and I'll probably keep a visited of size N2 and I'll mark every one of them as zero once I've done this I will try picking up one element from the first array always and for that one element remember we have an answer intersection which we have to fill for that one element I will go through J and I'll go through the second array now what am I doing I'm saying okay I is zero which means I standing here and I'm moving across the entire array that's that is that is what I'm doing right so I will be like okay if array of I is is equal to equal to array of BJ if it is if it is that means for this a ofi we find a corresponding in the B AR and if you find it we can take it but wait has it been taken previously and this is where the visited array will tell me the visited of the jth index so this is the indexing of the jth index are you not taken oh you're not taken perfect please come to our answer so this will be the corresponding added so I'll say visited of J has been taken so please mark it and you can break out there's no need to do any further you can break out once you have done this perfect and what's the other thing if this is this condition is false we just move ahead but be sure if at any moment a of J sorry uh if at any moment the array of B and J is greater than array of a of I we say okay we've exceeded you will never find even if you go ahead so this will kind of truncate this Loop just in case you are getting someone greater there's no point in going forward there's no point in looping so you stop and you can just stop it here so for every I is for every I you will Loop through the entire array B and you'll try to find someone same and which is not taken if it is not then you kind of add it to your answer and mark it it has taken and you break out so you keep on doing for every eye and at the end of the day you will have your answer AR so if I have to determine the time complexity of this Brute Force approach what will it be obviously two Loops running so that's an N1 cross N2 are the worst case if the break and all these things never happen at the worst case N1 cross N2 and what is the space complexity obviously the space complexity is B go of N2 in this case imagine you apply a visitor array for this you can do the reverse as well where you have a visited for this and you iterate for this and you check for the corresponding in the other array you can do how you wish to that is okay so we can say that that so we can say that in the order in which we apply the algorithm the space complexity might change so logically it will make sense to have the algorithm in such a way that for the smaller array is for the smaller array we have the visited array so that the space complexity is minimum but it's okay this is what you have to tell to the interviewer that this is my Brute Force approach so in case you want to try out the problem the link will be in the description and this is how the root Force solution code will look like but this is something which is taking a lot of time yes this is taking N1 into N2 and that's a lot of time so we'll be trying to optimize this and let's understand how the optimal solution will look like so the optimal solution depends on on both the arrays being sorted since they are sorted we will be applying something as a two-pointer approach and it's going to be very simple what we do is we basically keep two poters one at this one and the other one at this and now we will be taking like we will be taking the intersection of both so tell me something if this one like this is the first case is not equivalent to this two can I definitely say that we do not have any occurence of one can I definitely say that I can so I'll be like there's no occurrence of one please move please and then I'm like at two and at two like they equal oh there is an occence there is an Ence so be like let's take two and if there is an Ence can I say this two is for this two right so I'll move both I'll move both because they matched they matched let them put into a relationship and let's move okay now we have two I'm like three okay for this two it's lesser than three so I definitely cannot have a partner for two so I'll be like not an issue let's move now this three is a partner of this three so let's take three let's try to move both we have tried to move both now and now this three says okay fine I can still have a partner so again take three and move now this four says I'm lesser than five so I definitely cannot have a partner now the five says I'm equivalent to you so five will be a partner let's move now both so whenever they match move both if they do not match then just move next six equivalent to six so I take six and it moves I run out of Partners I run out of Partners remember this I've taken six and the moment I move both this I exceeds so there's no one else to be compared with there's no one else so there there's no one else who will be partner with so it's over so once you have done both the pointers this is how it will look like and this will be your answer quite simple so if I have to code this uh the problem link will again be in the description it's going to be very simple I is going to be zero J is going to be zero and I'll be keeping a vector int and so and at the end of the day I will definitely be returning it and I know one thing for sure I'll be iterating in both of them so I lesser than n and J less than n quite and now I know one thing if this particular a of I is lesser than b of J for an example obviously if a is smaller it doesn't have a partner please move you don't have a partner please move and I'm like what if it's the other way the other way means what if B is smaller then definitely the B Guy cannot have a partner sorry please move but if it's not the case they equal you guys can go into a relationship isn't it so I'll be like okay okay please go and both of them are SE so doesn't matter which one you insert and both of them can go ahead because you guys are committed now you cannot have dual relationship go ahead and let the other ones find theirs fine I'll go ahead once this is done the answer will be stored here and that's it so if I I'll just go go ahead and submit it so if I submit it I will see that this is running running running running I'm absolutely fine yeah so what will be the time C lexity can I say the moment I run out of partners for someone that's when I end but what can be the worst case when you like keep on going keep on going since I'm moving I I'm moving J so the worst case can be once this executes the other time this executes the other time this the other time this so if you're like i j i j i j i j i IG so we moving like one by one so it's like it's more like one here you're here this Moves In The Next Step this Moves In The Next Step this Moves In The Next Step this Moves In The Next Step this Moves In The Next Step this Moves In The Next Step this Moves In The Next Step this moves so moving one by one by one and this one has an N1 length this one has an N2 length can I say the time complexity will be N1 plus N2 that is in the worst case that is in the worst case can I say the space complexity are we using any extra space the answer to that is I don't think so we're not using any extra space so the optimal solution has a Time complexity and space complexity of this that that is seen on the screen so I can say that have successfully solved the optimal solution of intersection of two sorted arrays so I can go back into the sheet and I can say this is done as well so with this we cover up nine problems from the easy section of the array I know this was a long video and I hope you enjoyed every bit of it so please please do consider giving us a like because I put have enough effort for this video and you can you can understand by the voice so to continue our tradition if you have understood everything do comment understood and also make sure you do the assignment there was an assignment that you have to WR rotate the aray by D places so make sure you do the assignment and drop the code in the comments and if you are new to our Channel please please do consider subscribing to us and if you have haven't followed me on all my social media handles uh LinkedIn Instagram Twitter all the links will be in the description do join our telegram group with this I will be wrapping up this video Let's SP in some other video till then bye-bye take care Bren don't forget your golden I will