hello everyone and welcome to geek or Geeks today the problem which we going to see is Union and intersection of two sorted arrays here by sorted arrays we mean that the RS should be sorted in ascending order starting from the smallest element to the largest element so now let's look at uh what do we mean by Union and then we'll look at what do we mean by intersection so by Union we mean uh that uh suppose we are given two sets set a and b then the union is a set of elements which are in a in b or in both A and B for example we have the two arrays array one and array two so the union of these two arrays will consist of all the elements which are in either a or b or in both of these arrays similarly the intersection so intersection is basically the uh common element between the two arrays so uh we have array one and array two here so the common elements are three and five so three and five becomes the intersection so intersection can uh can also be uh phrased as uh the set of uh Elements which uh of a which also belong to B that is the common elements now uh let's look at the algorithm to find the union so to find the Union uh we'll uh have two index variables I and J and we'll initialize the variables by zero uh then what we do is uh we start comparing the element at index I of AR one with element at index J of array 2 so if element at index I of array 1 is smaller than elemented index J of array 2 then we print elemented index I of r 1 and we increment I if it's the other way around that is elemented index I of aray 1 is greater than elemented index J of aray 2 then we print the elemented index J of aray 2 and we also increment J if both of those elements are same then what we do is we print only one of them so we can print any of them and we print both I and J this is done because in the union we want to count the common elements only once once this is done so at least one of the arrays will be exhausted by exhausted I mean the all the elements of one of the array will be inserted inside the union array then what we have to do is we have to just uh insert the remaining elements of the larger array into the Union so uh let's start with the uh drw one before proceeding to the code so we have these two arrays array one and array two and index variables I and J as zero so we are we'll be comparing these two elements first so one is smaller than two so that means uh we'll increment I by 1 and we'll put uh one inside the union array so one is uh I is 1 and J is zero so now we'll be comparing three with two so two is smaller than three so we'll put two inside the union and we'll increment the value of J now Y and J is 1 so we'll compare three with three so these both elements are same so we come to this condition so we'll put three inside the union array and we will increment both I and J so I and J becomes two and the union array till now is 1 2 and three so now we'll be comparing four with five so four is smaller than five so uh we increment the value of I and we put four inside the union array so I is 3 J is 2 so this is the third element this is the second element now these both elements are again same again we come to this condition so we'll put five inside the union array and we'll increment both I and J now we are comparing 7 with six so 6 is smaller than 7 so we'll put six inside the union array and we'll increment J now we are done with this array basically all the elements of array 2 are inside the union array already so we'll just put the remaining elements of this array inside the union so here we have the Union now let's look at the uh C code for this so we have a driver program here where we have just T2 arrays we are calculating their size and then we have the actual uh function which will Implement our algorithm which takes us argument array one array two and the size so this is the function uh so the two input arrays and their sizes so now as per the algorithm we initialize inj with zero then we have this while loop here uh what the condition inside the while loop uh signifies is that uh this y Loop will be running till one of the array is exhausted so inside this condition we'll be comparing the elemented index I of array 1 with elemented index J of array 2 if uh the uh elited index I of AR 1 is smaller then we print the elited index I of r 1 and we also increment the I if it's the other way around then we print the elemented index J of R2 and we also increment the value of J if it's the third case where both of the elements are same so we can basically uh print any of those elements so we print array at element J element at index J of AR 2 and we also increment the value of J and I once uh one of the array is exhausted so it will come out of this condition so then we have these two Loops here to to uh basically uh print uh print the remaining elements of the larger array so this ensure that we have the correct Union so now the time complexity of this algorithm is order of M plus n this is uh in the case of worst case so suppose we have array one which has the elements 1 2 and three and we have another array which has the elements 4 five and six so in that case what will happen is that uh uh the uh this uh while condition will be running three times and when uh one of the arrays that if the first array is done then we'll be left with the whole of the second array and then this condition will have to run three times so total of six times for six element so that is why we have the time complexity of order of M plus n now now let's look at the algorithm for intersection so the algorithm is uh basically very similar but with some minor tweaks here also we initialize the variables with zero here also we compare the same elements but because here we are just finding the common elements we are going to print the element only in the case that both the elements are same otherwise we just increment the value of I or J whatever is the case so in case both the elements are same then we print any of them and we also increment I and J so this is pretty much similar to the Union uh so let's uh start with the tri uh I think uh it will be very clear with the triun so we we'll have these same arrays as in the previous case and we'll compare one with two so one is smaller than two so increment I we do not put any element inside the intersection array so now we are comparing three with two so again two is smaller than three so we just increment J and will not put anything inside the intersection array now we are comparing three with three which is common element so we'll put three inside the intersection array and we incent both I and J so I and J becomes two so we comparing four with five so four is smaller than five so we'll just increment the value of I so value of I becomes three so now we comparing five with five again the elements are same so we'll put five inside the intersection array and we increment both I and J so I becomes 4 and J becomes three so six is smaller than seven so uh we'll just increment the value of J to four and so so now we are done with this array two and in case of intersection because we are finding only the common elements so there cannot be a common element after we are done with the one array any of the array so we stop here and this is our answer so now let's look at the code again the driver function is is basically the same we have just changed the name of the uh function again we have the same input uh input arguments we have the initialization the same condition uh the only difference is that uh here in these two conditions we are not printing the element we are just incrementing the index variables I andj we only print in case of uh in case where element these two elements are equal so we also printed and you also increment the index variables again for the same reason as uh in the union case we have the time complexity of order of M plus n so that is all for this uh video uh all the content in this video can also be found on this URL for geeks for Geeks so you can go to this URL and uh try the exact code and uh you'll get I'm sure that you'll get uh a good feel of it yeah thank you