Transcript for:
Understanding Array Operations and Algorithms

hey everyone welcome back to the channel I hope you guys are doing extremely well so this is another video from the stripers A to Z 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 algorithms in any of the interviews in any part of the world so till now we have covered uh till step 3.1 fourth problem and in this video we will be covering these five problems just in case you wanna directly jump to any of the particular problem the timestamps 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 group 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 step-by-step 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 clicks 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 rooted 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 are rotating it so it'll be like two three four five 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 fruit 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 so 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 zero is one now what I say is okay I'm standing here this two ideally since it has left rotated by one should go at the zeroth index so I'll place it here so it's I'll place it place it at one index before and then again I will move that index and I'll see place it at one index before which is again the I minus one and then again I'll move the ith 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 see place this 5 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 will you implement it can I say this is nothing but the first index and this is nothing but the N minus one at 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 until I N minus one so you can run a loop till n minus 1 and then you can say this ith guy will go to I minus one so array of I minus 1 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 1 whatever we stored in temporary we take it and we will paste it over here as simple as that if I have to discuss the time complexity what will be the time complexity yes a simple bigo of n pass because we are running this Loop for n times thereby the time complexity is Pico of n are we using any extra space no thereby the space complexity is pic 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 Big of n because we're using an array to solve the problem yeah that array is already there what are you using so if someone says what is the space used in your algorithm then it becomes big often because you definitely are using this array but it is already clear but you are using it in your algorithm but if someone says what is the space that you're like what is the extra space that you are using then the extra space is Big of one but in for the algorithm we definitely are using this so understand the structural 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 we go fund so there's a subtle difference whenever you go to an interview always clarify it tell them that sir the extra spaces so whenever you go to an interview always clarify this tell them server map the extra space that I'm using is recovery 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 the series 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 interface so that every concept of yours is Crystal clearly presented to the interview and he is impressed this is how you should write 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 solve this problem now if this problem comes up in an interview the follow-up question very likely will be the next one which is left rotating an array by D places till I have solved a problem where you take left to read 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 follow-up question will be so let's try to solve this follow-up problem so let's understand the problem statement it states you to left rotate the array but This Time by Deep places assume for this given example array we have D equal to 2 so it's stating that left rotated by two places so these 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 one and two 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 one two three would have been left rotated and they would have been moving by three places ahead so in that case the answer would have been four five six seven and then one two three so that's the answer for D equal to three now what if yes what if like let's count the size of the array it's like one sorry my bad one two three four five six seven seven is the size of the array imagine I asked you can you rotate this yes can you rotate this by seven places so if you actually rotate this by seven places it'll again come back to the same place it will again come back to the same place so rotating it by seven pieces 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 makes sense so if it is 9 rotation can I break it down to seven plus two and say okay on seven notation it will be the original variety and then you just have to do a meager two rotation on the array does make sense if I tell you D equal to 15 can I write 15 as 7 plus 7 plus 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 notations will always bring you to the original array the remaining is what you need to do so can I see whatever array 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 array can I say this if it's given like 20 doesn't matter I'll just have to do six rotations because 20 modulus 7 will be 6 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 one two three four five six and this will go here that is the meaning of six rotations so anything less than 7 is very easy to solve that's why we will always do a modular of n because end rotations like on multiple of n rotation means coming back to the original array 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 modular with n and that will be solving your problem and that will be solving your problem if D is very very luck 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 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 store one element if D is 2 you will be storing two elements into this temporary and then you will rotate and then you will take the Two element and you'll put it on the back that's what we will 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 fields 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 what 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 6 and if D is 3 we start shifting from third index we start shifting from the third index which is the D Authentics 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 ith index if this is your ith 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 plus plus and I can say array of because the third index guy will go to the zeroth index guy please observe this guy goes here and this will become full 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 now you still have three places where five six seven 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 one two three 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 Memories so can I say if we are shifting by three places it means if the size of the array is 7 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 I'll be like okay seven minus three which is basically n minus D which is basically seven minus 3 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 in like n minus K and I'll go on to the last quite simple and what will it put in the rifi 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 easiest way to do this is like without any mathematical calculations or anything the easiest way is say J equal to 0 and put J and then do a j plus plus so what will happen at first G is here because that's the zeroth index takes up one puts it here then J goes here and this will easily fill up the last three places that's one of the ways to do it but if you are 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 chair 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 dth index can I see this I can now can I see someone who's at the first index will always go to n minus D plus 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 Plus 2. can I say this and this is the second index so n minus D plus 2 so can I say if you are base index is n minus d n minus D is your base index can I see this temporary will say okay if you are standing here if you are standing at I then you just need sorry n minus D to get your base index can I see this you just need I minus n minus t because again I'll repeat this is n minus D plus 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 2 and you can get the second guy from here quite simple match 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 t then the next index will definitely n minus D plus one the next will be n minus D plus 2 right and we're taking from 0 1 2 so this is like 0 this is like 1 and this is like two that's why wherever you are currently at just subtract the base index if you subtract first you will get 0 then you'll get 1 then you'll get two which apparently means this so you'll automatically take the temporary so 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 equal to 0 I lesser than D and I plus plus and in the list you can probably take a vector or a list in Java pushback in Vector in Java it will be list dot add array of I 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 plus plus or Java but coming to a cleaner code we just take the array as the input and then we take the d and then we call the left rotate function which rotates it and then we just kind of 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 something less than n because we know on all the multiples of n it will come back to its original array and then we store everything into temporary then we shift it and after that we place back temporary into array white 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 see the time complexity will be in order to do the step one this is taking a big O 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 we go of n minus D because those many elements are what you will be transferring or shifting to the front so n minus D the next one putting back temporary so the slide again we go of D because you're putting back D elements so that's like we go of D and if I have to add it up it will become we go of n plus d this will be the time complexity and if I ask you what is the very important mode what is the extra space extra so the extra space used will be because of D why because we are using a temporary array 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 pick off one extra space that's when you say okay maybe 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 type 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 one two three yes this one two three e is over here okay and this four five six seven is over here so what we can do is we will say okay listen let's take the first three elements and try to rotate it so I try to reverse it so if I reverse it it'll be three two one every person 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 seven six five four now what else is okay this is the Reversed array post to reversal one is the first D the next is the n minus d l 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 4 will come first this 5 will come here the 6 will come here the seven will come here this one will come here this two will come here and this three will come here done and dust it yes this was 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 added array plus n so if I perform this three reverse if I perform this three reverses I will actually get the result and I I don't have to do like I don't have to take a temporary do shift things and then copy pasting back again just three reversals first for the D elements then from D to n and then the entirely and if I do this I should be done and this will take me a Big O of 10 sorry because of D complexity because we are reversing D elements this will take me a Big O of n minus D because we are reversing n minus t elements this will take me a Big O of n because we are 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 2N 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 where the space complexity over here will be we go 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 plus plus so we just give this little reverse from array plus 0 like 0 the next to D minus 1 to D minus 1 and then you can say again reverse add it plus d to add a plus 1 this means from dth index to n minus 1 at index then I can say again reverse array Plus sorry plus 0 which means from 0 then x 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 we'll submit this I should be submitted so in case you're 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 plus plus 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 and 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 the right rotate the RFID places I have to come up with the solution and this will be an assignment try to think how will you write rotate an array by T basis 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 Brew to Optimal that will show your process and that does not impact in the interview set 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 will be five then there will be one so basically what you do is you take one two three two four five one so I took all the non-zero numbers and I put them into the front of the array once I've done that what are the remaining elements there are zeros and there are three zeros so 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 Force 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 group 4 solution if you look at the problem it states all the non-zero numbers at the front like all the non-zero numbers at the front so my mind kind of sees 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 non-zero numbers and again you can store them in a list in an array wherever you wish to so I have all the non-zero 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 that's then take three put it here let's then take two put it here doesn't take four put it here and 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've done that I know all the non-zero numbers are at the front if I have 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 I treat store all the non-zero numbers then put all the non-zero 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 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 0 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 approaches 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 0 and then you can go to Temporary dot size because that will tell you how many non-zero 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 non-zero numbers back over here it is like one two three four five six seven 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 eight and go to the last which is the n minus one at index so you start filling from the seventh index which is nothing but number of non-zero elements so you'll just start from the non-zero elements like whatever it is the number of non-zero elements I'll go till the last and you will say in all of these places I'll just fill up 0 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 O of n because I'm running an entire Loop can I say this will be taking imagine there is X imagine there are X non-zero 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 non-zero the remaining will be n minus X so can I see the total time complexity to be Big O of n plus b go of X plus b go of n minus X so minus X Plus X will cancel and then we go off to n will be the time complexity of this particular one and can I see the extra space again very important the extra space that I'm using will be we go of X where X is the number of non-zero numbers and that at Max can be we go of n imagine the entire array to not have a single zero then you will enter transferring the entire array into the temporary so thereby the this is the worst case 7 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 we 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 code The Brute Force solution and submit it the problem link will be in the description there is a reason why I am 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 interview 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 will 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 the strain put it here somehow I can take this two and put it here and maybe somehow I can take this 4 and can I 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're already iterating in the array remember this we are already iterating 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 to next index after 0 which is this I'll point it over here now what I say is I start from here and I check are you a non-zero number he says yes I am a non-zero number okay we have a zero here let's let's start so I'll do as well so the 2 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 am a non-zero number I'll say Okay swap to the zero so I'll go across and again stop so 3 goes here 0 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 or even one zero number he says yes I'm a non-zero number I'm like okay so so two goes here zero goes here perfect and now I'll move by 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 non-zero number he says no so no swapping and this will be 0. perfect and the ga will be moving here and the I will be moving here once I've done this I'll just clean this he says yes and 0 comes in here and then I move y here next one are you a non-zero number he says yes so one comes here zero 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 non-zero elements are in the front and all these zeros went to the last very simple and it's done and what we did was a single iteration if we carefully observe what it 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 say the optimal solution what is my step one if I have to ask you what is my step one it's finding the first zeroth 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 until I plus plus and you see hey array if I are you zero if you are zero okay fine J store this index because this is zero I 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 1 it means there is nothing and you can just stop you can just stop if J is still minus 1 there is no zero and all are non-zer elements so you can stop the moment you have J what's the next step we did we took a i right at the next object and this is where we start out so I said okay I'll start from G Plus 1. and I'll go until here and what did we do we do we said hey are you alone he said yes I am so I'll check hey if array of I are you a non-zero number if you are a non-zero number can you please swap yourself with array of I and array of J and if you have strapped if you have strapped can you just move your G plus plus one 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 says 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 two 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 B go of X because you're doing a break where X is the first index where the zero was formed then you move from here to here which is the remaining n minus x n minus X length so this is like the remaining n minus X where you moved so the overall complexity is this plus this where X and X goes off so the time complexity overall is Big of one sorry week of n are we using any extra space no we're using the given array yeah 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 solution the problem link will be in the description what I've done is I've converted the same pseudo code into a C plus plus 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 now the next problem that we will be solving is linear search linear search is one of the 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 you have to tell me which is the first organ it's 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 okay very important what is the zero based indexing does it so the zero waste 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 minus 1. simple right very soon 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 write it 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 ith index because that's where the first occurrence is if they want last occurrence you start right returning from the last if they want all occurrence 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 -1 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 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 node so you can check them out as well so whether it's the most easiest problem in the array 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 goals you have three E3 goes F4 4 goes f55 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 does not close so this is how you can easily do an Union so the union of the both arrays will be one two three four five imagine I just go ahead and say Hey listen I also have a six in that case the union will be one two three four 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 sorted arrays 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 interviewer should be the Brute Force approach what will be the Brute Force approach what are we doing we are combining both of them but we are 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 autumn in a sorted order very important because you have to return the Union in sorted order as well so can I see let's take a set data structure I mean like why not let's take us a 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 that set 5 goes into the set perfect 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 sex not in the set so after iterating in both Diaries the set data structure will have one two three four five six 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 sex 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 eye 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 y because you're using something like set if you're using something like like if you're using C plus plus 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 cannot Define this data structure and then what we do is we go across the first array assuming that to have a size N1 we can go across the first array and we can just set dot 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 dot insert A2 dot i a to I so what this will do is it will put everything into the set once you've done this you can declare the union to be offset dot size quite simple again and in this what you can do is just I2 again you can use an auto I Twitter you can write it in the set once you are treating in the set you can say Hey listen maybe you can keep a pointer like I equal to 0 and you can say Union I plus plus equal to YT so first time goes to the first zeroth index then to the second index if you're using something like a list or a vector you can simply write Union dot add or pushback 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 see the stakes we 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 see that the complexity will be N2 log n again n log n where n is the size of the set which we'll 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 big O of N1 plus N2 are the worst case imagine the array one contains all different elements than array2 then it will be everything different and all different will go into the set and if all different go into the set it'll be N1 over here N2 over here so the total elements in the set will be N1 plus 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 big O of N1 plus N2 are the worst case and the space complexity is we're using an external set which might end up taking N1 plus n to the worst case if all of them are unique and then we are using a 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 first solution again the problem link will be in the description make sure to add hash include with Slash STD because in this function snippet it was not there and this is how the code will look like in case you want the job and passing code there will be links in the description for the notes you can go over there and check it out so we are 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 a j point over here so I'll just erase these couple of lines perfect so I'll keep an eye pointer on the first element of the first array and I'll keep a g 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 initial 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 use the I pointer to the next index I'll move the icon 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 see wait the last element I took into the Union array was one and Union means no repetition just unique elements like fine the last one was once 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 will be two so I can take two from ether so I'll take just two from the first and this 2 was not equivalent to this so I took it and now I'll move the I tell you that now if I have to again take between 3 and between two I'll actually take two because Union always takes smaller wedges at the front but this two is already here so the last element is equivalent 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 next four and three but wait this three is already here do not take it move the pointer four and four again take one four and move the pointer let's try five and four 4 is already there because the last one is there so 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'll you'll not compare anymore but you will I treat in the remaining portion of the other array you literate in the remaining portion of the other array and I will check if it's equivalent to pack or not and then you will 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're given this uh function sorted array where we have to return a list and a 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 also figure out the size of the second array which is something like this and 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 attic and then we 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 and we say hairless on the first array if that's smaller than the secondary both the pointers are pointing if the first element is smaller than the other element in the other area 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 array 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 level it's like back is this not EQ valid to the current RFI if this is not okay cool let's take it it'll be like fine I'll take it no problem and irrespective of whether you take it or you do not take it you will 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 you move quite but if you're doing a DOT back the union array 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 this is the first time which means Union array dot size is equal to zero then you always 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 is the same thing I'll copy is 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 C I'll just pushing B of J once this is done I'll I'll just move the J Point quite see quite C and after this is completed I will return but wait what if while I trading 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 write it so you say okay listen if the first was exhausted J will still be there and if J is still there 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 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 Aries 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 so at one go I have 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 way throughout the center somewhere I might go out to say that and somewhere also iterating throughout this entirely because no matter what we do we will I treat through every element no matter what we do we will be hydrating 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 for Loops or any Loops apart from the snow steps will always be like this you will be either here either here either here either here either here so that means it will be go of N1 plus N2 yeah there are a lot of Loops a 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 two 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 statements take 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 array 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 2 I actually see a 2 over here so there has to be a corresponding match so I see a 2 over here so I'll take it if I see again two There Is No Chorus like there is a two but there is this two has already been occupied like it's already been matched with this so there is no corresponding two for this so 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 so I'll again take it remember over here repetition 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 this question comes up in an interview the first solution will definitely be a group 4 solution and what will be the Brute Force 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 corresponding element in the other hand 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 we will pick up two and we will check if there is a two and we say we have a 2 so we take this two then we will say we will pick up this 2 and we will see if there's a two there is but this has been taken by this so we 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 will do is I'll probably create a visited array I'll probably create a visited array which will be marked as zero zero zero zero zero 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 bre 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 to are you here yes I am here so I'll take this too the moment I take this two I will mark it as visitor I'll say this too 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 2 but it's taken now I see a three so since it's a sorted array I am sure that Beyond this there will be no two so I stop I stopped I'll be like I did not fine next three let's check two no three yes yes let's take three and at the same time see your taken you are taken let's go ahead three again two again two no not equal to three three yes equivalent 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 well next four now whenever you have four do you have four 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 if I will get it here so you'll take five a little market 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 ready 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 sudo code what I'll do is I will say N1 is the size of the array enters the size of the BNA and I'll probably keep a visited of size N2 and I'll mark every one of them as 0 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 secondary now what am I doing I'm saying okay I is 0 which means I is 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 equal to equal to we find the corresponding in the bra 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 JF index so this is the indexing of the GM 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 but Bishop 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 as taken and you break up so you keep on doing for every eye and at the end of the day you will have your answer 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 n two are the worst case if the break and all these things never happen at the worst case N1 cross into and what is the space complexity obviously the space complexity is bigo 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 UI trade for this and you check for the corresponding in the other array you can do how you wish that is okay so we can say that that so we can see 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 interview 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 4 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 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 pointers 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 2. can I definitely say that we do not have any occurrence 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 a two unless they're equal oh there is An Occurrence There Is An Occurrence so I'll be like let's take two and if there is An Occurrence can I say this 2 is for this two right so I'll do both I'll use both because they matched they matched let them put into a relationship and let's move okay now we have to I'm actually 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 the partner of this three so let's take three let's try to move both we have tried to move both now another three says okay fine I can still have a partner so again take three and now this force is I'm lesser than five so I definitely cannot have a one now the five says let's hope not 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 that 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 is no one else to be compared with there is no one else so there there's no one else who will be partnered with so it's all 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 end answer and at the end of the day I will definitely be returning it and I know one thing for sure I'll be actually reading so I less than n and J is the name 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 party please move and I'm like what if it's the other way the other way means what a b is smaller then definitely the B Chi cannot have a button sorry please move but if it's not the case the equal you guys can go into a relationship isn't it so I'll be like okay please go and both of them are seem so it 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 this 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 and go ahead and submit it so if I submit it I will see that this is running running running yeah so what will be the time complexity can I see 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 the other time this execute the other time this the other time this so if you're like i j i j i j i j i j i j so we are moving like one by one so it's like it's more like once here you're here this moves and the next step this Moves In The Next Step this moves 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 n one plus N2 that is in the worst case that is in the worst case 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 also this that is seen on the screen so I can say that I've 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 arrays 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've put up enough effort for this video and you can you can understand by The Voice so to continue our tradition if you've understood everything do comment understood and also make sure you do the assignment there was an assignment that you have to write rotate the array by ID 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 and explain some other videos [Music] I will find the light in