CodeCamp Day 7 | Advanced Sorting techniques and Problem Solving

foreign [Music] [Music] together [Music] so hello everyone a very good evening to everyone present here uh just give me a confirmation in the chat box that I am properly Audible and visible so that we can very quickly start hello Pawan how are you hello Ajay hello ashutosh uh yeah just give me a slight confirmation that I am properly audible so that I can very quickly start yeah a very good evening to everyone and welcome to today's session and yes thank you Pawan very much so yeah uh do write your names in the chat box I see around 10 people are around 33 people alive with me so do write your names in the chat box so that I could get to know your names or just do a plus one that would suffice hello Karthik hello Pavan just write a plus one in the chat box okay so yeah and a few pointers before we start I would really appreciate if you all could interact with me while we are progressing in the session that would very certainly help me and at the same time it will help you as well okay so today is the day 7 of code camp and this particular series we have brought at Geeks for gigs for you all so that you could basically get into a habit of solving coding questions on a regular basis okay so you must be seeing Siddhartha and Yash uh in the first six days and you must not have seen me on on this channel on a recent basis but I am also a mentor at dx4x and I will be introducing myself shortly hello Ashish kindly do not spam just one single plus one is good okay so let me just uh share my screen and then we will start uh just give me a minute to me yeah I hope my screen is very properly visible to everyone out here okay here hello Ashish so let me just change the layout uh which will basically be helpful for you all okay so yes I think my iPad screen is very properly visible to everyone okay hello Raj yeah so uh those who are joined with in this particular live session can you please write that whether you will be appearing for your internships or your placements in the coming internship and placement season thank you and how are your preparations going on and what are you presently doing I hope that everyone is properly doing their preparation if you are if you are having your interviews in the next few months I am sure that many of you would be having your internships and your placements in the coming next month or so in the month of July and August okay summer holidays currently I'm doing an internship that's great power I am also currently doing an internship right now okay so yeah uh so uh let me give you a small introduction about myself and then we can start my name is gaurav Kumar shop as I have already written on the screen if you could see and I am presently in my final year at IIT kharagpur but basically I am I finally hasn't started yet it will start from August onwards currently I am doing my summer internship as well at cult fit uh I'm sure do you guys know about this particular company called fit I am doing my software engineering internship there and I am working as a mentor at Geeks for geeks for a very long time and I have had quite an experience in delivering content related to data structures and algorithm okay so if you could have a look at the previous videos at least four Geeks in the month of March February and December I was pretty much active on this channel uh in the practice Channel okay so yeah thank you Ashish yeah learning DSA for placement that is great shubham see uh cover you are in final year yeah I will also be starting my final year very soon okay okay so this is a small introduction about me and uh apart from this code Camp uh like we are on the seventh video of this particular series and uh if you guys remember and if you guys are following uh me or uh if you guys guys are following the channels of weeks for geeks we do bring uh series as such we had uh graph series we had DB series all uh those particular series we keep on bringing for delivering content uh to our audiences okay so uh if you're preparing for your internships you can also check out other courses at G Geeks for geeks we have a CIP course which is basically a complete interview preparation course and we also have a course called the uh Geeks for Geek self-based course and recently we have launched a comparative programming course as well okay so a competitive programming course which is basically the CP uh course if you like to call it in that way so uh that would certainly help you in your online assessments of your internships and placements and in fact I have worked as a problem Setter in those particular courses and I have added my own problems there and I keep on adding that okay so uh this was about the courses to check those out life course uh just have a look at the website I am not really sure about all the live courses going on you can check out at the website and you will get to know okay so yeah so let's continue with uh our uh series that is today is day seventh and if you could have a look at the uh description uh today is basically we are going to study about Advanced sorting algorithms and we will be doing a few problems as well okay so uh I don't think there has to be anything Advanced related to Advanced sorting algorithms uh so uh anyone tell me what do you guys think when I say Advanced sorting algorithm what algorithm comes to your mind Ashish shubham yeah uh I would really appreciate if you guys could make the session a little bit interactive in the chat box uh yeah heaps or merge sort okay so uh you know that quick sort that is also good in fact we have a really really great set of sorting algorithms okay so the simplest one are the insertion shot bubble shot and selection chart right so can anyone tell me the time complexity of these particular sorting algorithm selection insertion and bubble shot what do you think is the time complexity of these algorithms can anyone tell me merge sort is really a good sorting algorithm that's great bubble actually uh if you guys know is that a merge sort is a very common algorithm everyone has heard about it it's an analog n algorithm but the uh important part and the Beautiful part about world sort is that there are various questions of very hard level that can be solved by the concept of merge sort okay you will basically find the concept of merge sort being applied or linked list as well and these are very popular interview questions okay like uh it's a very uh like there is a very very less chance that someone will ask you Radix sort or or some very Advanced or very lesser known sorting algorithm but if they are asking a merge sort it means that they are checking your concept on recursion and how very well you understand the concept of recursion and the merge part of the more sort okay in fact we will be discussing merge sort in great detail today because the third problem that you guys will be doing today is based on merge sort only okay the complexity of these codes are uh bigger of n Square okay so and what exactly is the complexity of merge sort okay yeah so uh do you guys uh have the problem links as well uh the the problem which we will be solving today okay okay in that case let me uh just give you a small brief idea and then we'll continue okay yeah so uh before I move on to solving the questions let me just tell you that this sorting algorithm have a Time complexity of Big O of n square and merge sort is a very popular sorting algorithm which has a Time complexity of n log n uh so uh do you guys know that we have a uh sorting uh we have a predefined function called sort function with C plus plus STL can anyone tell me what is the time complexity of that particular algorithm yeah and login yeah that's great and login in fact n login is one of the best uh time complexity uh shell shot I don't think uh see what I would recommend you is that you understand the basic sorting algorithm in a very very great detail and have a go through about how exactly these algorithm work cell short Radix short count short okay keep shot is very important okay so Heap Sort is important I would recommend uh to learn heapsort because the application of heaps are very important in from interview point of view you can basically create math sheet menu and using priority queues and the implementation of these are important so make sure you learn these but the other sorts like Radix sort count sort uh I don't think these are very uh these are very important because no one will ask you to implement but in fact you may be asked verbally to Define what exactly is Radix shot so you just have an overview okay but do learn all the time complexity okay learn all the time and the space complexity and the and the concept part of okay concept part of these algorithms okay not very in detail about how you can code everything because yes uh just to go through in fact if you Google all the Sorting algorithm you will find a Geeks for geeks article that basically lists down all these sorting algorithms okay and just you can then keep that on revision mode just to devise a few times on a regular basis okay yeah okay so uh let me share the questions now and then we will so the first problem that we are going to do is the do you want me to do the easy problem first or the hard problem first uh in fact let's do the easy problem first because I am I suppose if I start with the hard problem uh many uh audience I will lose the audience out so let's start with the easy problem so I have uh send the link of the first problem in the chat box okay yeah we will be starting with easy problem as usual okay uh I see uh 40 plus students are live with me I would recommend you all to kindly be interactive uh okay so let us read the problem statement first and then we will try to um solve the question so let me share my problem statement screen yeah the name of the problem is uh chocolate distribution problem okay so let's see what exactly does this problem say us I hope everyone can see my screen okay yeah so uh I do have the solution code pasted but there is no point in looking at the solution code because I will be helping you go through the nive approach Brute Force approach and then we will discuss the optimal approach okay so there is really no point in looking at the solution code I will that is just for my explanation I will be explaining you to you at the end okay so but first let's read the problem statement so what exactly does this problem statement say uh in this question uh you have given an array a of positive integers of size n where each value represents the number of chocolates in a packet okay so each packet can have a variable number of chocolates and there are M students a new task is given to distribute these chocolate packets among the M students such that each student gets exactly one packet the difference between maximum number of chocolates uh given to a particular student and the minimum number of chocolate given to a particular student is minimum okay so let's have a look read at the problem State a few examples here so let's say I have got three four one nine fifty six seven nine and twelve okay so I have got eight uh so eight positive integers and eight positive integer is basically representing the number of chocolates eight different packets okay but I'm not supposed to give all the eight packets to all the uh five students because in the question it is mentioned that each student should get exactly one packet okay so it means that I pick up a packet I choose any five packets from these eight packets and I distribute those five packets to these five students exactly one okay now the question is asking us that I have to find a difference between the maximum number of chocolates received by any one particular student and the minimum number of let's receive any one particular student and this difference I have to minimize so when I say I have to minimize this difference it means that I have to choose those particular five packets in such a way such that this particular difference is getting minimized okay so just have a plus one in the chat box if you had uh with me till the uh tell you okay if you have understood the problem statement just do a plus one in the chat box and let me know okay that's great bubble so uh do you guys are getting any kind of ideas in your mind that what exactly will be uh what we will be applying in this question and in fact yes uh that uh we are having uh doing a session on sorting so definitely the idea of sorting will be used okay okay that's great yeah just uh let me know yeah so what ideas are you guys are having uh presently coming up in your mind related to this particular problem certain single pass okay let's see yeah so uh just have a intuition uh that uh in the question it is said that we have to choose any five uh packets out of the eight packets first let us have a look at the constraints okay in the constraint it is said that n is around 10 to the power 5 okay and AI is around 10 to the power 9 but the number value n m is the number of students students is less than n less than or equal to n it means that I will always have the number of students either less than the number of packets or equal to the number of packets okay it doesn't mean that a number of students will be greater than the number of packets in that case I won't be able to distribute the chocolate packets so the constraints make sense now okay I hope this part is clear now we have to think we have to think of an optimal way to to take these particular M packets out of these particular n packets and distribute in such a way such that the maximum minus the minimum is always the minimum okay is always minimum so I hope uh everyone has properly understood this score so let's get back first five major packets distribution so do you think that the first five will always work okay so let me share my iPad screen now and we will move to the understanding part of our solution then uh just a minute first time like any first step I don't think why do you think any first term should work what is your logic we will find difference between each packet and then distribute pack I don't think this is a really good strategy to go about okay so uh let's have a look here something so can anyone tell me okay yeah uh let me just include a new page here okay so uh basically uh we have a our array is of size n and we got M students okay so basically let's say and N is always less than or equal to n so we got n packets and we have to distribute this among M students such that every student gets one single packet right and the difference between the maximum minus minimum we have to minimize this okay so without going into very great detail let us just try to understand uh in a common sense way okay so let's say I've got an example some here as well let's say uh our example initial array is equal to seven three two four nine twelve and fifty six okay and M is equal to 3 okay and uh n is equal to 8 in this case because we have got eight different packets and we have got eight different values right so uh now uh we are asked to distribute among three students okay so uh which of these particular makes sense okay so uh tell me the problem statement is basically something like this that we have to optimally choose M packets out of the given end packets such that the difference is minimum okay so can anyone tell me uh how many subsets I can form basically uh how many different subsets I can form out of of size m subsets of size m out of n packets can anyone tell me Ashish like the question is somewhat similar to this right like you have to choose uh you have to choose M different packets out of these end n given packets and you have to distribute them right and you have to make sure you have to choose optimally so a nice solution what I'm telling you all is that we can have a nice solution okay just the comments and solution what exactly is a common sense solution the common sense solution says that let's forget about everything sorting or anything let's forget the idea is let us just try to have a look into all possible subsets that we can have all possible way we can have five uh we can have M different packets out of the given end packets okay we will try out all possible combination and then we will distribute that those possible combination to all the students try to calculate the maximum minus minimum and this will choose that combination which will give us them anymore okay so live solution is basically try out all possible the nice solution basically says that try out all possible combinations okay of M packets calculate your answer is basically the maximum value minus the minimum value and choose that particular subset which is giving you the minimum answer okay your question is done okay but this will not actually help us in interviews but this is just a common sense way can anyone tell me what exactly is the time complexity of this live approach foreign factorial minus M minus n factorial and uh Pi n factorial so this is the number of ways you can basically choose uh in fact it should be can choose M system it should be in chosen okay you have got n packets and you are choosing M packets out of those n packets okay m is always less than equal to n okay so a slight mistake here this should be n factorial into n minus n factorial divided by n factorial okay so this is how uh yeah just let me know what do you think is the time complexity of the solution of the knife solution what do you think is the time complexity of generating all solutions can anyone tell me M Square uh M Square n m m n no no no no these you see there is a factorial term involved in it how do you think uh generating subsets take a m Square time no no not Times Square time no Deepak no Ashish anyone what do you think is the time complexity of generating all possible subsets if someone is a just gave you a array of size n and it is asking you to generate all possible subsets of size M so how will you uh think a little bit easing n into 2 to the power n n factorial into n okay okay uh you guys are like moving in the correct direction you can even Google these things out you will basically get to learn these as well at the same time as we are learning so uh can anyone tell me let's say uh how many subsets are possible for a array of size and tell me this just uh how many subsets are possible for a array of sizer pratik says you're correct so 2 to the power n is the total number of subsets okay is right also so uh thing now we don't actually need to create all the POS uh all this we don't actually have to generate all possible subsets we just want to generate a subset to size m foreign is happening here is that do we need M subsets or M packets uh M sub we need M fact yeah we basically need M packets but uh the nive approaches basically we generate all possible ways to select M packets and then we choose the best one okay so I'm just asking what will be the time complexity n minus M uh minus one yeah exactly about yeah so let us have a look here uh just a minute let me just uh discuss so let us say that you have a function uh you have an array and the array is 10 20 30 40 and 50. okay now let's say that you want to generate all these uh subsets of size three okay so let's say you take the first element as 10 then you can have 10 20 30 then you can have 10 20 40 then you can have 10 20 50. okay this will one uh this is one of the ways to generate then you have then you put 10 30 and then you put 40 then 10 30 and then 50 then you put uh 10 40 and 50 and then finally you put 20 30 and 40 then 20 30 and 50 then 20 40 and 50 and finally 30 40 and 50. so uh we one two three four five six seven eight nine ten see we generated 10 subsets of size n and if you see one two three four five five c three uh 10 11 12 this is equal to uh 12 right okay okay so I hope this is clear hmm yes right so uh basically 10. so in fact what we are doing here is that we will basically be reading two uh loops and then with the help of us we can have a calculate width to M into n will be our time complexity to just have a generate all possible uh ways right we uh we stand here and then we try to generate the all the subsets starting with 10 then we try to generate all the subsets starting with 20 then we try to generate all the subsets starting with 30 40 and then 50. in fact we will not go to 40 and 50 10 20 and uh 30 will suffice rate so this is the uh naive approach that I was talking about and so yeah but let's not just spend too much time here uh the idea is that the time complexity will be n into M but we don't want that so what we will do basically is that try to sort this array okay why we'll try to sort this array because we want to minimize our difference okay okay so what we will do here is that we will first of all sort our given initial array so uh after we saw this particular initial array this is the array so 2 3 4 7 9 12 and 56 now what we will do we will try to look at uh every possible uh window of size M okay so uh can anyone tell me if I am standing at an index I and I want to go uh what will be the last index such that this sub array is of size m since the value of M is equal to 3 I want to choose all possible sub array of size and consecutive all consecutive sub array of size I'm right because the array is already sorted I have sorted the array and whatever happens the difference between maximum and minimum I will get the optimal answer in this fashion only okay so I hope everyone understood it that why do we need to sort the array because if you sort the array we don't have to basically uh travel across all possible subsets we will just have to make one single pass and we will get our answer okay so uh the way I was asking is that let's say if we have a array okay so let's say we have a input I and we also have something yeah so we have got an input uh index I and uh the next index that will basically cover a sub array of size M will be I plus M minus 1 okay because we want to move we want to include M elements into our sub array and finally what will happen two three four uh yeah so the first sub array is basically two three and four then next sub array will be three four and seven and the next variable before seven and nine the next variable be 7 9 and 12 so the next array will be 9 12 156. eight so finally what will happen basically is that I have generated all possible uh sub arrays in a consecutive fashion now what will I do I will just compute the difference between the maximum and the minimum sliding window we are just sorting it out and just applying our intuition and thinking that how can we get an optimal set of values such that maximum minus minimum is equal to is as minimum as possible across all possible sub arrays got it so if you guys are enjoying this particular session just do a plus one in the chat box we have two more problems to discuss and we will wrap a wrap around in more in one hour or so okay the last problem will be a hard problem the second problem is a minimum problem medium problem and the first problem is an easy problem okay so yes so uh in the first uh sub array that we generated the difference was to then in the next Subway that we generated difference was four then in the next survival the difference was five then the next time the difference is still five and in the final the difference is 56 minus 9 which is definitely a very big number so we don't care about that the we got the minimum value in the first sub array so we will be outputting the value 2 okay Deepak okay generally the last problem is take home okay let's see what happens uh okay I can do something like this I will uh discuss merge sort in a very depth I will discuss another problem called count inversion in a very depth okay in a very depth fashion and you can apply the concept of merge sort and count inversion to solve the last problem okay in that case uh just uh try to implement it okay because the medium problem is also very simple and we can just do it okay then let's let's have a Let's uh see how it goes we will then decide accordingly so let's come back to our uh let's just try to write a simple pseudo code that will basically help us solve this question so the code would looks uh look something like this what we will do basically is that first of all we will sort okay so uh if someone is asking you to sort what will you use will you start writing Mozart code yes Poonam that's great uh really great ideology so just a funny question that if someone is asking you to sort um a given array will you start typing out the merge sort code for example in this question you are given an array and the first step that you have to do is sort so how will you do sort in STL yes of course I don't know if uh if anyone would write a merge sort code so basically let's say you are given an array ARR so we will sort a error.begin comma Ari dot end I'm just writing a pseudo code by the way okay don't just start writing a merge sort code okay I know this is a session for advanced uh sorting algorithm do not write words or code okay just use this after that what we will do we will declare two variables start equal to zero and int n is equal to zero okay because we need to know the starting point and the ending point of our given sub array okay and then what we will do and then um we will declare another variable called let's say a difference okay difference and we will initialize it with Max uh one E9 okay this is basically into max why are we initializing it with intermax because we want to minimize the difference right and every time we try to minimize the difference uh we will try to uh that is the reason we are initialized initially initializing it with into max okay now what we will do we will run a for loop from I is equal to 0 to I is uh how long we will run the follow can anyone tell me can anyone tell me uh till uh what position I am supposed to run the follow exactly uh I was just trying to add some humor okay so I just said that it will be very funny if someone writes a merge sort definitely no one will write I know right definitely no one present in this audience will write okay length minus M uh n minus M plus 1 okay n minus M plus 1 is saying length minus m pratik is saying n minus M plus 1. okay uh let's see what will be formally correct Yeah so basically uh I should iterate up to I should be less than n minus M plus 1 okay why because I will I am only interested in a subset in a sub array of size N I am only interested in a sub array of size n so definitely I should have n minus M plus 1 okay if you just think a little bit you will get to know that why I am doing this this is not a very difficult thing to learn after that what will I do I will calculate the difference difference will be the last index minus the first index so the last index will be I plus M minus 1 and the first index is obviously I okay so this is the difference now we will check whether this particular difference is less than uh okay let me just write M diff okay this particular difference that we calculated is less than M div okay this variable is different and this variable are different so if this particular difference is less than the maximum difference we have it means that we have reached an optimal answer because we are trying to minimize every point right so if you are reaching a particular value and if you are reaching a particular difference which is definitely less than the difference that we have already run so it means that we have Regional optimal answer and we should definitely store that answer so what we will do we will just update MDF is equal to the difference start is equal to I or the value s is equal to I because I want to have the pointer start and the end pointer with me I want to keep those pointer safe because I have to return an answer and then finally we will have n is equal to I plus n minus 1. okay so this is the start and the end and finally what we will do we will return our answer can anyone tell me what will be the answer that we will return I have already pasted the link in the comments of the problem tell me what will be the answer hello Pavan hello pratik hello hello Ashish hello Deepak uh Deepak is saying a s two e plus one um like uh the question is asking us I just have to return the difference okay so the optimal difference so the answer will be the array at end minus the array value at start okay so after I run the entire Loop uh the whatever value I have stored in the start and the end are my optimal starting point and the ending point or the sub array so that is the starting point will be the uh so I just have to make this particular difference uh end minus the start okay a of n minus the start this will a of n will contain the maximum okay so a of n this will contain the maximum value and this will contain the minimum value and Max minus Min is our answer for this okay so I hope everyone understood it can you explain the start is equal to I and N is equal to I plus M minus 1 because in the question we have we are given that we have n different packets but we have only M children and M is less than equal to n so we have to always select a sub array of size M because we have only M students we only want to distribute amongst M student and not more than that okay I hope uh this is this part is clear won't MDF also contain the minimum value won't M diff also contain the minimum value M div is basically uh yes MDF will contain the minimum value okay yes yes you can return that also yes okay so um yeah we can return MDF yes so yeah I just wanted to make you understand that yeah the idea of start and endpoint the star the value start and the value end okay if someone asks you that instead of returning the difference just return me the maximum and the minimum value in the optimal case in that case you have would have to maintain a start at the end pointer okay so that is uh the reason I just kept a two variable it doesn't harm us two but at the end the problem is solved okay so let me just uh share my screen once again of the problem and let's try to solve this okay uh just a minute let me share my problems problem on the screen and then um thank you Deepak thank you Ashish thank you Poonam uh chocolate distribution share so uh yeah so we can also let me just control the so if even if we submit a of n minus a of start the solution should work and even if you submit M uh the solution is in this problem the variable name is MI and the mind okay so if I just write uh mind is in this case Okay the solution will still work okay because both the same thing I hope everyone is everyone enjoyed this particular problem and I please have a plus one in the chat box if you have properly understood this problem we will move to the next problem then okay let's move to the next problem then the next problem is a medium level problem and uh let me just share the tab and the question link as well so yeah okay now uh wants us to wants me to distribute chocolate amongst you all uh I'm not sure how can I do that virtually uh maybe uh you can ping me up on LinkedIn you can just try to connect with your LinkedIn and if by chance uh if you ever get to meet remind me that I have to give you all chocolates okay that's just a joke in fact okay so let's try to have a look here in this question this is a very popular question uh like uh so triplets in this question you are given an array of size n and you're also given an integer X okay now you have to basically just return yes or no okay you don't have to return anything else just return yes or no if you are able to find three values in the array such that the sum of those three values is equal to X okay if you can find this written yes if not just written note nothing else straight away so what can you imagine what can you think uh it's a good the problem statement is just a one line statement nothing very fancy about this problem statement so tell me how will you solve this question in the question if you see in the example we have n is equal to 6 and X is equal to 13 and the array size is equal to 1 4 45 6 10 and 8. so output is equal to 1 because yes means you can definitely find a triplet uh one four and eight such that this array sums up to 13 okay so in that case in this case the answer would be again one and in in fact if it happened that you have got an array you are unable to find it so you will basically return though okay return false okay so just tell me what do you think like what are the first things that you are getting yes this is the famous threesome problem a lead code uh in fact uh this is the famous problem is called treason right like there are very different variations of this problem as well in you can also be asked that you have to return the three you have to return that whether you are able to form such that a sum is equal to zero or you in fact you have to return the total number of triplets total number of unique triplets such that the sum is equal to zero or sum is equal to X uh compared with a given sum after finding all subset will compare with given sum okay you can do that but but since uh that will be not very optimal uh in fact you have to try out some other possibilities also you can use the last problem approach and in every window of size three we add all the elements and check if it is equal to Target or not okay okay but uh you are thinking in a good direction but that will not actually lead us to the answer okay uh just let us have a look and look into the constraints okay so in the chocolate distribution problem the time complexity of the problem was n log n because we used uh VL login to sort the algorithm okay in triplet sum problem the constraints allows us uh the constraints are up to 10 to the path three and we can we have we are allowed a Time complexity of n Square okay so we have to basically find a triplet such that a sum is equal to 10 okay now uh if you are just looking in this fashion for example if you're just comparing you sort the array and you take the first three elements and you see that whether if it is equal to the given sum or not if not you move to the next three element this is a very wrong approach this will not work okay because uh like if the first three elements are not working then and you take the next three consecutive elements it may or may not work but we do not know but there are many other ways that you are leaving out there are many other possibilities there are many other possibility subsets which are leaving out okay yeah we have to find the sum of three numbers such that uh basically we have to find those three optimal values size that sum is equal to X but if we cannot just uh use the concept of the previous problem the previous problem was a very easy problem just we cannot iterate over all possible sub arrays of size three so you take the first three numbers and the next three numbers we cannot do like that okay because we can do like that it may give us the answer but there are many other values which we are missing out which can actually give us the answer okay in the previous problem we have to find the we have to minimize the difference between the max minus Min so in that question it made sense to actually uh use uh in that particular approach but this doesn't ask us so okay optimal solution we can fix one variable and then and for the other variables of B and C we can use two pointer approach and see if the sum is equal Target yes exactly this is right in front of you the code yeah this is exactly what we are doing can anyone tell me a better solution um like uh brute force sort and for every I and J uh yeah we can do that can anyone tell me an approach that uses a map if I if let's say if I'm your interviewer and I'm asking you a question that do this question but do not use two pointer do a user map I want to use map how you will do it can anyone tell me an approach of using map in that case there will be an extra time complexity uh hash said uh yes tell me the approach tell me the concept how we'll solve using map can be done by recursion um well may or may not be done but why do you want to apply recursion when things can be done without recursion ah yes we will be using hash Maps but tell me a concept okay uh let me just share my iPad screen and then we will discuss various ways we can solve this question Okay so in fact I will be discussing a live approach I will be discussing a better approach and an optimal approach okay so and we will be submitting the optimal approach uh oh sorry I just uh reshared the screen give me a minute let me share my other screen [Music] make each element as key and remaining pair as value yes exactly rishabh this is the correct approach and then we will try to find out that whether a particular value is present in the hash slab hash map or not okay saw two pointers um let's see sorting and two pointers I have already got a lot of value a lot of comments related to that I'll look for third in the hash map yes uh pratik Works uh uh third in the hash web so prati can you tell me the time complexity of your approach Fulham says that from the given sum subtract one element and then find the two vary by remaining array yes exactly we will be doing this this is the optimal approach so uh pratik tell me that uh how what will be the time complexity of uh the comments that you just wrote okay is writing so let's have a look into the Brute Force approach so uh like let's say that we are uh we are in class 9th or tenth and we do not know about any optimization algorithm we're just given this problem and we are asked to uh write a code right okay so uh the question says that we are given an array and we have to find three elements so what we can do basically is that we can run three Loops okay so the basic idea is we let's run three Loops okay uh what we will do we will run a for Loop for I will another uh we will list another folder for J we'll address another for Loop K so basically we will go across all three values okay we will iterate across all the three values and we will check that if a of I plus a of J plus a of K is equal to equal to uh given value X or not if it is equal to equal to X in that case uh we will just return uh true okay we will just return okay so the time complexity of this approach will be bigger of N2 and we don't want that because we uh because n cube is very very uh expensive process okay so and the question says that we have to do it in uh because of L Square the expected time complexity okay so we don't go on there this is a this is a bad approach okay so let's say someone's someone in the comments said pratik pratik said that what we can do basically is that um we uh take a element okay so pratik where is pratik's comment let me just uh have a look sort then take two pointers look for the third in the hash map yeah this is a good idea so what we can basically do is that we'll try to sort the element okay okay so the idea is that once we sort the element uh sorting an element in ascending order basically gives us a smaller element uh in the beginning and the bigger elements and after that okay so what we will do basically is that we sort our array after that what we will do uh let's say we take the first element okay and what we do uh let's say um let me just uh let me just Okay so uh let me just have a look into the uh one two three okay so uh this is the example problem one four forty five six ten and eight okay if I'm sorting this particular array the array will become 1 4 6 8 10 and 45. okay so this is the array now so it becomes 1 4 6 8 10 and 45 and then finally what will happen so basically let's say I take the first element okay uh let me just name the variables a comma B comma C I take the first element a is equal to one okay now when I take a is equal to one um and now I need to find the value uh my target sum is basically uh let's say 13 x is equal to 13. it is already given in the question this is the example from the question so X is equal to 13 okay now uh what what do we need so uh let me just say I already have one so I subtract 13 from 1 I get 12. now I have to find two numbers such that the value is equal to 12 okay now what I do I take two pointers approach how yes exactly we'll be using sorting algorithms this exactly we'll be using sorting algorithms and then definitely why we uh okay so I take the value 12 after that what will I do basically is that um so uh now what will I do I will just take a pointer to pointer I will put on 4 and then what will I do I will basically subtract 4 so 12 minus 4 will be 8 so once I put up 8 here basically then what will I do I will try to find a value so what will I do I will try to find uh whether I have 8 present in my array or not using a hash mark okay okay so after that what will I do uh I will store all the values in the hash map whether it is present or not the or just the occurrence is right and then we will try to find out whether it is present in my array or not with the help of a hash mark if it is present I will just return here yes if not I will be written false in this the time complexity will be N squared login because because we are just using a map right okay so this is just uh using the concept of sorting as well and idea of map as well okay but we can actually uh optimize over this and prevent the use of hashmap by using another concept okay the concept of two pointers okay so let's have a look into the concept of two pointers first can anyone just summarize me the concept of two pointers okay so yeah so let's have a look here uh just a minute yeah so what we will basically do is that uh let's try to uh first of all we will sort the array right we sort our array then we'll try to run a loop okay our Loop will start from I equal to 0 to I is less than n minus 2 because uh we need to at least find three elements okay so uh let's say what do we do we will take two pointers one at uh so one at the ith index and the other at the last index okay so uh this pointer will be at an index I plus 1 and the uh R pointer will be at an index n minus 1 okay so this is at the I plus 1n position wherever I am I am just taking a next position and this is at the last position so basically if this is our array this is my I I am putting one pointer here and another pointer here so I am trying to find a optimal value in this particular part by keeping this particular part fixed so what I'm doing I am fixing my ith position and after that I am iterating on I plus 1 to n minus 1. using two pointers I am trying to find two optimal values such that the sum is equal to X okay now how we will find that you optimal values we have to basically use an intuition use an idea the idea is something like that let's say I have my I here I plus 1 here in fact let me write L okay L here and R here right we will be iterating across these two pointers these are my two pointers two pointers basically help us finding two optimal values right these are my two pointers now I have to do something like this I plus L plus r is equal to X okay I have to do something like this L plus r is equal to x i is fixed okay but this L and R are not fixed L and R are variables we can basically change them now we have to use an idea how we can change them let's say I plus L plus r is equal to equal to X this is the first condition if let's say if I am just I just put a value I put an iul put a value R and I'm able to find it as equal to equal to X so we have hit the jackpot and we will just return true but if not there can be two conditions the first condition is that I plus L plus r is less than x if it is less than x what does this mean can anyone tell me if it is less than x tell me if it is less than x what exactly does this mean it means that I have to basically increase either my l or my R the values present at L or R such that it becomes equal to X I want to add few values okay I want to just increase the value okay so in that case what will I do I will do an L Plus because c l is present here R is present at the end I cannot increment R because it will overflow I can increment L to the right side why because my array is sorted I know if I increment L just by one value I will get a bigger value I will get a bigger value and it may be possible that once I am incrementing the value of L I make it a value such that I plus L plus r is equal to equal to X okay listen to this very carefully that if we are able to somehow get a value I plus L plus r is equal to equal to X in that case we can just say uh we can we will just be returning got it so if it is equal to equal to if it is less than x we will just uh do L plus plus else we will do R minus minus else means if it is greater than x if it is greater than x it means that I must reduce one of the values of Ln R okay I cannot reduce L uh or in fact I cannot reduce L because if I just reduce cell it means that I have already built that place so instead what can I do I will reduce R because initially I have taken I to the extreme left and R uh L to the extreme left and R to be extreme right okay and this is my height I is always fixed and I am iterating my two pointers on this okay if I have got a value I plus L plus r as less than x I will try to increment I so as to get a better value such that the sum becomes equal to X if not if I have got a bigger value I have exceeded my value I will try to decrease RN okay so this is the concept I hope everyone understood this is Shahid so just have a plus one in the chat box if you understood the intuition behind the problem okay now what we can do basically uh try to write a small pseudocode in fact doesn't matter because this is already a pseudo code itself okay we can then directly jump to submitting this particular problem and okay so tripletsm so this is a problem okay I hope everyone can see my screen I would that's great um that's great that's great okay so this is a very simple question like this is the code is just a few lines if you just count the number of lines one two three four five six seven eight like around 10 lines four and the complexity is n Square okay we would be making it Complicated by using hash map okay because the complexity would be n Square login but just by an intuition that we will increase the pointer if we have a if we we will increase the left pointer if you have a lesser value than x you will increase the r pointer if we will decrease the r pointer if we have a greater value than x this is just a simple intuition behind following this question okay so let me just go and have drink some water meanwhile you can also take a two minutes break just have entering some water and then you will continue with the third problem okay so hi I'm back yes uh Richard you can use a binary search in the Inner Loop yeah so uh let us uh but uh the the but the point is that we are trying to do a sorting algorithm questions so uh we will we would be like binary search is uh we will be trying to do that in the next few weeks itself right so that is the reason uh we did I did not actually uh um go there yeah okay so let's have a look into merge sort now uh let me just submit this problem and see whether it is correct or not now we come to the hardest part of the of this particular session uh it is basically implementing merge sort okay so I will show you the question and then uh you can see that all the test cases have passed so therefore this question is correct so now uh we this let's come to the hardest part of the hardest question uh let me share this tab so yeah so this is also a very simple question just a one line problem statement but this is actually tagged as hard and in fact why it is hard because we have to actually write and Implement a merge sort logic to solve this question in fact this question can be solved in a very very few lines if we just try to apply the concept of binary search on this question okay if you know the functions lower bound upper bound and what exactly does this function does we can solve this question in very few days like seven or eight lines in fact we can solve this question in two lines also by using uh data structure that uh not very commonly used but this but in this particular session we will be implementing one more sort algorithm okay so yeah uh I will just uh share it to you just a minute so in this question uh we are given an array uh of n positive integers and we have to count the number of smaller elements on the right side of each particular array right so basically it says that let's say you have got an array 12 1 2 3 0 11 and 4. now you have to count the number of elements which are smaller than 12 and and are present on the right side of 12 in the given array so if you see all the elements on the right side of 12 are less than 12 so there are six elements so the uh first value of the output array is 6. for the value 1 you see that there are there is only one element that is co which is basically present and it uh which is basically lesser than the value one and it is present on the right side okay and uh let's say if you have to for the value 2 it is one for the value three uh it is one again but for the value 0 it is 0 because 0 is the smallest element and there are no element which are lesser than 0 present on the right side so and so on the question goes something like this right so um what I am thinking about is that since we have a very diverse set of audience here I will be discussing more sort in detail and I will be discussing a similar problem called count inversions because these are very important problems and then I will give this problem as a take home problem you apply those two concepts and solve these questions okay meanwhile for the for the students who are much intelligent here can you all tell me a data structure that can actually solve this question in two or three lines can anyone tell me let's see who can a data structure a hint this is a very rare this is a data structure actively used in comparative programming if you do code forces you will know this data structure but you don't find that this data structure in C plus plus STL gfg platform I'm not sure like um you can sort this question uh but the you can use sorting algorithm definitely to sort this question but actually um uh the idea that I wanted to discuss in this session for previous problem okay can you share the problem link yes of course I can share the problem in just a minute there are various ways you can solve this question without application of merge sort but I want to discuss merge sort in this session because the name of the session is Advanced sorting algorithm and I prepared a few content for merge sort okay and I will be discussing a very similar problem called Counting versions which is very uh like if you are given giving an interview and uh in an interview uh let's say if you're asked to uh give given the question account inversions in that question you know the integral would expect you to write the code for merge sort because writing a code for more sort actually test you uh your merging logic your recursion logic and the way you actually uh implement the merger okay it tells you that how in-depth you can actually uh know your Concepts okay so back to my question can anyone tell me a data structure that will actually help me solve this question in a very quick few lines okay I am not very proficient so yeah whatever and C plus plus do let me know okay so this is a problem statement but we will try to do a similar problem uh called merge sort okay so let us first understand words start first and then we will try to implement this okay so uh to my answer does anyone know about policy based data structure evds also called pvds and there is a data structure called audit set if you use this data structure you can solve this question in two lines okay so this is not present in STL it is present in pbds policy base data structure which is basically an implementation of red black curries so this is a bit advanced stuff but let's study uh Mozart here just a minute let me share my iPad screen and then we will continue okay so let's see yeah so let's have a look into merge sortner okay so this particular monster algorithm is also called divide and merge algorithm okay and the time complexity for solving this algorithm is n log n okay now let's say we are given an array the size of our array is three uh this is a particular array so what we basically do in most sort is that try to recursively uh okay Power let me just type it out for you it is called policy based data structure okay uh instead of typing let me just write it on my screen it is called um policy based data structure and we will be implementing order set with the help of audit set if you just uh Google this up you will get to know it it is very actively used in CP if you try to solve food forces contest you will get to know about this particular data structure okay so this was just for uh not a point not not a point of our discussion right now and I guess someone asked my LinkedIn profile let me just share it to you all and then we can proceed okay yeah I guess uh I just I actually pasted my LinkedIn um in the comments I think you guys can see it uh Poonam uh priority queue like why is this flickering I'm not sure okay yeah there was a slight problem with my uh casting of my iPad screen but I guess this is working right now is that so can you all see my screen I don't think so um okay it's blank let me just reshare it thank you I think I hope everyone can see right now can you all can see the I think it is visible okay let's continue now I've also pasted my uh LinkedIn uh the particular link okay so you can just have a if you would like to connect with me then that would be really great okay so let's continue yeah so this Pawan was asking for the um ordered set thing okay so this is basically a policy based data structure and it's kind of a kind of advanced so let's not go into there okay so let's have a look into the idea of more sortner so merge and merge sort is basically divided merge algorithm and the complexity is basically n log n okay okay so complexity is n logo so what we basically do we are let's say given a particular array so let's say we are given this particular array three one two four one five two six and four okay so what we do we try to split this particular array into two parts this is the first part it's the second part now recursion so basically we are splitting the left part first so what will happen in recursion when we split the left first it goes recursively calls for the next left part so this will be again split three one two four and one this will again be split into three and one and then two in the left part will be split into three and then one okay so this is how it is splitting okay the left part first then the right part okay so now recursion works so when the size of the array becomes one like we can keep on continuous splitting but when the size of the array becomes one in that case we can no longer split okay so what we will do we will try to merge them back up so we start merging them but there is a condition of merge we will just not simply merge it back the way we split it we will merge it back in a sorted fashion okay so when I'm merging three and one back together of three and one I will put one and three together because one and three is in solid fashion this is how it works now I have one three and then I have got two so these two are sorted arrays now what will I do put it as together I have to make sure when I have to make sure such that uh I have to make sure that the arrays are basically sorted so every two sorted that order the merge logic should be in such a way such that it takes two sorted assorted arrays and sort merges it back in sorted fashion so this will be one two and three we will discuss a merge logic as well so how we are exactly merging more we are basically merging we are standing on let's say one and then we are standing out to we are comparing that whether one is less than two or not if one is less than two we put one into our merge diary then we move to three then we check whether three is less than two or not three is greater than two so instead of three we'll put two because whatever number is less we will put first and whatever number is greater we will put a second so two uh so this particular array is done now we are left with three we'll put a three so this is the merge logic okay now when will you merge okay the question is when will you merge when both left half and the right half is sorted we will try to merge so the idea is that we keep on merging smaller elements and make it sorted so whenever the left part and the right part is sorted we will merge it back together and create a new sorted array so this is the entire logic of Mozart okay so uh we will try to merge let's try to implement the merge logic right so what exactly is happening in merge sort so let's say uh we have got uh basically two pointers right so let's say uh we got a particular array here we got a particular array here this is array this is Arab okay this is a sorted array and this is also a sorted array so what I'm doing here is that I am putting two pointers here okay this pointer will be let's say I and this point that will be sha and comparing the two values if the values uh if let's say I is less than J I will put the value this particular value here and then move the pointer here again I will do the same thing for these two values whichever will be less I will put it and increment the pointer okay so this is how the merge logic will work and the complexity for merge logic will be o of N1 plus N2 because I am just iterating across both the sorted areas at once okay so let's have a look into the merge sort logic so how exactly are we going to look into the more sort logic let's say uh we take a smaller array for better understanding of the question this is our array so the array elements are three to four one and three there I have already mentioned the indexes also indices we will initially have a low value low will be equal to equal to will also have a high value high will be equal to the last value of the index okay which is equal to 4. we'll try to implement we will pass our given array will pass the low value will pass the high value and then what we will do as I initially said merge sort is a divide and merge algorithm so what we will do we will try to find the middle value because we want to split it we want to divide the array okay so middle value will be low plus I by 2 okay so I hope everyone is with me okay now what we will do we have segregated our merge sort into two parts left part and the right part number what we will do we will send recursively called the merge sort function once again with two indices the first one will be low and the next one will be mid why because if this is low this is high low plus High by 2 is actually giving moment so 0 plus 4 by 2 is equal to 2 so this particular value is made so I am taking the first three numbers in one part and making the next two numbers in the different part so three one four and one and three these are the two splits that I have made and this particular split is receiving three one four and this particular split is receiving one and three okay so low and weight low basically contains three uh the first index which basically contains the index of three to four okay so three to four and one and three okay now what I am doing I am recursively calling the function to split the array into two parts now this will recursively call to split the array into three to four okay so if I just write a logic here what will happen 0 and 4 is the indices it will split in into the next split it will again split into zero and one and finally what will happen zero comma zero and one comma 1 the size of this plate become once so the base case it brings me to the base case now so the base case of this particular uh recursion will be when the size becomes one so what happens when the size become one when the size is becoming one low is equal to equal to high or in fact we can write low is greater than equal to I okay because in that case the size is becoming one right so we will just return it means that the size has become one now it's time to merge the two arrays okay whenever size become once uh we can no longer split we will merge it back so at this point we got a size is equal to one now what will happen we have written a merge logic also this merge logic is taking two three parameters the first is to do the mid and the high it is taking the starting index the middle index and the high index so basically I have the indices of the positions I want to merge so I want to merge from low to mid and from mid plus 1 to high okay so these are the two positions from low to mid and from mid plus 1 to 5 so that is the reason I have already from low to mid and from mid plus 1 to high these are sorted love I hope everyone knows here knows about lower source so this is a thin explanation okay now what will happen uh we merge this to arrays so let's have a look into the uh I have already discussed the question so if this is our two sorted arrays what we will do we will try to merge it the first point that will do this pointer will be made is that third point that will be mid plus one and final pointer will be high so what we will do we'll create a temporary array the first step is to create temporary array then we will declare two variables the first will be left left will be equal to Loop and right will be equal to Mid plus one why because we want to have two point as I just discussed after that what we will do we'll run a while now while loop uh basically left will be less than equal to Mid and high will be right will be less than equal to high okay now what will happen I will just uh try to check whether the left value is less than or equal to the right value if it is I will add it in my temporary array then dual f plus plus if not I will add it in the right value and do a write plus same thing will go after I am done with this I will just check that whether there are any leftover elements in either of the arrays okay if there are any leftover element so if if we have leftover element in left part then we will add those if we have leftover element in the right part we will add those okay and now finally what we will have our temporary array will put it back in the original array okay because I have actually merged these two parts okay so this is the idea of more sort and the complexity is basically n log so I hope everyone understood it let me just share my um stop the screen sharing show it show a merge sort code to you and then we will continue [Music] um yeah yes I will accept your connection request okay so yeah so can I please have a plus one in the chat box if you have a comfortable with the most short code let me know okay yeah that's great so uh what is happening here is that um so this is exactly the conditions that we have but let's just this is the logic we are dividing into middle we are then sorting the first part sorting the next part and then merging it back together this is the more sort logic right so this will certain ascending order that is a summit okay now we'll do a similar problem called count inversions okay now using the uh Concepts learned in merge sort using the concept learned in merge sort and the concepts learned in content version we will be able to solve that hard problem okay can you explain the non-recursion algorithm of merge sort um yes I can explain but uh that's not in the agenda today um I would recommend you to have uh just read the Geeks for each article for the co-host we do have a non-recursive algorithm but understanding the recursion algorithm is actually quite helpful okay in fact uh now let's uh let's say I you are given this particular question count inversions okay so in this question this is a very famous problem and it is very frequently Asked okay foreign [Music] but let's have a look into this question it says that we have to count the number of inversions inversions basically means that you're given an array and you have to basically count the number of uh number of pairs I comma J such that EFI is greater than a of J for all possible ing so the I is less than G okay so this is the inversion okay in fact if I say you that if you make a one line change in the merge sort comment a merge sort code we will be able to solve this question we have to just count the number of inversions okay yes exactly you're correct modify merge to get the number of times the element from the second sub array is smaller than the first summary okay okay so this is the question let me just give you the link and then I will back share my iPad screen and then you're correct so what exactly is happening is that we have written a machine logic rate so what we are comparing whether the element on the left part is greater than the right part number if it is greater what we are doing we are just showing the smaller part but let's say whenever an element is greater whenever an element in the left part is greater than the element in the right part it means that that is an inversion right that is a valid inversion so what will I do I will count all the element after that because since both the arrays are sorted see all the elements after the element in the left part will be basically a valid conversion for the element in the right part okay so let me explain it to you uh in the form of in with the help in my iPad and in that case you will get to understand it better hmm so count inversion is basically uh you have to find the number of pairs okay so let's say uh you've got two sorted arrays uh this is a sorted array and this is sorted array okay so let's say you are standing on three and you're standing on two now you see that 3 is greater than 2. so it means that 3 is a 3 comma 2 is a valid uh inversion rate so what you will do you will do a plus one in your answer but doing a plus one in the answer won't help because the two are already spotted so what what happens is that all the numbers after three I repeat all the numbers after three are also valid inversion for the number two so instead of adding plus one I will add all the numbers after three so three five six which is basically plus three instead of plus one I will add plus three okay because uh Brute Force way of finding the number of inversion is something like this is standard to uh go across all the values and see if it is less than two or not the standard three we go across all the values if it and try to find all the values lesser than three the standard five go across all the values we stand at six try to find all the values lesser than six and then increment the count okay so this will will basically uh take an N Square approach but since both the arrays are already sorted in merge sort when we are merging them back together we can just count the number of inversion at that particular step really so what we will do will declare a global variable count and then what we will do we will just do count plus equal to Mid minus left plus 1 why mid minus left plus 1 because this particular is low this particular is made and mid and this is left so mid minus left Plus One will give you all the numbers after left and in that particular array so what we will just write this particular line of code it will help us count of all the smaller number on the right side okay so this is the only modification that we have to make such that we get we can count the number of inversions okay so I hope uh you guys understood this question it okay so let me just share my screen so this is account inversion code and if you see I only made one particular change in this particular code and it is equal to this I declared a value called long long count and uh in this I just made this particular change whenever the left part is greater than the right part it is a valid inversion and I'm just counting all the count that is possible from that particular value so let's Summit this problem so now you have to basically utilize these two concepts to solve the question on count smaller elements okay so can anyone here tell me how exactly are we going to utilize these Concepts to solve this question anyone pratik ashutosh Pawan Poonam nitesh arushi pratik yeah so uh the idea is very simple because in this question you have to basically return a particular array that will contain all the number of all the elements which are basically on the right side and it is smaller so it basically means that some way you are basically storing all the inversion itself okay so if you just add all the elements six plus one plus one plus one plus one it is basically giving you the count of inversion the sum of this array whatever you are returning in this count smaller elements is basically the total number of inversions when we array so instead of just counting doing a count plus equal to you store it in a particular array called count okay and try to implement this logic and I'm sure everyone can do that I will share it to you um just a minute let me just open that question uh okay uh in fact if we just have a look into the editorial code I think the editorial code the person who has actually authored this question has made it in such a fashion okay so if you just have a look into the editorial code itself it's uh written in order set because uh I think the problem said that the person who actually said this problem on the geek's colonies did not actually uh wrote a verse not logic in the back end he actually wrote the ordered set logic okay uh yeah in fact uh if you see other people's submission for this problem you will be finding that many people are using uh lower bound upper bound these are binary search techniques but actually I wanted to discuss how we will apply more sort okay because sometimes in interview you know uh writing a very short code will not get you actually the interviewer expects you to write very optimized well structured clean code and it he or she will mention you that if you can do it in l login then I do a more sort logic because he wants to know that your concept of merge what is correct okay but if you're doing a contest yeah you don't want to write a merge sort you will use audit set or you will use a lower model up account function to get quickly to the answer okay so the driver code is already uh uh these merge sort question yeah uh it is not an algorithm it is a policy based data structure okay that is very commonly used on code forces Conquest okay you don't have to learn this doesn't actually help in solving lead code or internship questions but it will help you solve uh code forces contest very well okay so I am submitting this problem and if I have already given the link of this question uh in the uh you can have a go and have a look at my submission for this particular merge sort code and you can try to understand it how basically uh the two concepts of merge sort and Counting then versions are being applied here okay I hope everyone enjoyed this session we started with around 50 plus students really at my session and then we have presently not 20 students I hope everyone is enjoying this particular Series today is the seventh day we have 14 more days to go and uh from Tomorrow onward Siddhartha and yes we will be continuing with this particular series and if I get a chance I will once again come back okay and once again let me just uh introduce myself my name is gaurav kumarshan and I will be in my final year very soon at IIT kharagpur do hit me up on LinkedIn if you would like to talk to me okay okay amazing mazaga that's great that's really great today is actually uh Friday night and I really enjoyed spending uh two hours in two or three hours I prepared for some content here as well before and right now in fact I am in at my office okay so if you uh right now I'm streaming it for me from my office I was actually two days of working days so uh after work I actually went across and uh saw the questions and prepared a few content and right now I'm just read it okay yeah in fact this is equal to office okay thank you ashutosh yeah see you yeah a really really great night and do enjoy your weekends okay and definitely turn up for tomorrow's session as well should I learn flutter sir please reply why would you learn shuttle if you if you are interested in app development then you should learn flutter but if you want to get into a company then you should learn DSA and competitive programming okay development doesn't really actually help in landing a job but DSL CP will okay that is great okay then bye have a great night have a great weekend enjoy