CodeCamp Day 17 | Mastering Greedy Algorithms

Key Takeaways

foreign [Music] so if my voice is clearly audible as well as I'm properly visible then write down plus one in the chat box okay is my okay I got the confirmation thank you thank you I'll be sure so are you guys excited for today's session hi Devils okay so whatever your name is so are you guys excited for today's session and how many of you have been following this entire series hi Ram Chandra so how many of you have been following the entire series of code camp so basically this is the day 17 and in today's session I'll be discussing about greedy algorithms okay so we'll be understanding what actually the entire Paradigm is hi mithilesh hi I am new to this okay okay Abby is following okay and devil is also following okay so basically in today's session I'll be giving you a broad idea so I'll be giving you such a technique that if you follow this technique and whichever question you encounter that will be under greedy Paradigm you'll be actually able to at least get a Brute Force approach or you will be able to let's say if that question was asked to you in the interview or somewhere else right you will be at least able to give them a solution that might partially work or that can be the Brute Force approach okay okay you can see oh yes I'm excited I joined around 6 PM but I'm familiar with the basic concept okay great okay so without any delay we'll start within a few minutes like uh two to three minutes more till then do you guys have any kind of doubt do you want me to like do you want to ask any time any kind of questions regarding career or regarding any kind of DS apart you can write down in the chat box will be beginning at eight zero five till then but let's wait for everyone so that everyone can join and take the best out of this session sir uh is this will be easy to join session now I am will it be understandable okay yeah I'll try my best if you are new to uh this session or new to DS I'll try my best that I'll be explaining uh such that everyone will get the concept and will be able to understand the concept okay I'm unable to recall my concept that I have learned okay so uh Gupta says I am unable to recall my concept that I have learned so basically what I used to follow when I was in college I Was preparing I used to note down the concept I used to note down the algorithms which are standard algorithms right and you can constantly keep on revising after like a week or something like that so revising the concept revising the algorithms helps out a lot okay good evening shubham good evening okay so let's start so basically the first part which I'll be covering will be giving you a basic idea about greedy algorithms how you can think about achieving the workable solution for any of the question that comes under greedy paradigm so just let me share this screen I hope my screen is visible to everyone okay I think it's visible okay so first of all what do you guys understand by the term greedy okay so let's start with the basic thing what do you understand by the term greedy it's very obvious you might have heard about this word very uh frequently right everyone knows the meaning of being greedy and we never want to be greedy so greedy algorithms we know the general word greedy greedy that means Being Greedy means like you want something so badly that you can achieve it like uh anyhow you want that thing and you will be greedy like you will not see the benefits or the uh thing which you are doing that might affect other people right you will you want that thing you will achieve it right no matter how whatever path you take so basically greedy algorithm is something like that like if let's say this is your problem statement this is your question and here is the path that you need to follow in order to achieve the answer okay so basically you can consider this as the problem statement and this is your solution or the algorithm that will give you the required answer optimal option if any step is part of the overall optimal solution yes greedy means selfish yes exactly yes you are exactly correct so basically uh if I want if I am giving you a problem State when I ask you to find out the solution for it so you will achieve a path you will follow a path that works greedily that works greedily means that let's say the question says that you have to maximize something right you have to maximize The Profit you have to minimize the uh let's say minimize the cost right basically the question wants you to maximize or minimize something so how will you achieve it so basically let's say if the final goal is to maximize The Profit then what you will be doing at each and every point at each and every uh certain point or sub problem you will try to maximize the output you will try to maximize the output you will figure out some kind of technique or you will figure out some kind of repeated thing that needs to be done at each and every problem statement the smaller sub problems so problem once a problem two sub problem three and sub problem fourth if you focus on this thing achieving the maximum or minimum at each and every sub problem and eventually you will get the finalized maximum or minimized answer for your problem statement that is how greedy algorithm works so now I hope this part was clear to everyone can I know was this part clear what actually means greedy algorithms a plus one in the chat box let's skip the session very much interactive so that everyone will enjoy okay and in between you can shortly put down your doubts I'll uh simultaneously straight down the chat box okay was it clear yes or no in the chat box okay I hope it was clear to everyone so now let's say how to find out the solution for greedy algorithms okay uh let's say there was a some kind of problem given to you and you were asked to find out the solution and you somehow figured out that greedy algorithmic way can be applied over here so basically what you can do this is your problem statement one I'm not taking any kind of uh question over here in order to explain this thing so basically let's say this is your problem one and you have to find out the solution for this problem so what you can do you will be given input test cases right input test case one input test case two will be given to you so you can read down the input test case and you will be able to figure out that somehow I can understand this input test case one and I have figured out that some kind of technique that is A1 technique can be applied on this input test case one and I'll be getting the solution one for it similarly while reading now reading out the input test case number two you figured out okay so something I was missing in the uh approach number one that I was applicable on input test case one now I have understood that this point is also very much important okay so I figured out a corner test case that this needs to be handled and I figured out that after algorithmic one I came to know that some of the steps were missing and now I am able to understand that this A2 might work for the other problem so what you can do you got the solution number two now what you can do in order to find out the uh answer or the algorithm that will work for this problem you can try out different different test cases okay now just give me a minute I was saying that you tried input test case number one and you figured out an algorithm that will give you a finalist solution then you figured out input test case number two had a corner kind of thing and I came to know that I need to add some some of the points to my algorithm number one right and I came at the solution number two now how to finalize that this is my algorithm and this is going to work on each and every test case so for that what you need to do you need to figure out different different test cases based on the constraints and based on the problem statements try to at least figure out at least five test cases okay and now what you can do you can apply this algorithm A2 on the test case number one and you will be able to understand okay I can apply algorithm A2 and I'm getting a correct answer then you can try out the same thing for the test case number two and you figured out a completely new approach is applicable over here so is your algorithm algorithm number two not at all worthy no it is possible that this can be a corner test case and you simply need an if else condition to handle this this kind of test case then you will apply the same algorithm for now you have two different tools A2 and for solving the test case number two you figured out there was A3 algorithm which was only working for test case number three I mean the test case number two now A2 you tried out a to one test case number three and it is working perfectly fine you did the same thing with T4 and you did the same thing with T5 so if you will try to solve the test cases more and more in terms of greedy questions you will be able to figure out similarities in algorithm and those similarity will help you to finalize a working algorithm that will be applicable and that will be working on each and every test cases of that problem so basically in Greedy algorithms if you want to find the solution try as many as test cases you can trying out test cases will be helping you a lot in terms of greedy algorithms is it clear try out as many test cases possible as many test cases you can this is the key to solve questions on greedy algorithms okay after the session focus on this point and you can take an easy question if you have if you are just a beginner you can try out an easy question and try out as many test cases you can and mark my word you will be able to figure out the solution on your own I am not saying that it will be applicable for hard questions as well for hard questions you need some prior knowledge about standard problems and standard problems are very much important for learning DSA each and every topic has a set of standard problems and you should verify you should learn about standard problems because each and every standard problem will give you different kind of techniques to look at the data structure and like it will give you a different perspective uh for the data structure for that algorithm okay so standard problems are the must for each and every topic of data structures and alcohol terms okay is it clear yes or no in the chat box is this part clear to everyone any doubt till now uh is there a structural way to figure if degree solution will work for a particular problem like for DP we look for overlapping sub problems and optimal substructure no greedy does not have that kind of thing that is the reason you need to try out as many test cases you can okay a structured way is this thing trying out as many greedies I believe greedy is the easiest Paradigm which you can learn very fast which you can learn very easily and in Greedy as well everything revolves around standard problems only okay each and every new question will revolve around standard problems just like dynamic programming each and every question revolves around set of standard questions in DP over here as well you will figure out that okay A variation of standard problem is being asked to me confirmation from everyone I got a confirmation from only Poonam was it wasn't it clear to everyone okay pratik I hope I was able to answer your question okay so now let's start with the first question of our session and as we know that the last question is going to be your homework question and I'll be discussing the basic understanding of the problem and I'll be discussing what you can do in order to achieve the solution of it okay so the first question so I'll be let me share the link of this in the chat box and I want everyone I'll be giving you few of the few minutes to try to understand the problem statement and after understanding problem instrument just write down over here mention it that I have read the problem statement okay two to three minutes for understanding the problem statement here is the question and the name of the question is minimum sum of absolute differences of pairs try to understand what this question is trying to say I've shared the link in the chat box so over here you are given like you can read out the there are two different arrays and something needs to be done that you have to create a pair right try to read the problem statement the problem statement is not lengthy enough it is very short and crisp and not very much difficult language is used okay so now uh I hope everyone has read the problem statement okay so let's understand let's read the problem student all together so in this question you are given two arrays A and B of equal length okay and your task is to pair each element of array a to an element in Array B so you have to make pairs between two arrays array a and array B such that the sum of absolute differences of all the pairs is Minima basically you have to make pairs by selecting an element from array a and array B and let's say you have different M number of pairs and now what you have to do you have to select the pairs in such a way that if you take the differences of each and every pair pair 1 has difference D1 pair two has difference D2 and so on so if you sum D1 plus D2 plus D3 till DM then that sum should be minimum possible so that is what the question is asking you to do is the problem statement clear is the formal understanding of problem statement clear yes or no in the chat box and then we'll understand with the help of a test case okay so let's take this test case input example number one and let's understand over here over here in the first test case n was equal to 4 and the error elements for a is equal to 4 1 8 and 7. the second array was array B and over here the elements are 2 3 6 and 5 and what will be the output according to the question let's not see the output right now and let's try to solve this question first sorry for the inconvenience about this thing so now over here the question says that you have to select an element from the array a let's say what a pair contains pair contains an element from the array a and an element from the array B and what you have to do you have to where each and every element of array a with element of array B so let's say you get for this question you will be getting four different pairs and you have to find out the differences of each and every D1 D2 D3 and D4 are the difference and you have to take the sum of these differences and if you take the sum of these differences let's say it is D Dash you have to find out you have to select the pair in such a way that this D Dash will be minimum possible because we know that you can select the pair in many different ways right so your target is that so now let's try to select pairs from this one so let's say for first pair I am selecting 4 and 2 okay I'm just randomly selecting two this way I'm selecting in this manner so 4 and 2 is a pair so 4 minus 2 will give you 2 3 minus 1 the absolute difference we have to take the absolute difference it will give you 2 and this will give you 2 and this is going to give you two so the sum of it this comes out to be eight okay so we got one D is equal to 8 that the sum of the absolute differences came out to be 8 by selecting pairs in this manner so now what other pairs do you think we can make what different pairs do you want to select anyone from the audience write down different pairs which which you want to select should I go for four and three or should I go for one and two let's go with one and two okay so I selected a pair one and two now let's take other pair as four and three so I selected four and three now let's take other pairs five and seven so I selected five and seven and now let's take other pairs eight and six so now let's take the absolute difference this will be 1 this is going to be one this is going to be 2 and this is going to be 2 so the sum will be 2 plus 2 4 5 and 6. so I got one more D and it says six so it is lesser than eight right I can observe I got a a better answer compared to the previous one so I got D2 as 6. if you keep on doing this again and again I guess this is going to be the smallest answer you cannot minimize you cannot decrease more than six let's check what is the answer given in the output and answer is the 6 right the output is given to us as six so basically I selected such a pair and came to know that 6 is the minimum answer which I'll be able to get so this is the pair which is giving me the minimum sum of absolute differences is the question clear to everyone yes or no in the chat box do you want me to take another example is the question clear to everyone okay so now okay so let's take other example as well so that it will be clear you will get a better understanding so the other input test case contains this so over here test case number two input 2 over here n is equal to 3 a is equal to 4 1 and 2 and B is equal to 2 4 and 1. right so now what will be the output let's try to find the output so let's take one of the pair as 4 and 2 the other pair is 1 and 4 and the other pair is 2 comma 1. so what will be the difference to 3 and 1 so the sum comes out to be six so I got one d one has six so now let's change the pairs Let's Take One and Two and let's take I took one and two I took two and one and I'll be taking 4 comma four so what will be the sum this is going to be 1 this is going to be 1 and this is going to be 0 the sum comes out to be equal to 2 it is obviously lesser than D1 so the output comes out to be two let's check if this is the optimal output see over here I am getting the output as zero so this is not yet optimal let's uh try to find a better set of pairs okay so now let's try in a different manner so if You observe carefully over here you can observe 2 is also present in B and 2 is also present in a so I'll be keeping 2 comma two and one is also present in both of them and 4 is also present in both of them so this will be giving you different 0 0 and 0 right and the sum of this difference comes out to be 0 right so the output minimum D3 is minimum then D1 and D2 and hence output can be zero it cannot be less than zero right because we have the sum of absolute differences thank you minimum sum will be zero yes exactly so now what about the approach what do you think what can be the approach for this problem what do you think how you can solve this can anyone say The Brute Force approach can anyone share the approach that you are thinking right now so try to think how you will select pairs over here the technique or the thing is how you will select the pair the way you select the pair it will affect the final sum of differences sort the array okay om say sort the array and what is the reason behind sorting you are absolutely correct term so what is the reason behind sorting how will that help us okay we got an answer from repeating pratik's question is there a structured way to figure if video like for DP okay so I already answered that thing uh you can just go back in the video and you will be able to understand it okay so um what will be the reason behind sorting the array ascending order yes exactly so let me elaborate what om is trying to say so basically he's trying to say that we have to sort the arrays so let's sort there and let's understand the reason behind sorting the error okay so after sorting we get one two and four and for the array B we will we will be getting one two and four okay so basically after sorting you can observe that if you select the adjacent pairs adjacent element in both the RS like two two and four four the absolute difference the sum of absolute difference is the minimum possible so this is perfectly working for input test case number two so you can take it as algorithm one right algorithm one what you did you sorted the array and took corresponding element from both of them so this is algorithm one see in this manner you figured out for this test case number two algorithm one is working now we need to verify this will work for other test cases or not so now let's sort this array so this will be one four seven and eight and now this is going to be 2 3 5 and 6. so now let's select the adjustment one and two four and three and five seven and six eight so a few observe carefully you can observe that over here this is the pair which was giving us the minimum answer five and seven and eight and six and the minimum answer came out to be equal to six so this is perfectly working the algorithm work is perfectly working for this input test case number one as well right okay so now let's try another test case as well so that we can be sure enough that this is the final algorithm and it will work so if you will take one more test case let me uh take a random test case that is going to be input test case number three so let's take 3 9 14 and 12. and this is the array a this is array B and let's take eight seven four and nineteen okay so there are four number four uh different values in each and every array let's try to sort it so this will be 3 9 12 and 14 and this is going to be 4 7 8 and 90. now let's take the path three comma 4 and then 9 comma 7 and then 12 comma 8 and 14 comma nineteen okay so this will give you 1 is the difference 2 has the difference this will give four and this will give you 5 so the sum is equal to 1 plus 2 plus 4 plus 5 9 10 and the sum is equal to twelve can I do better than this and if you will argue that why this is the optimal answer and if I am able to justify it then this is going to be acceptable right so basically if you draw a number line we know that in the number line this is how the number line looks right it starts from 0 and it goes to infinite and time now on this number line if you place the elements of array 1 and array 2. so now on this number line if you place the element of array 1 and array 2 so by sorting 3 is over here so let's mark it with white 3 and I need to extend the number line no worries okay and let's uh ignore the numbers in between okay so after 8 we directly have the next number as 12 14 and 19 okay so I'm just writing down this manner over here 12. 14 and 19 okay imagine there are numbers and over here as well so 3 is the number after three we have 9 8 then 9 10 and over here we had 12 and what else do we have 12 and 14 and 90. 14 and 19. imagine there are numbers in between as well so 3 is the number in Array 8 3 9 14. this is nine this is 14 and 12 as well and for the array I'm marking it with green color okay so this is eight seven four eight seven four 8 7 and 90. okay if You observe carefully the after sorting you can observe see if I am taking an element a in pair number one pair one contains a and if I want the uh absolute difference of this to be smallest then what I can do I need the closest element to a if I want the difference of the other element if I want the difference of a minus B absolute difference of a minus B to be minimum then what I can do I can select a and b as close as possible if I select 3 and 4 if I select 3 and 4 or if I select 3 and 19 which will give you smallest absolute difference what do you think obviously 3 minus 4 will give you the smallest one 3 minus 19 will give you 16. so by sorting each and every number which should be paired to the closest number will be adjacent to each other okay will be closest to each other so after sorting this is how you replicate the number line by sorting so this is the reason why I'm sorting the arrays so if you sort the arrays so what is our algorithm so algorithm comes out to be that you need to sort both the arrays and select chorus bonding elements in both the array in both the array to make a pair so this is the algorithm for this portion any doubt till now yes or no in the chat box any doubt do you guys have any kind of doubt okay so now we need to sort the errors and select corresponding elements so we can directly move towards the coding implementation for this same I'll be coding in Java but as I mentioned the entire algorithm I guess everyone will be able to code in other languages you simply need an algorithm and implement it in any of your language right so first step is to sort both the errors so I have an inbuilt function in Java that says Eris dot sort and it will be sorting both the errors so I'll be applying uh the inbuilt function to shortboards I have started both years now the second step of the algorithm came out to be selecting bonding elements from both the arrays right so what I will be doing I will be iterating over both and what is the size of both the areas size of both the array is equal to n because they are of same size now in order to store some answer I need a variable right so I'll be taking long because it is possible that absolute difference let's say over here if you will take the constraint the constraints is the maximum element can be as large as 10 to the power 9 and small s can be as small as 0 let us imagine an uh worst case example in which array a contains all zeros and the other array contains 10 to the power 9 each and every element is 10 to the power 9. now if you will take the absolute difference the sum will be equal to 10 to the power 9 multiplied by 10 to the power 5 imagine an array of size 10 to the power 5 according to the constraint so 10 to the power 9 into 10 to the power 5 will be somewhat somewhere around 10 to the power 40 and integer data data type is not uh huge enough to store such a very large number right so I have taken this data type as long now let's take the adjacent element so adjacent is array of I minus B of I now we need an absolute difference right we don't know whichever which element is going to be the uh larger one so I have taken the absolute difference of both of them and I'll be adding the answer and at the end I'll just simply returning the answer okay so let's try to compile and run and the compilation works perfectly fine I hope this works and the compilation is completed let's try to submit and see the acceptancy and you can see the problem was successfully solved right over here we you'd use the same technique right I explained that in order to solve greedy algorithms this technique of trying out as many as test cases will work and each and every step at each and every test case you will be able to understand that this is the similarity of approach for each and every test case is it clear yes or no in the chat box were you guys able to understand it properly or not okay so if it was clear we can move towards the next question so the next question is this one a Mini maximum meetings in one room so try to read the problem statement okay so the question is like it has many lines of uh problem description so try to read the problem statement I'll share the link of this in the chat box okay so try to understand what the question is trying to say and try to read down the example as well so for this I'll be giving you five to six minutes and if you have read the problem statement just mention it in the chat box foreign this is one of the standard problem of greedy algorithm okay and a variation of this question like we will be asked to you as well okay it can be asked in an interview as well and this is uh also interview uh like Centric question it has been asked many times in interview a very famous question of greedy algorithm how many of you have completed the reading of the problem statement okay so I missed a comment that is pratik says this approach can also be too big for Max difference also yes this approach can be for maximum difference okay yes you can do that as well okay pratik has read the problems as well and what about the other guys and for this uh for this question for the previous question what you can do whether it is given no that for all the the sum of the absolute differences of all pairs is minimized so if what a maximize was given to you what if maximize was given to you in the other different question try to think on that okay so for greedy algorithm you will be able to see that for minimum also you can solve that question for maximum also you can solve that equation okay and whichever is the hardware one will be the priority of the interviewer so we'll put minimum or maximum and for some question it does not make sense that what is the minimum of profit or minimum of something right for some question you can solve it for maximum also and for minimum also okay I hope it is clear so now it's 8 39 is there anyone who is still reading the problem statement and those of you who have read the problem statement tried working on the approach of it okay okay now let's understand the problem statement those of you who have not read the problem statement pay attention over here will be understanding together so the name of the question is maximum meetings in one room and difficulty level is medium okay so don't focus on difficulty level just go directly to the problem statement there is one meeting room in a form okay so there are n meetings in the room uh and meeting in the form of s of I and F of I so where s of I is the start time of the meeting I and F of I is the finish time of the meeting I so for ith meeting s of I denotes its start time and F of I denotes it and time so the task is to find the maximum number of meetings that can be accommodated in a meeting group you can take an example let's say in an organization there is a meeting group okay and there are different different meetings that needs to take place you are given time the starting time and the ending time it stick it is very much strictly to be followed that whatever is the starting time and Minima finishing time you cannot extend or you cannot reschedule the meeting so what is the task the task is to find the maximum number of meetings that can be accommodated in the meeting room as there are n number of meetings and it is possible that the timings of two meetings might overlap and it and you cannot put both the meetings in the same room at the same time okay so the question says we want the maximum number of meetings to be held in this meeting room so you have to find out what is the maximum number of meetings that can be held in the waiting room so you can accommodate a meeting if the start time of the meeting is strictly greater than the finish time of the previous meeting as I mentioned if the meeting timings are overlapping then you should be sure enough that the start time of your current meeting is greater than it is strictly greater than the end time of the previous meeting that means after the previous meeting has ended completely then and only then your meeting is allowed if it is starting after the ending of the previous meeting okay and it is given in the note that if two meetings can be chosen for the same slot then choose meeting with this smaller index in the given array okay was it clear till now okay we already got an answer from gaurav okay so we'll uh not directly jump to the solution part but let's uh solve it on our Pace right so was it clear was the formal understanding of this the story part clear to everyone yes or no if it was clear a plus one in the chat box right so now let's take this test case and try to understand that how we can achieve it now here you can see in the input n is equal to 6 that denotes the number of meetings and S is the array that says start name of every meeting and F is the array that denotes the ending time and in the output you can observe there are some different numbers one two four and five so what does it mean so it is the meeting ID I mean the first meeting or the index of the array let's imagine the indexing of both the array starts from one one two three four and five and at the end six so over here in the output it has mentioned that which meetings can be conducted and what is the ordering in terms of uh no such ordering is to be followed but this is the total number of matings which you can uh accommodate in the material so one two four and five so that means the mating starts at 1 and NZ 2 can be done 2 that is 3 and 4 can be done and four that is five to seven one and five is this one eight to nine so this four meetings can be held in the meeting group so let's understand let's copy the test case so here is our question number two if you have any doubt in the problem statement do mention it right now okay okay so question number two and now we were having the test case as this so let's so the test case is n is equal to 6 and the starting array s is equal to 1 3 0 5 8 and 5. and the other array that is finishing time of the earth meetings is 2 4 six Seven Nine and Nine okay and we have to find out which meetings will be held and in the output you have to put their IDs so ID will be one two three four five and six or the numbering of the meetings right and now here is our imagine this is my meeting room now how will I start solving this test case we need to understand so we know that let's imagine a number line I mean a number line or a timeline okay and the timeline starts from zero this is one two three four and now over here let's mention the meetings as well so the meeting one starts from one and it ends at two so this is meeting one and the other meeting starts at 3 and ends at 4. so this is mating number two over here everything is based on the time right so it is better that we imagine actually how on the number line it looks like so after M2 this is meeting three starts at zero and it ends at six you can observe that this meeting times are overlapping right clearly we can observe so the fourth wedding starts at time at fifth hour and it ends at seventh r this is M4 and what is the fifth meeting it starts at 8 AM or let's say eight hour and it ends at 9R this is meeting number five and the last meeting starts at fifth R and it ends at ninth hour right so this is the last meeting that is meeting number six now you have to find out that which meetings should be scheduled so that maximum number of meetings can be done right in that room so let's see if I am selecting meeting number one if I'm selecting meeting number one then all the overlapping meetings cannot be held in that room submitting three has no scope of being held okay so let's say if I'm selecting meeting number three now after selecting meeting number three I have an ideal time after two hours right after two hours I can organize any kind of meeting I want so this is meeting number two because I have the option that at uh R number three I have meeting number three okay so I'll select meeting number two now over here as meeting 2 is being held meeting three cannot be held because it is overlapping so after the fourth R I am completely free I have the entire meeting room so I am selecting meeting number four and after meeting number four I have a it ends at the seventh R and I have completely free time so I'll be selecting meeting number five if I'm not selecting meeting number four let's say over here what is the total number of meetings which I was able to conduct I am able to see that four meetings were being conducted that was one two four and five okay and let's say if I was not going for the meeting number four over here okay instead of meeting number four what will be what will be selecting I'll be let's say I'm selecting meeting number six if I am selecting meeting number six I cannot conduct four and five and over here what will be the sum of meetings or the total number of meetings that were conducted it is equal to three submitting one two and six were conducted right so I can see the better option is to conduct the total number of four meetings can be conducted and that is the maximum answer better than that I don't think we can do it let's try out one more if I am selecting meeting number three instead of meeting one let's say if I'm selecting meeting number three I selected meeting three so I cannot select any other meeting not meeting one or not meeting two not meeting three I mean four and six also cannot be selected so the last option remains is meeting number five so what total number of meetings two meetings third and fifth so what is the uh optimal and what is the maximum answer how many meetings can I I can conduct four meetings at Max and that is going to be the output for this what's the question and how to solve it in a Brute Force manner was this part clear can I get a confirmation okay so pratik has mentioned two different approaches okay foreign okay so in this manner we can try out different different approaches and we can solve our test case but overall this Brute Force manner this Brute Force way if we select this Brute Force if you go in this in this manner it is obviously going to take much amount of time right so what do you think what can be the approach how we can achieve it how we can reach down a solution okay pratik has already mentioned the knife as well as the uh other approach so I want the answer from other people as well what do you think try to think what can be the Brute Force approach foreign how can we achieve the answer how can we find the answer I think we can use previous quotient approach maybe okay so over here that was a smart move so in the previous question we did some things sorting and kind of thing right so over here on which array should I go should I sort the first array that is the array which says starting time or should I sort the second array we need to think on that right which sorting will help us which sorting will be beneficial uh does there any free certification yes gaurav you were correct about the approach which we can take from the previous question but try to think on which array should I apply sorting or on both the areas do you think applying both the arrays on uh like sorting on both DRS will be helpful yes or no in the chat box what if I apply sorting on both the arrays is it a correct way to do or not okay so gaurav says sort both the arrays not on both the array okay so why not sorting both the array how many say how many of you are agreeing that we can sort both the arrays I'm not asking the reason or anything I do you guys have a do you guys like are thinking in that way that we can sort both the arrays how many of you are saying that we can sort both the arrays and how many of you are denying that do not solve only on start okay so gaurav says only on start and what about the other people what do you think so I can understand by now everyone was able to figure out one thing that sorting needs to be done okay and how were you able how were you able to think about sorting because if you draw a timeline in such questions you will be able to observe okay you can observe that meeting one is being held before meeting two I can observe overlapping of meeting one meeting and meeting two right so try to visualize the numbers okay if it says it denotes time try to visualize on on a timeline in this manner so this will help you a lot okay so I got an answer I think when it uh ZIP the list and sort by the end okay first thing we can try out that as well and uh bhavya says start and end time is the pair so we can't sort yes exactly so basically over here this both the arrays represent the starting time and the mini and the ending time of a particular meeting so this two cannot be placed at any other position okay if this one denotes the starting time of meeting 1 then this 2 needs to be placed at this particular index only you cannot rearrange it anywhere else because the there is a mapping between the uh both the elements of array both the elements of start and the first error so basically this elements are mapped together okay you cannot interchange them if you interchange them then you will lost the data you will not have the correct data okay yes exactly above here you are correct because if we sort both the array the couple of start and exactly sorting will ruin the array okay so uh okay so pratik said I think we can zip the lists and sort by the end time okay so we can do that as well but I need to know from you guys why are you guys thinking about sorting the end time what if I sort the starting time won't that work and what is the reason if you are saying that that will not work I agree with you okay so without questioning I'll be agreeing but I want the reason behind sorting the ending time what is the reason behind sorting the ending time what do you think okay so what is the reason behind sorting the end time okay end time means uh current meeting is the first to end time means the current meeting is the first to end uh there is no previous mending ending before it okay anyone else why do we need to sort the ending time of the meetings what if I sort the starting time of the meeting let's try out by sorting the starting line okay first of all Let's uh verify that why should you move in that up in that direction so over here what I'm trying to do is that sort the sort the starting time okay I'll take the same example this one and over here as a mapping is there between both the elements what I'll be doing I will imagine them as a pair okay so you can imagine them as a pair in this manner meeting 1 says one two two meeting two says three to four and meeting three says 0 to 6 waiting four says five to seven eight to nine and five to nine five and mating six now I'm sorting based on the starting time okay so I can see this starts at zeroth time it's so I can place it over here and now this will be the second one sorry excuse me sorry I forgot to share the screen so over here I have I have mapped the starting time and the meeting time you can imagine this as a class or anything as an object of meeting and that object contains what it contains the starting time and the ending time of the meeting okay and you can place the ID of that meeting as well that is the index so I'll be placing uh three different values starting time ending time and the index index starts from 1. so now I'm sorting this arrangement of Matrix based on the starting time so for starting time I can see M3 as the smallest starting time now M1 is the smallest starting time and now what else now I have M2 as the smallest one and M5 so whether you can observe M4 and M6 so node says that whichever meeting is having the smallest ID should be selected let's say you reach a scenario that you have the option to select M4 and M6 right and both of them are starting at the fifth r so you should go for M4 but over there this should have the same ending time as well so let's say I selected M4 then M6 and now at the end M5 so this is the Sorting based on the starting time so now let's try to understand so now after sorting what I will be doing what how will I achieve the solution now I have sorted now how should I work on it yes exactly pratik sorting by start time does not give much information okay so what information is missing over here okay so I have sorted and now let's say after sorting I'll be selecting sequentially right there was some meaning behind sorting no I sorted it so now I can select sequentially right so let's start with M3 I selected M3 and it starts it I'll be mentioning it over here the ending time of the previous meeting so currently my M3 is being held and it has an ending time of 6. so next meeting can only start after sixth R okay not at six star as well so can I go for M1 no because it has a starting time of one can I go for M2 no can I go for m 4 no I cannot go because that value are lesser than the end time of the previous meeting can I go for M6 no can I go for M5 yes I can go for M5 so M5 will be the meeting which is which is going to be held and the end time of this meeting 5 is 9. so any value or any meeting which is starting after ninth R can perfectly be organized so after I am fine nothing is remaining right so I can go for this as well so I will be going with M5 so what number of meetings were conducted I can see 1 and only two meetings are conducted but that is not we know that that is not the correct answer right isn't it take the uh the pair taking less time no over here we have to focus on total number of meetings that I can organize okay so if you focus on the duration of the meeting that is not going to help okay if you focus on the duration of the meeting then it is not going to help everything questions so is it clear that sorting on the uh starting time is not giving correct answer why because over here the main focus is that and the time of the previous meeting and the start time of the current meeting okay if I want to conduct conduct a meeting if I want to currently organize a meeting then I I need to check the end time of the previous meeting okay and then and only then if if the end time of the previous meeting is strictly lesser than the start time of the current meeting then and only then I can organize this current meeting so over here this inequality will be giving you the correct answer will be helping you to find the maximum answer if and only if you sort the Matrix based on the end time because the end time will be obviously will be lesser than the start time okay I am sure for each and every pair so now before sorting based on the end time let's say on the number line this is the end time of every meeting and time of E2 A3 let's say uh E5 is ending over E4 is ending over here and a 7 is ending over here right so this meeting will be started before this end time only right because we know that the starting time is obviously uh lesser than the end time so this is how the arrangement will look like okay so at the end you simply need to compare the end time of the previous meeting because you have sorted based on the end time so this part is completely sorted now you simply need to check whether the next meeting E2 can be held or Not by just checking the end time of the previous meeting okay as we know that the start time is always lesser than or equal to the end time we can apply the Sorting on the end time so this part will be uh checked this part will be done for us and this inequality part that is can I organize the next meeting or not can be checked by simply doing this inequality comparison okay so that is the reason that sorting on the start time will not work if you sort based on the start time let me give you a visualization of that as well now let's say I start assorted based on the start time so this is S3 S2 s uh let's say seven I'm just randomly writing down okay so don't focus on this part and this is s it's a six so now as I've sorted based on the starting time it is possible it is completely possible that the start time of one of the meeting can be as long as possible it can be like let's say the it has the largest ending time right so this meeting will be clashing with the other meetings as well and you will not be able to handle or you will not be able to held any kind of meetings if this S3 was selected because a start time is bounded by the end time but from start time we can't tell anything about the end time yes exactly because if we sort based on the start time we will not have any kind of idea regarding the end time if we have sorted based on the end time we can see that start time is lesser than the end time so this meeting might have started at a time let's say this meeting was ending at the fifth hour then I can be sure that M1 might have started at some time lesser than 5. but if you sort based on the starting time let's say M1 was starting at R2 then you cannot say nothing you cannot say anything about the end time you can simply say that the meeting one will be ending at an R greater than 2 but this is obvious now right and this is not at all going to help me uh in scheduling the next meeting because at the end I need to compare the end time as well are you getting my point everyone a plus one in the chat box if this part was making sense to everyone okay can I get the confirmation from everyone whether this part was clear to you or not okay thank you pratik okay so now we concluded we can conclude that sorting on the start time is not going to help so what else other thing so we had three different options right sort both of the arrays sort based on the start time and the other option was sort based on ending time we have three different options and one by one we can conclude for each and every that this thing is not going to work this is also not going to work and now the last thing is remaining it's sorting based on the end time so we need to verify whether this is going to work or not so now let's take the same example and verify it thank you for the confirmation you guys are attentive right are you all students or uh are you working professional as well can I know what what do you do what my audience does are you working professional or pursuing or Refresher okay write down the chat box I will write it down so now this thing second thing which I which I was going to do was sort the ending time okay so unrelated your writing is beautiful thank you student student okay and what about you pratik are you a student or working somewhere thank you so let's get back to this so I'll be sorting based on the end time based on the ending time career shift trying to get back into it preparing for interviews okay that's really don't you guys think that ID is a very like uh that any non-tech anyone from non-tech background as well and those of you who are already in Tech they can obviously get the job in IIT but those of you who are not from non-tech as well you have lots and lots of opportunities over here because you simply need to know DSA and just start learning a programming language and that's the entry level thing which you can do for getting an entry in IIT so everyone welcome to it okay and um is working that's really great we have a very like everyone is like thriving to get into it and it's really great and trust me this is not going to end like IIT sector is going to progress a lot it is going to achieve new steps Telecom to ID okay so now let's uh get back to the question part so sorting based on the ending time okay so let's start sorting so I have taken this pair where n is equal to 6 there are n 6 different meetings now let's sort based on the ending time and over here I am sorting in increasing order of the time not in decreasing obviously you know we uh what why what is the need of sorting and decreasing time because time does not run in Reverse manner it does not decrease right it always increases so I'll be sorting in an increasing order of the time and which is the smallest who has the smallest ending time ample let's pick M1 now the other is M2 let's pick M2 the other is M3 based on the ending time and now this is already sorted let's pick and place it over here so now I have sorted the entire meetings based on the ending time so now let's one by one check and I will give one more variable that is end time that denotes what was the end time of your previous meeting okay and currently no mating is there in the meeting room right so the end time let's skip it as minus one over zero anything let's keep it as minus one because for some of the meeting its starting time can be equal to zero as well okay so I'm for safety purpose I have initialized n times minus one so now let's pick m one so when can you uh pick a mating so you have to check if the starting time if the end time of the previous meeting that is the variable end time is strictly lesser than the starting time of your current meeting starting time of your current meeting then and only then if this condition is satisfied then and only then you will take this meeting to the meeting room okay so now let's compare so end time is this end time is -1 and what is the first meeting start time it is one so minus one is lesser than one yes absolutely so this M1 can be organized so I'll organize AMP one okay and if any of the meeting is being organized then you will update the end time so end time will be nothing but the end time of the meeting which was organized previously so two will be the end time currently now let's pick the next meeting so next meeting is M2 so let's compare the start time so this is my end time and time is 2 and what is the start time is 2 lesser than the starting time of our current meeting yes so I will take this meeting to to the meeting room and update the end time so end time will be the end time of this M2 so this will be 4 so now let's check for the next meeting next meeting is this one M3 and time says 4 and what is the starting time of the meeting starting times meeting is zero so do you think this inequality holds true absolutely not 4 is not lesser than zero right so M3 will not be selected now moving towards next meeting so that is M4 and time is 4 and starting time of M4 is 5 so let's see 4 is lesser than 5 yes absolutely so M4 will be conducted and let's update the end time to the so friend time will become 7 because that is the end time of the previous meeting now let's check the next meeting so next meeting is m6 so do you think this this is the starting time do you think 7 is lesser than five no absolutely not so skip m6 and go to M5 so M5 says its starting time is 8 so 8 and 7 is lesser than 8 yes absolutely so I will go with this meeting M5 and updating the and time to night so 9 will be the end time so now after this is there anything remaining no nothing is remaining now how many meetings were conducted four meetings were conducted and whatever their IDs and IDs were one two four and five and this is going to be the output okay is it clear yes or no in the chat box was this part clear to everyone what was the process of selecting a meeting if you want to select a meeting then this is the inequality that should hold true this inequality holds true for a particular meeting then you can select this meeting and update your end time variable so was this approach was this uh process clear to everyone yes or no in the chat box a quick reply if you have any doubt mentioned in the chat box okay so thank you so now let's write down and convert this process into an algorithm Okay so let's write down the steps of the algorithm okay so what is the first step First Step includes sorting the array right which array which array finish time array I have to sort based on the finished time array so can I directly sort this finish time error and will it work no as I mentioned that the elements of both the arrays are bounded to each other they are mapped to each other right you cannot change the arrangement of them or you will lose the data so what I will be doing I will be over here create you can create a pair you can create an object it's your choice right so what I'll be doing I'll be creating an object of every meeting okay I have created an object and vertical be stored inside that object now inside the object I will store its starting time its ending time and its index because in the output we need to print the indexes at which meeting will be conducted so after doing so what you need to do place this entire thing in an error list or a list to be more General put this objects in a list okay so as you have created a new list some space will be occupied and then space occupies occupancy will be equivalent to what it's space occupancy will be equivalent to the number of meetings that is order of n space will be occupied okay so time and space will be discussing at the end of algorithm so I have sorted now I need to sort the meetings right an object a list of meetings was create created now I need to sort the meetings so sort the list of meetings based on their ending time okay so now I have assorted list of meetings so now after doing so what I need what else do you need I need a list to store an answer list to store an answer now what else do we need I need a variable over here this Andy time was the variable that denotes the ending time of your previous meeting right okay so this anti time variable is required so let's get an end time variable and what else do you need do you need anything else no I don't think anything else is required now the next step is going to be a loop I need to run a loop on each and every element of this meeting so basically now end time let's say is initialized to -1 so I will be running a loop from 0 to I is lesser than n and inside this what is the condition that I mentioned that if this condition is satisfied then and only then I will include the current meeting what is that condition so that condition is over here if the end time of your previous meeting is lesser than the current times current meeting starting time then only then you will be including right so if this condition is satisfied so if what I am doing let's call the list let's name this list as meat okay so now if for the current meeting of I and its starting time if this starting time is strictly greater than the end time of your previous meeting so end time this is my end time if this is the inequality if this inequality is satisfied then I will include the current meeting in my meeting room so I have created an answer arraylist right answer list so what I'll be doing answer dot push or answer dot add I will add my current meeting what I'll be adding I will be adding its index okay I will be adding its index so I have added this meeting in my meeting room and what else do I need to update I need to update my end time variable I need to update my end time variable with what value with the end time of the current meeting which was included okay meeting I was the meeting which was included so I will update my end time variable in this manner and that's it at the end what you need to do you simply need to sort the list of answer why do you need to sort the list of answer because if You observe in the output the indexing is mentioned in increasing order only so if you are sorting each and a particular meeting based on their ending and starting time it is possible that the indexing will not be in a sequence it will be randomly selected and hence you need to sort the last answer list and then simple nothing nothing else the entire algorithm is complete foreign any doubt till now any doubt in this algorithm any difficult part any line you are not able to understand any part is any part of the logic yes or no in the chat box okay if you have any doubt in these algorithm just directly mention it right now okay thank you for the confirmation okay so this is the enter algorithm so now let's try to Implement and implement in terms of code right so over here again I will be using Java you can use any of the language of your choice right so now I'll be creating an object of meetings and that object start and an idx will be the variables so what I'll be doing I'll be creating an object so I'll be needing a class and what I'll be calling it I'll be calling it as class let's say I need three different variables I need start time ending time and what else I need I need idx that is the index X let's create a Constructor for initialization of this variables so whenever a new object of this type is created I will be initializing all these variables with the starting line ending time and the index right so I have created an object now what was the Second Step sort the list of Matrix but the first step was to create an object of every meeting and put it inside a list so now I have an object I have a class but I need a list or something like that so I will create an error list and the data type of the analyst will be objects of temporary class and let's call this as meat equal to new Iris now one by one let's put all the meetings inside your error list meet so I'll be iterating over the starting time and the ending time and what else I will be doing I will be creating an object of meeting or an object of temp and I will be pushing that temporary object inside my analyst that is mid arraylist okay so now let's create an object I'll be directly creating an object and inside that object I'll be passing the arguments the starting time the ending time and what else index so index as I mentioned the indexing is one based indexing so whatever is the index I'll add one to it so this new object needs to be added to your mid so I will be adding this object inside my list meeting any confusion in this part if you have any confusion do mention it right now okay as this is not language this week everyone I hope is not aware like might be coding in different different languages right so I have created a list of meetings so let me add the pointer as well now the Second Step was to sort the main things based on their ending time now I need to sort a list of objects so now here is the trick here part okay so what I will be doing so over here we have something called as comparable interface in Java and you can implement this comparable interface and inside that there is a comparative method which you can implement it inside the class which you want so what I'll be doing I will be implementing comparable interface and I want temporary class of objects in it and what else I will be doing I need implementation of comparative method click end compare to method and the argument which I'll be passing to it this is language specific if you are not aware if you are not coding in Java and don't uh try to like don't get confused by this thing okay and object I'm passing an argument of objective and what I'll be doing I need to sort based on what I need to sort based on the ending time so I'll be sorting it based on depending that so this thing will help me to sort the entire list of meetings or objects based on the ending time right so now I can use the inbuild method to sort the entire meet let's check the output as well right and now let's run a loop in order to see the output just to show you that this will sort it let's see the output foreign and over here this is the index okay so let's see the output and I need to return correctly return this an empty list I'm just returning an empty list so that we can see the output because this function requires uh something to be returned right so I've returned this part and what is the error okay are you guys with me or not yes or no in the chat box so whether you can observe the starting time and the ending time I had three meetings one three and five they are starting at one three and five and you get three three five so starting time is one starting time is three but over here we are sorting based on the ending time so this is how it looks ending time let's take this example as well let's copy this example and let's check the output your observe ending time sorting has been completed so now let's remove this and let's go get back to overhaul so this is going to work perfectly fine the Sorting part is complete now let's see what is the step number three I need an answer arraylist and I need a variable and time so let's see I need a list called as answer and I need and time variable okay so enter your end time is equal to minus 1 and a list of integer to store the answer and it is going to Only Store uh indexes right so now this is the third step which is complete and now what is the fourth step I am going step by step so that you can understand what actually we are trying to do and now the fourth step is to iterate over the entire array we trade over the meetings and now what else I need to check so what I'll be doing addition every index I will extract the static diamond and the time of the particular meeting in a variable okay so make plot get the element at the is index and inside that element we at the start time foreign now I will be comparing the ending time that is if the end time of the previous meeting is strictly lesser than the starting time of my current meeting then I can conduct my current method so conducting a current meeting means making an entry inside the answer error list so I'll be adding the ID inside the answer arraylist and what else we need to do we need to update our end time variable to the end time of our current meeting so that updation is also complete and now this is our fourth step so fourth step is complete now what is fifth step is to sort the entire list of answer because I need the output to be in the sequence of meeting numbers right I need it in increasing order according to what is mentioned over here C you can observe your task is to you don't need to read an input output your task is to complete the function Max meetings which takes the arrays and Returns the meeting numbers we can attend in sorted order so sorting is required so I'll be using collections dot sort to sort B list and this list will be answered at least and now I can return the answer list let's compile and run quickly and let's get this thing done was it clear can I know from the audience if this was clear or not so whether we are getting zero zero zero okay so the reason for that is this part Let's uh try to debug why we are getting zero so we created a meeting we created idx okay idex I made a mistake over here now let's try to again compile enter and we can observe compilation perfectly fine let's try to submit and see if this gets accepted or not so till now uh what is the time in space complexity of this approach what do you think is the time in space complexity of this algorithm you can try to figure out what is the time and space complexity this is the creation of a list of meeting this is sorting part okay so sorting takes n log n okay so let's try to debug let's try to understand so this part will uh this second step will require big off n log n and number of meetings are there so creation this part over here this part takes order of n because you are iterating once so now this is constant time this is not going to take any amount of time we go off one this is constant time right and iterating over the meetings what is this order of n it and over here the fifth step is sorting again and what are we sorting that is let's say in worst case what can be the uh size of this answer list in the worst case it is possible all the N meetings can be there inside you answer this so again this will be order of analog n so order of n log n plus order of n plus order of n log n plus order of n so overall I can take it as order of angle again yes exactly pratik you are absolutely correct sorting is order of hand login it is not order of n okay I hope this is clear by now so the time complexity comes out to be order of n what about the space complexity what extra thing have you taken I have taken only a meeting array and I have utilized this answer array and the size of both the arithmics can be order of n because this meeting array contains all the meetings and this answer array adverse can contain all the meetings so the space complexity can be taken as order of n and this is exactly equal to what is expected from the question expected time and space complexity how time complexity of sorting algorithm is order of n log n so the best sorting algorithm which you can think of that is merge sort which is also implemented internally in this and build functions and it will take order of analog okay soil foreign regarding this question or else we'll jump to the next question that is the question which will be given to you in homework and are you guys doing the uh practice questions on your own this kind of questions which the email thought is giving you as a homework okay I see no doubts coming so uh let's read down this problem statement for this question I will be explaining in the entire problem statement and I'll be giving you some hints so that you can try this Solution on your own okay and I already already taught you the technique to solve questions on greedy algorithm right take different different test cases and then you will be able to solve it not repeating this question let's look at first how about how about but how to arrive at greedy solution see for greedy as I mentioned okay so again uh trying to uh explain you see for greedy according to my experience and according to the questions which I have solved on greedy and on DSA generally greedy can the the algorithm for greedy can be found by repeatedly working on test cases try to create a generator test case if you have a test test case try to get the correct answer and how you will get the correct answer by arguing that is this the optimal answer if this is the optimal answer try to find out a conquering answer that try to minimize this try to find a smaller answer compared to what you have achieved for that particular test case and keep on doing that thing for different different test cases and you will find similar kind of steps which are being followed in solving each and every test case so that is the way to get the solution for greedy algorithm now I hope you are able to understand pratika okay and obviously you need to know standard questions of greedy or any of the DSR topic you need to learn about standard problems as well okay okay so the last question which I'll be giving you for practice that is candy I'm not giving you candy I'm giving you this question and try to read down this problem statement or let's uh already it is 940 so I'll be uh reading down the problems too and I'll be quickly explaining you what the question is trying to say okay so the quotient difficulty is hard but it is not very much hard the solution part if you will understand if you look at it it's not very much complex okay so there are n children's standing in a line and each child is assigned a rating value given in the integer array ratings rating array denotes the rating of the ayat of the ayath child so you are given you are giving candies to these children subjected to the following requirements okay each child must have at least one candy and children with higher rate higher rating get more candies than their neighbors okay so these are the two points these are these are the uh requirements for assigning a candy okay so you have this you have to follow this part each child must have at least one candy and children with the higher ratings get more candies than neighbors so what you have to do return the minimum number of candies you need to have to distribute candies to the children you have to find out what amount of minimum candies I need to keep it with me so that these two points are satisfied for the given test case so now let's work on this sample example so over here n is equal to 3 and ratings array and this ratings area contains 1 0 and 2. so what are the two points that two points are at least one candy and candy for a student okay and the other requirement was student with higher rating children with higher rating get more candies than their neighbors student with higher rating get more candies than neighbors okay short form and we are neighbors okay so now this is the thing one zero and two so the first point say is that at least one can be for every student okay so let's assign one for every student now the second Point Says student with higher ratings get more candies than their neighbors so let's start with the first one so one and their neighbors are zero so over here one should contain one should have more candies compared to zero so over here you can see Zero as having one candy so I in order to minimum in order to find minimum number of candies that you should keep you will try to uh not give more or not required amount of candies to any of the children okay so not giving more number of candies which is not at all required to any of the children so minimize the candies you need to have you need to have so this should have one more candy so I need a number which is greater than one and the closest one is two so I'm selecting two that is two candies so now let's come to this so zero is it larger than both of its neighbor no it is not larger so one is sufficient enough for zero now two is it larger than both of its neighbor yes over here no neighbor over here zero so zero is already having one but two is also having one candy so it needs to have more higher these compared to zero so the next number which is larger than one so I need a larger number compared to zero compared to one so that is going to be two so this last student will be given two candidates so in total how many candies are being allotted two plus one plus two that is equivalent to 4. so the output comes out to be 4. and let's come check it so whether I am getting 5 as the output okay so it's 2 plus 2 plus 1 that adds up to five sorry my mistake it adds up to five two plus two plus one that is equivalent to five so five candies is the minimum or minimum number of candies that you need to get with you yes exactly you are correct okay so this is what the question is trying though so let's take one more example and now let's take one more test case test case number two and that what I'll be doing I'll be rearranging the two zero one let's say this is uh three okay and following the steps according to the question so this is the step which I need to keep in mind so 0 1 2 and 3 and now the first at least everyone should have a candy so assigning one to every student now the second thing needs to be handled student with higher ratings get more candies okay so the first student let's start it is having rating two and both of its neighbor so over here no neighbor and this is zero so zero is having one candy and 2 is also having one candy so it needs to be having higher candies compared to zero so next number which is larger than one it is two so two will be assigned to this two now next zero is it larger than any of its neighbor no so one is sufficient for a so for this one is it larger than any of its neighbor yes it is larger than this left neighbor so for compared to left neighbor it should have higher number of counties so both of them are having one candy so if I give him one more candy that is two candies and this uh second point will be satisfied for this student now the last one so last one is equal to three thank you and for last one what else do you need to do you need to compare both its neighbors so left neighbor is not right neighbor is know that not there and left so three is larger larger than both of its name right so obviously it needs to have higher candies compared to one so a number greater than two which is just greater than two that is equivalent to three so he will be having three candies and now what is the total number of candies distributed 2 plus 1 plus 2 plus 3 that is equivalent to eight eight candies are being distributed okay so now was the question clear to everyone yes or no in the chat box a quick reply from everyone whether the question was clear to you or not can you uh show it for a test case two one zero three yes yes absolutely it will take one more test case test case number three and two 1 0 and 3. okay following the first step at least one candy for everyone one one one one and one now following the second step okay so this first student it is larger than any one of its neighbor this one so both of them are in one but it should have larger or higher number than this one so I'll be taking the next number larger than one that is equivalent to two so two will be assigned so over here one is it larger than any of its neighbor yes it is larger than zero right and both of them are having same candies it is not at all uh acceptable right so this will also have higher number of countries but I want to minimize total number of candies that should that I should have so I'll be taking a number larger than this larger than this and smallest one so that is equivalent to two so two candies will be given to him now for this zero any of its neighbor is smaller than zero no and what about this last one any of its neighbors smaller than three yes this neighbor is smaller and both of them are in one candy so I'll be skipping this I need a larger amount of candy so a number just greater than one comes out to be two so two will be sufficient and this inequality holds true story uh ratings get more candies than Neighbors what is this sum 2 plus 2 6 plus 1 that is equivalent to 7. for this the output comes out to be 7. okay pratik was it clear I hope is it clear to everyone yes or no so that I can give a hint on how to solve this not clear which part can you mention pratik which part is not clear okay two and one both have same candies okay okay we got it yeah yeah thank you for finding it out so the second point is not being uh fulfilled for everyone right so two and one both both of them are having same candies so you can observe over here two and one are having same candies so that is not at all uh sufficient enough right so I need a larger number compared to this one compared to this one a larger number which is closest which is smallest one and larger than this two that is equivalent to three so this will be as handle three instead of two and now this is the minimum candies I should have that is three plus two five six seven and eight and the output comes out to be eight now anywhere else no I don't think anywhere else one okay three okay and two and one I hope now it is clear is it clear now okay so now what about the Brute Force approach are you guys able to think about a Brute Force approach so we recurs on the left if needed okay so this approach which we were doing right now you need to apply it more than I don't know how many number of times right because at each and every point you will be fulfilling both the points for a particular index both the points will be fulfilled for a particular index in each iteration right so in that terms you need to apply this Loop many number of times until and unless you see no change happening to this entire array and every time try to pick the what you will be trying to do maximum of both the child left or right child okay maximum of both the left and the right so over here for the particular student array of file you have the left child and the right child right what you need to do let's say both of them are greater than the current both of them are I mean both of them are having less ratings compared to U array of I minus 1 area of I plus 1 both of them are having less reading so this obviously needs more number of candies so what you'll be doing you will be taking the maximum of both of them that what candies are assigned to both of them so candies of I minus 1 and candies of I plus 1 so maximum and plus 1 is the number of candies that you will assign to current student isn't the highest as to have highest can that means three no it is not the case that highest should always have the highest number of candies okay if over here uh see the comparison is not among the students not among all the students the comparison is Among The Neighbors I minus one I plus 1 right so the comparison is for the Neighbors only it is not for the total number of students available okay so this is how I can select the uh proper minimal amount of candies I need to give to the particular student okay so for this what you can do you can iterate over the total number of arrays total number of elements in the array I is equal to 0 to I is lesser than n and at each and every time you if you find this condition to pull true that I is greater than any of them okay any of them so what you'll be doing plus one to the number of candies of its neighbor will be assigned to ayathon and this algorithm needs to work until you see no change inside your array until there is no change until the array remains unchanged in any of the iteration after that iteration only you will end the while loop the outer while loop okay else you will keep on continuously applying the while loop so that is how the Brute Force algorithm can be implemented okay so that Brute Force algorithm will be let's say the outer loop runs K number of times and the inner loop runs n number of times so what will be the time complex it is the time complexity will be K into n and K1 can be as large as n so the overall time complexity will be n Square or more than n square right K value can be greater than n as well so the overall time complexity comes out to be K into n now what about the space complexity space complexity is nothing I am not using anything for the Brute Force approach so space will be constant over here but time is very much its exponential I mean not the it is quadratic okay so this approach might not work if K is equal to n If You observe what is the maximum possible number of n it can be as large as 10 to the power 4 so n Square will be 10 to the power 8 and it is possible that uh 10 to the power 8 number of iterations are not acceptable for this question okay write the algorithm name foreign approach so now what guys what you can think of so this is my hint for a better solution what you can think of Target on left neighbor for every for every student Target on left neighbor sort out things with the left neighbor first and then you can sort out these things with the right neighbor okay that means Target on the left neighbor it means that what I am trying to say over here the second Point Says student with higher rating gets more candies than their neighbors so that's this statement will be changed to student with higher ratings get more candies than its left neighbor so that is sorting out the things with left neighbor and sorting out the things with right neighbor means student with higher ratings get more candies than the right neighbor okay so I have divided the entire question into two different segments two different parts and if you solve for both this part you will eventually arrive at a minimalistic number of candies okay now when the session is almost over okay so if you focus on this thing that sorting out things with the left neighbor first and then sorting out things with the right neighbor first this is going to help you to think calmly so let's uh let me give you an idea about Target on left neighbor sorting out things with left number let's understand what it means with the help of test case two one zero three this is two one zero three now I will make sure that each and every student has who has the higher rating compared to left neighbor he is higher number of candies student with higher ratings get more candies than left neighbor foreign needs to be handled as it is one one one one everyone gets one candy student with the higher ratings get more candies than the left neighbor so each and every time I will simply compare with the left neighbor so zero does it have a left neighbor no one does it have a left neighbor yes so I need to check whether this is having higher rating than the left neighbor or not so do you think one is greater than two no so this is not having a higher rating so now the next one zero so do you think zero is having a higher rating compared to its left neighbor no so it does not have to have more number of countries now what about this three so do you think three is having higher rating than zero yes obviously three is greater than zero so sorting out things with the left neighbor that means this left neighbor has one candy so obviously this three needs to have higher number of candies so next large number the larger number after one will be equivalent to two so this will have two number of candies so say similar to this let's let's sort the things with the right neighbor zero one two and three this is two one zero and three foreign [Music] okay so starting with this one does it have a right neighbor no and each and everyone initially will be assigned uh one can be according to the equation at least one can be for each and every student so this one so zero is greater than the right neighbor no so leave it as it is so one is greater than the right neighbor yes so it should have higher candies than T zeroth neighbor right so plus one to eight so this will be equivalent to two so now coming back over here so 2 with its right neighbor 2 is having higher higher rating compared to its right number so a number should be greater than 2 with himself right so 2 plus 1 will be equivalent to three so three candies will be assigned to him and now this is the current number of candles so now with the help of this data try to think how you can achieve the finalized solution this was the hint for the optimal solution was it clear to everyone yes or no in the chat box if this makes sense okay any doubt anything from your end if you want to ask anything you can ask it right away [Music] yes and those of you who are trying to solve this question uh the last question let me paste down the uh link of this as well and put down your solution in the comment section and I'll be happy to read down your approaches right if you have any kind of different thought process or if you are able to figure out the solution with the help of this health do mention it in the comment section attach a link of your solution I will write it down okay okay so do you have do you have any kind of doubt you want to ask me anything or any uh uh anything that you can ask it right now I'm here for five minutes and then we'll end the session so for greedy do as many questions as you can no it's not the case for any of the uh for any of the uh topic or any of the topic of DSA it's not the case that you need to solve as many questions as you can the target should be you should know that why you are studying DSA you are studying for interview or you want to do competitive programming so there are completely two different paths interview Centric path then you need a perfect or a different strategy to look at DSA okay so you need to focus more on understanding standard algorithms properly and you need to focus on solving SD sheets as well okay I do like I have been giving guidance to students regarding how to prepare for DSA I have been telling to everyone that focus more understand more standard questions right you should have a better understanding of standard questions for every uh DSO topic because everything revolves around standard questions in interview and for CP there's a completely different approach right you need to know many different algorithms you need to increase your speed you need to try out as many questions you can right it's all about practice so will that do as many problems as you can works perfectly fine but in a specific manner not randomly choosing any question and just starting uh to you know invest some time on it okay okay I hope uh you guys enjoyed this session if you really enjoyed this session then do uh like this video and share it with your friends as well right and to comment down in the comment section if you you if there are any kind of views regarding this video I can do solve the last question it's very interesting and you will uh enjoy it a lot okay so let's meet tomorrow apart from DSA to get SD what are the things you need apart from DSA to get SD okay so apart from that you need a good communication skills like at least if you don't if you are not fluent at English it does not matter right if it fluency in English does not matter it matters that are you able to express your ideas right that is the other person able to understand your ideas or not that is one of the thing communication or expressing the ideas and working with the team is one of the non-tech thing which you need to have right you need to accept start accepting to work with uh the ideas of other people and other else apart from that projects are required if you uh if you are asking about technical part projects are required let at least few basic projects that says you know development okay so for Technologies whatever role you are applying for mention it inside your resume you can you already know what technologies or what are they expecting from the candidates so for Technologies you can do that thing and for resume shortlisting use keywords and for keywords you can look into internet or there will be many articles available that how to make your resume is shortlisted by the algorithm which uh filter out the resumes right so for that you can do that thing and project building projects should be written and there are many uh method of writing down the resume right so you should completely focus on keeping your resume short and crisp enough uh my third year finishes Wednesday I'm I'm planning to learn convertible how to get started about yourself and work means my third year finishes Wednesday I'm planning to learn computer program how to get started so the first thing is to learn about DS if you don't know DSA go focus on DSA understand every topic of DSA to standard problems there will be around 200 250 to 300 standard problems get it done understand all of them properly after doing so now you can shift to practicing DS equations okay after getting a practice on DSA question at least 200 questions more after that you can start completing programming that's what I suggest to everyone okay so uh so my name is a mentor at Geeks for gigs and I have been teaching students and I have been into ad Tech from past two years and currently I am working over here as a mentor okay [Music] so now I think we should end the session here only it was great interacting with everyone and I hope everyone enjoyed this session and do share it with your friends and do it in the upcoming sessions I will be taking the live session for tomorrow as well I hope this session was not at all boring did you guys found the session to be boring or was it entertaining apart from teaching what else I do okay so what apart from teaching in terms of uh job or profession or what else and if you have any kind of doubt you want to connect with me you can connect me on LinkedIn as well okay so I think it's a time we should end the session here only bye bye everyone good night and practice the last question so list of standard DSA questions can be found I am working at Geeks for geeks that's what I mentioned apart from teaching that is my profession right now okay so where to get standard DSA question you can take any of the website you can look you can write down you can Google it standard questions on DSA in gfg over there if you focus or if you will say greedy algorithms you will get a list of standard questions easy questions medium and hard do the standard ones okay over you okay so bye bye everyone good night it was great interacting with everyone let's meet tomorrow bye