CodeCamp Day 21 | Final Challenge Integrating DSA Concepts

Key Takeaways

foreign [Music] audible clearly hi Ram Chandra hi Pavan Kumar write down uh please write down why yes in the chat box if I'm clearly audible as well as visible okay thank you Okay so this is going to be the last day of our code camp and it was a very very great uh Journey interacting with all of you right and I have seen many of you have already been like following from the day one and it's a very good thing if you have been following from the day one hi pranjal hi okay so we'll be starting the session soon enough uh as it is going to be the last session we'll be having a lot of discussion with each other and I'll be uh like answering all your queries if you have any kind of queries yes I am Gujarat I'm from Gujarat okay so uh we'll be like I want to keep this session very much interactive I want everyone to like if you have any kind of doubts you can post it right in the chat box so basically this session is going to be more like interactive session rather than just simply solving the questions I am just discussing how to solve each and every question right so I'll be discussing like say uh just like the previous session I'll be discussing two questions right now and I'll be giving you one in the uh homework to all of you but at last session I guess Pawan you have been following from the day one right I'm starting from the first day but College Works session attention it's very hard to maintain consistency I also agree with you if you've been like uh working professional or like simultaneously going to colleges right good but then also then you have maintained the consistency it's a good signature like you are willing to learn DSA right so I'll be sharing my screen and I'll be uh starting this session so first of all before starting the session I would like to know do you guys have any kind of queries regarding any how to prepare for DS anything I'll be more than happy to reply and have a good conversation with everyone okay so uh so what will be uh what is the position education Adu okay so you can follow let's say if I I can tell you about the interview part basically if it the interview is going to be around DS then what you can do you can prepare uh interview Centric questions right you can follow any kind of SD sheets and do not jump here and there between different different SD shirts right keep on consistently following one HD shape and that will be more than enough and simultaneously participate in uh weekly coding contest dealing daily problem of the day and something like that playlist the entire playlist of the code Camp is available on the Xbox YouTube channel you can also like let's say if you are attending the session for the first time you can start the code camp or let's say you can start this trick starting from the day one watch the session on the first day keep uh keep on practicing the homework questions and you can follow the uh the code camp at your own pace as well right so the entire playlist is available so preparation resume how can you regarding this part okay so if resume shortlisting then what you should do basically there is a possibility like let's say for applying for a back-end developer role and inside your assume you have mentioned anything about back-end technology or anything right basically if you don't do such kind of thing if you don't mention any of the keywords related to that specific uh profile then your resume it is possible that your resume not might not get shortlisted okay so try to add keywords to your resume and uh see resume shortlisting it takes lots of effort you need to con consistently keep on applying to let's say five to seven companies each and every day at least at the end of the week you will be getting calls from one to two companies right that is how you hunt for a job okay uh vaishnavi vaishnav is the is this playlist uh enough to revise TSA DD 21 days yes you can use this playlist as a revision part as well because each and every DS topic starting from Basics to Advanced have been covered over here and the standard problems as well as the interview Centric problems have been covered so you can take this entire playlist as a revision as well okay okay what are the good projects for data science Rules okay so regarding data science role I will not be able to uh answer very nicely so regarding DS or anything our interview Centric I'll be more than okay so now let's start without without any delay I'll be discussing the question and I'll be sharing the link as well okay and uh in between the session let's have a communication right so let's make this such an interesting okay I hope my uh screen is visible to everyone okay so just a minute let me open this stream as well okay thank you Bhavan can't able to solve simple error questions don't worry unit practice you need to solve standard question first of all and then you can solve the other uh questions okay so the first question is equilibrium point okay so before directly going to the question I would like to explain you uh different like let's say a new topic to everyone and the modification or the uh usage of that topic will be done in this question okay so let's start so the topic which I'll be discussing today is prefix some array okay have you heard about the uh word prefix can anyone from the audience write down what is what does it mean by prefix or let's say if I if I have given you a string something like that or let's say if I have given you an array and now in this array if I am saying that I want to uh if I'm targeting this array containing 2 and 12 what does it mean it means it is a prefix of this array right similarly inside this string if I am saying that this string a b it is a prefix string for this string right and if I conclude if I include only the alphabet a then and also then I can say it is called a prefix string basically uh if you start including the element starting from the zeroth index then that means uh you are targeting the prefix of that array or of that string so now over here let's say if I give you an array one two three four five and six so now what I'll be doing I'll be creating this is the input error given to you and now based on this I'll be creating one more error that is called the prefix array so what does it mean the prefix array so what I'll be doing basically I'll be creating a prefix sum array just give me a minute okay so basically I'll be creating a prefix sum array of it what does it mean prefix sum we have seen the word prefix we need to know what is prefix sum so basically in this array prefix what I'll be doing at each and every index I'll be storing the sum of all the elements starting from the zeroth index till the ith index okay currently my I is standing over here so what does it mean I need the sum of all the elements starting from the zeroth index till the index number zero okay so that means only one element will be included now I'll be taking my pointer I forward it will be pointing to this index number two it's a 0 1 2 3 4 and 5. any doubt till now yes exactly yes that was quite quick enough so now now currently I'm standing at the index number one I need the sum of all the elements starting from the zeroth index till the ith index so that means some of this many elements 1 plus 2 will give you two now for this second number uh index number two what I'll be doing I need the sum starting from zeroth index to the index number two that is one plus two plus three that will be equivalent to six now for this starting from zeroth index till the index number three that is one plus two plus three plus four or what I can do I can add this sum that is one plus two plus three it is present at this index plus this element 4 6 plus 4 will give you ten now for this index I can add 10 and I can add 15 that will be giving you 15. and for the last index I can add 15 and 6 that will give you 21 basically at each and every index inside the prefix uh some array the value present let me write down the definition what value will be present at each and every index so basically inside the prefix array prefix of i it is equal to the sum of the elements starting from the zeroth index to the ith index in the input array okay I can represent the value present at each and every Earth index in this manner is it clear the idea about prefix array prefix some array is this clear to everyone yes or no in the chat box a quick uh reply from everyone this topic this prefix some array will be used in many medium to hard uh kind of questions okay so this topic is very much important to understand a quick reply from everyone whether this was clear to you or not okay thanks Pawan thanks for the confirmation so now similar to this what do we have we have something called as suffix sum array what do you understand by suffix summary okay what does it mean by Sophie summary can anyone guess what do you understand by suffix it will be something opposite of prefix sum right so now let's say I'm creating a suffix summary so what do you mean by suffix summary a reverse order of preview prefix sum okay sorry does it mean if I reverse this entire array 21 15 10 6 2 1 and if I store this value will it be the suffix sum no it won't be so basically this is reverse of the prefix sum how is it reverse actually it's reverse means that it will be containing the sum of the element starting from the last index okay so basically let's say if this is the definition of our prefix sum then suffix sum will say that suffix of I is equivalent to what it is equivalent to the sum of the elements starting from the last index and last index is n minus one of the index it is n minus 1 of index and till the Earth index so let's let's start from the last uh index for the last index how many elements are there from n minus one ath index to the till the current index how many elements are there only one element that is six now for this what will be the value sum of all the elements from last till current index 5 plus 6 will give you 11. now for this what will be the sum it will be 5 plus 6 plus 4 or you can say 11 plus 4 that will give you 15. now for this one it will be 5 plus 6 plus 4 plus 3 or you can say fifteen plus three it will be equivalent to 18 and now now for this one that will be 18 plus 20 18 plus 2 will be 1 to 20 and for this one this will be 21. okay it is not exactly reverse of this prefix array but somewhat values will be similar that is the last element and the first element of prefix and suffix will be equivalent because the last element of prefix denotes the sum of the entire array and the first element of suffix denotes the sum of the entire array was this part clear prefix sum and suffix sum is this part clear to everyone yes or no okay thanks for the information okay so now let's move to this question and understand what does this question would say okay so I'll be giving you five to like say uh four to five minutes to read out the problem statement I'm sharing the link of this question in the chat box okay so try to read down the problem statement and try to understand what does it mean okay sorry down the problem statement go through the examples as well and just write down yes in the chat box if you have gone through the question okay this is also one of the uh like whatever we learned right now prefix some suffix some something can be applied over here okay that was an uh that was a hint from my end have you gone through the problem statement how many of you have read the problem statement there are only two lines I guess everyone has read yes or no quick response from everyone if they have uh if you've read the problem statement okay thank you arushi for the confirmation and one more okay so let's start so what does it mean so uh the question says that first of all the name of the question is equilibrium point and the difficulty level States easy okay and why is it easy you will understand see if you haven't heard about perfect sum or suffix sum then this question might be difficult for you because the expected time and space complexity requires the knowledge of prefix sense of exam okay so now over here in this uh in this question you will be given an array of positive in a positive integers okay and the task is to find the first equilibrium point in an array what does it mean by equilibrium point so equilibrium point in an error is a position such that the elements before it is equal to the sum of the elements after it basically if I say the index number let's say three in some array is the equilibrium point then the sum of the elements from 0 till 2 and some of the elements from 4 till n minus 1 will be equal that is what the question is trying to say problem statements clear try to solve okay sir if any if and I what education need okay so now let's try to just quickly go through this example okay so here is our example inside this example we have an array that contains elements 1 3 5 2 and 2 okay so now I want to find the equilibrium point equilibrium point means let's say if I am saying that this Index this point is the equilibrium points and then what else I need I need the sum of the element on the left hand side three plus one will give you 4 and the sum of the elements on the right hand side two plus two will give you four so exactly yes I can say this is an equilibrium point because you can see left sum and write some are equal right so now what about the other point let's try to see the other points let's say if I'm saying that this point is an equilibrium point what does it mean so it means the sum on the left hand side is equal to 1 on the right hand side it is equivalent to 9. are they equal is one equal equivalent to 9 no it is not equivalent so 3 this position is not the equilibrium point so basically in the question what you have to do you have to find the first equilibrium point in an array so for this input the output comes out to be index number okay so indexing uh according to the error indexing will be one based indexing for this question the indexing will be one based indexing it is mentioned over here uh as a node the written the index of equilibrium point one based indexing so what will be the index 1 2 3 4 and 5 answer the output 3 will be printed is the question understanding clear to you odd then how will how we will add before and after see now I guess this part was clear to you uh education edu was this clear to you is it clear yes or no education edu is it clear your doubt so now try to think as I've explained the problem statement now I expect after understanding prefix sum suffix some now I expect from you guys what can be the solution right can anyone say The Brute Force solution let's directly go through the Brute Force quickly and till then you can think about how you can use utilize prefix sum and suffix some array okay that was that was the hint from my end rest of the people who already have understood the brute force uh who have not understood the Brute Force Focus over here okay so what will be the Brute Force approach Brute Force approach is pretty simple what I'll be doing I'll be having one of the iteration over the entire array starting from this index now at it at each and every index I'll be running a loop on the left hand side starting from I minus 1 with index till the 0th index and I'll be running the loop on the right hand side starting from I plus 1 with index LD last index that is n minus one nothing X so running a loop on the left hand side of this one will be having sum 0 and now running a loop on this right hand side that will be three plus five eight plus two ten plus two twelve right so I got the left sum and write some zero equivalent to 12 no it is not equivalent right so uh the index one is not our equilibrium point so let's see the other part this position so left some run a loop from uh one to the index number one so one element will be there run a loop from three to last and x 5 plus 2 plus 2 that will be equivalent to nine sum will be this is not equal right one is not equivalent to nine so basically this approach can be applied as a Brute Force approach in which the outer for Loop will run on the total number of elements and there will be two inner for Loop which will be running for the left sum and the right sum and the overall time complexity for that approach comes out to be order of n Square that was the basic root Force approach and the space complex it will be constant because we don't need any kind of extra space to store the sum or anything right so what about the hint I gave you uh pratik says for Brute Force for every position add some on the left and right exactly yes so uh what do you think what can be the utilization of this prefix sense of exam so now let's understand what if I have the prefix array what if I have the prefix array and the suffix array for the given array let's find the prefix sense of X array okay so prefix array 1 1 plus 3 will be four four plus five nine nine plus two eleven eleven plus two thirty and what about this suffix array starting from the last index that will be 2 2 plus 2 4 and 4 plus 5 9 5 plus 9 plus 3 will be equivalent to 12 and 12 plus 2 will be 13. I have suffix and prefix array okay so we got an answer pratik say is find prefix and suffix sum and for every check if they are equal for every position check if they are equal okay so let's understand now I have the prefix sum and the suffix so now I'll be trading over this entire array prefix or suffix simultaneously both of them okay now let's say currently I'm standing at this point I am saying that this point is equilibrium point how can I argue that so basically I need this sum on this left hand side and I not need this I'm on the right hand side so what will be some of the elements in the input array in the input array I need this sum actually right and this sum is present at the index number 2 inside your suffix array so I'll be fetching this value so let me just change the color so so I'll be getting this value and now I need the sum of all the elements this is my current position I need this sum that is from uh index number one to the index 1 minus zero one minus 1 that will be from 1 to 0 this is not possible so the sum on the uh left hand side will be equivalent to zero so I got two some left sum is this and a right sum is equivalent to 12. this is not equal right so this is not the equilibrium point so basically I am I have tried like basically we have eliminated the loop which we were using to find the left and the right sum so now moving on forward with the index number 2 index number two I am saying that this index is equilibrium but I need this sum this sum is present at this index at the index 3 in the suffix array and this entire sum is present at this at index one in the prefix array so is one equivalent to nine no it is not equal so this point or this position is also not an equilibrium position so moving on forward uh at this index index number three let's see if this is equilibrium point I need this sum this sum is present at which index at index 4 inside your suffix array and this sum is present at which index index number two inside your suffix array so this is what we are going to compare so is 4 equivalent to 4 yes or no in the chat box yes obviously a very easy a question right is it possible with uh two pointers Can You Solve IT two pointers approach C two pointer approach is required to look for an element what kind of element that adds up to some kind of sum or something right so two pointers approach will not iterate over each and every left and right sum for each and every index but over here you will be able to do so basically you need to test each and every index and two pointer approach is optimization and it requires no iteration or repeated iteration right so that's the reason you cannot use two pointers approach because we over here we are not looking for any key element or any double elements right we are not looking for any pair of elements is this clear to you everyone yes or no aware or who are here after day one I am here after day one Okay so so let's start again okay so is this part clear to you yes or no quick reply from everyone is if this part is clear to you foreign okay thank you for the confirmation now we know how to generate prefix array okay so let me show you how to create prefix area Okay so let's say I have created an empty array that goes by the name prefix and its size is equivalent to n and all the elements are equivalent to zero so now I'll be running a loop on the index number one starting from index number one to index lesser than the last one okay and now prefix of i is equivalent to what if x of I is equivalent to the element plus what prefix of i minus 1. prefix of i minus 1. this is how you generate an enter prefixer and what about the suffix array and one more initialization step is required because for the prefix of 0 we know that the element is going to be equivalent to the element element at the index number zero so the initialization step is going to be this that prefix of 0 is going to be array of 0. now what about the suffix array suffix of n similar to prefix of n what I can do I can write down suffix of suffix array starts from the last index so last index will be initialized n minus 1 is equivalent to array of n minus 1 and now I'll be iterating I will be it I'll be iterating from which index from the second last index n minus 2 2 I is greater than or equal to 0. is it clear yes or no so now suffix of I is equivalent to what it is equivalent to array of is equivalent to array of I plus suffix of I Plus 1. right this is what the suffix of I denotes isn't it similar to prefix array right we simply need to have a clear understanding about prefix or suffix so this is how I will be generating prefix and suffix and how will I compare each and every point right I need to see whether it is an equilibrium point or not okay so what I'll be doing I will be running a loop on the so let me write down the steps of the algorithm okay we will optimize this algorithm as well okay so the first step is to generate prefix and suffix array right so after generating the prefix and suffix area what else I need I need to iterate over the input array I is equal to 0 to I is lesser than n and after this what I need to do I need to check what that ith element or ith position is my equilibrium point or not how can I do that I need the sum of the element from zeroth index till I minus 1 Authentics till the last index so this sum will be available at I plus 1 index inside your suffix array and this sum will be available at prefix of i minus 1. I am stretching a lot on this question because over here this question in this question a very important topic that is prefix sum suffix sum is being discussed that is the reason I am extending or stretching out more on the algorithmic part of this question okay till now is it making any sense to uh you guys is it making sense what we are doing over here yes follow in the chat box if this makes sense to everyone okay thank you for the confirmation now I will be iterating over each and every area element right starting from zeroth index till the last index now there is one catch right we know that I cannot find I minus 1 when I is equal to 0 and I cannot find I plus 1 when I is equivalent to n minus 1. for the last index I cannot find I plus 1 and for the first index I cannot find I minus 1. so you can handle this part separately or you can put two if it has condition like this if I is equal to 0 then you have to check what you have to check you have to check and so now if I is equal to equivalent to zero first of all let me have two different variables left sum and right sum so left sum will be equivalent to 0 and the right sum will also be equivalent to zero now if I is equivalent to zero I is equivalent to zero and I will be having no left sum if for I is equal to 0 no left sum is present so I'll be adding one more condition if the right sum or the prefix sum but I'll be doing suffix of I plus 1 if the suffix of I plus 1 is equivalent to 0 or not basically I am saying that left sum is zero now what about the write sum it will be present at the index I plus 1 I'll be finding it some I'll be calling it as write sum is this equal to 0 yes or no no it is not equivalent then let's say if it is equivalent then you will be returning the index returning the index basically I plus 1 will be written else if what else if let's say I is equivalent to n minus 1 Authentics last index so in that case I know that suffix of I plus 1 is not possible for this so what I'll be doing I'll be checking if prefix of i minus 1 because left sum exists right it exists at the index I minus 1 if this is equivalent to 0 or not then return I Plus one base indexing that is the reason I am returning I plus 1 else what else you have to check whether you can add else if else if prefix of i minus 1 I already have explained this part so not explaining it again and again and suffix of I plus 1 if this is equal then return I plus 1 directly return I Plus 1. and here is the end of our for Loop so this is the entire algorithm to solve with the help of prefix and suffixer any doubt till now pratik says can you list problems that require prefix sum after solving this I would suggest that go to the you can search for prefix sum and then write the keyword Geeks for gigs you'll be having a page that says prefix some details about introduction to prefix command some standard questions okay so focus on standard questions see directly no there are no questions which will be using prefix sensorfiction this is very few questions out there right so basically they will be utilized they will be used in a medium to hard level of questions okay and whenever any kind of question requires you to answer queries in constant amount of time and in such kind of uh questions where you require to have some in such kind of questions prefix and suffix can be used so now based on this what will be the time and space complexity what do you think what will be the time and space the algorithm is in front of you so read the algorithm and guess the time and space complexity order of n for both the pratik says order of hand province is order of n and what about the other people what do you think what will be the time and space order of n plus n yes exactly to be more precise space will be order of n plus n that is two arrays prefix and suffix array which are having size equivalent to input arrays used arushi says order of n yes and here is a for Loop a clearly visible for Loop that is going to iterate over each and every array element that is going to take order of n time and for generating the prefix array order of n for generating suffix area order of n that is time complexity can be written as order of 3 n and space complexity can be written as order of 2 N basically linear time in space complexity for this approach now I want to let's say I want to uh decrease the space complexity I don't want to create or generate prefix and suffix array can I do without generating prefix sense of X array try to think what actually we are doing over here is it always required to have a suffix array do you guys think that suffix array is required each and every time yes or no what do you think so let's observe something over here so over here no so Pawan says no and also do mention the reason that why don't we need suffix array okay so let's say I'm doing one thing what I am doing instead of this suffix array I will be having a sum variable that says the sum of the entire array the sum variable denotes the sum of the entire array so somehow let me show you in this part in this test case 0 1 2 3 and 4. now over here if I want to find the suffix let's say currently I am standing at this index so what I'll be doing I'll be having two different values that is some variable that will be initially equivalent to the sum of the entire array and let's say what is the sum it is equivalent to 13 I guess 5 plus 3 8 9 10 is on 12 and 13. at sum is equivalent to 13. along with this I'll be having one more variable that is prefix sum this are variables they are not and it is not an array prefix sum is initially equivalent to zero so now this sum variable will be helping me to find out the suffix sum and this prefix sum will be helping me to find out the suffix up so let's observe how can we achieve it currently I am standing at the index number 0. so now for this index what I need I need the suffix sum I need this sum so the first step is to whatever element You Are encountering For the First Time subtract that element subtract that element from the sums so that will be 13 minus 1 will be equivalent to 12. so this 12 which you have got after subtracting the current element is the sum of this part it is the write sum so after subtracting what else do you need you need to compare the prefix sum and the sum do you see sum and prefix sum have the same value no it is not having the same value so moving on forward now before moving on to the next element before moving on to the next Element Make sure you will be adding this element to your prefix sum so one will be added so prefix sum will be 0 plus 1 that will be equivalent to 1. now moving on forward with this now next element so on encountering a new element as I have mentioned you have to subtract that element from the sum so 12 minus 3 12 minus 3 will be equivalent to what 9. right and what else you have to do so first of all the first step is to subtract the current element this is the first step this is the second step second step is to compare the value of sum and prefix sum and the third step that is after uh before moving to the next position what else do you need you need to check what else you need what else do you need you need to add the variable to your prefixer add the variable to your prefixer this is very much easy to understand now I have encountered now I cannot see nine and one equivalent so I need to move forward so I'll be adding the element to my prefix sum so one plus three will give me four moving on forward this element so now first encounter so 9 minus 5 will give you 4. and what else now I need to compare this step 4 is equivalent to 4 yes exactly so this is my equilibrium point I think we can okay so Pawan says I think we can calculate uh when I'm iterating the array okay I missed so many chat okay so pratik says subtracting the subtracting form from Total will give the suffix a value at any position okay it's exactly maybe no not Milan says no and no one says I think we will go to my updating and then check if it was different okay so basically we simply can do this and achieve this with the help of variables as well okay so if you focus if you like pay attention to actually what is happening in your algorithm no you would be able to observe that something is redundant this data is not at all valuable in order to solve the current sub problem so you can get rid of those data extra data see in the prefix and suffix some extra things were stored right like if I was uh working on this element why I don't need any kind of this data this data is redundant right so we can avoid storing the uh extra data which we are not going to utilize anywhere in the question okay so over here we don't need any kind of prefix some suffix sum but the knowledge of prefix and suffix sum has helped us a lot to finally reach to a very efficient solution right so that is the reason I was paying more uh like let's say I was stretching out the topic of prefix sense of exam I guess you have understood the reasons okay so this way optimization and everything can be like you'll be getting an idea in this manner if you know actually what prefix sense of exam is okay so directly the in the interview as well uh they will not ask many questions having prefix suffix but uh let's say indirectly they will be using for optimization part okay so these are the steps now before this what else do we need I need the sum variable some variable equivalent will be equivalent to what it will be equivalent to zero till the last element that is n minus 1 array of I okay I'm writing down the mathematical representation using Sigma you can imagine this with the help of a for Loop right everyone is smart enough over here right so sum is equivalent to this now what what else do we need I need one more variable that is prefix sum and initially this value this variable is going to be storing zero prefix sum is equivalent to zero and this is the initial thing I need to do foreign can be included inside your for Loop so I'll be having a for Loop starting from the index number 0 to I is lesser than n last index so the first step is to get rid of the current element from the entire sum so I'll be getting suffix sum and luckily if I am able to find any of the index that says sum is equivalent to prefix sum just to directly return the value of that index return I plus 1 . okay is this making sense this is the efficient algorithm is it making sense yes or no any doubt anyone okay and so this is going to be our algorithm so let's directly code this part I guess uh this implementation can be done in any other languages I have written down the algorithm and we can do it but what about the variable data types so keep in mind that we need to use what kind of uh data types see in this kind of questions which seems to be very much easier just it is for being on the safer side just pay attention to the constraints okay every time pay attention to the constraints it is possible that you might encounter some memory overflow for some variables and that might lead to a wrong answer so I have good experience what mathematics needs for better okay so uh someone says I have good experience what mathematics needs for better I didn't get you uh can you be more elaborative or a phrase okay so I was saying about what kind of data type I need let's say I am creating some variable okay and I have a prefix some variable that is initially equivalent to zero now some variable is going to store be some of the entire array so at Max in the worst case what can be the value that will be stored inside my sum let's say I take a worst case example in which the RS size is 10 to the power 6 and the other elements are 10 to the power 8 each and every element now what will be the sum of that entire array that will be 10 to the power 6 into 10 to the power 8 10 to the power 8 right that will be equivalent to 6 12 14 10 to the power 14 will be the sum of that array inverst case and 10 to the power 14 cannot be stored in integer right so you need this some variable to have long data type and whatever the prefix sum let's be on the safer side and have prefix sum also with long data type so now let's start the iteration I is equal to 0 till I is lesser than n and I plus plus so the first step was to get rid of the current element from yourself but before that I need the sum of the array element all the array elements I is less than and sum plus is equal to array of I will be getting the read I will be getting rid of the first element array of I will be removed from the sum so this is my suffix sum now and if sum is equivalent to prefixer and directly return I plus 1 because that is your equilibrium point if this is not the case then what it's not the case you first of all need to add the current element to your prefixer so array of I will be added and at the end just directly return the value of what it is mentioned over here your task is to return -1 if no such Point exists so its for Loop will be executed and if nothing is written then you need to return minus 1. I have good experience uh in JavaScript what mathematics needed for DSA basically like are you saying that what mathematics do you need for DSA is this your question just write down yes if this is your question okay so compilation is successfully completed and let's try to submit it and you can see the uh problem has been successfully solved right see uh I got a question from thank you nagarjuna so he's saying that I have good experience in JavaScript or mathematics is needed for DSA I guess this is what you are asking right so see mathematics is not much needed for DSA if you are looking for uh going into computer programming then it is required very much mathematics will be included uh you will be reading out about let's say different different algorithm algorithms that will be directly the question and competitive programming can be directly from your mathematics right so for DSA a very little of DS is required just like Co fire does Genesis and prime numbers gcd such kind of mathematics a very small portion of maths is included for the DSA part I hope I was able to answer your question okay so now I want to announce something I want to share something with you guys okay it will be very much interesting for you as I can see the audience are very much uh active nowadays so I think I should share this right now So currently there is something going on at Geeks 4 gig so it will be starting from 1st of July and that goes by the name geek Olympics okay so what will be this Festival this is kind of festival at Geeks for gigs in which coders like you can participate in different different events right so you can register over here and it will be uh starting from 1st of July and it will be extending till 31st of July an entire month of this Olympics so what you what do you get there are different different events possible so there is something called as code extreme so basically if you explore there will be putd gfg weekly and you can go through this part what actually this event contains and the interesting part which you might be much like let's say you can attend these sessions the interesting part is that there are some lives sessions available so basically there will be live daily like uh study sessions 31 days 31 sessions the free opportunity for you to upskill master new technology basically uh industry experts will be called on the uh session and they will be giving you the reality they will be sharing you the actual thing about what industries ask your industry is looking for in the employees let's say XYZ technology like let's say Java back-end development right we want to know from the actual uh industry experts who have been working from years and years right and who have been working in a good product based company so they will be in the interview and you will be able to post your questions and they will be sharing the knowledge and they will be sharing you the path so this is the most interesting part you can check the other interesting things other interesting events as well okay I'm living this part of exploration on you guys and there are some prizes also available right so you can explore this page go through this page and also register it over here I'm already registered okay so Pawan Kumar is quick enough it has already registered good okay I'm sharing the link of it in the chat box as well it might help you and yeah I've shared the link in the chat box so now let's get back so uh was the question clear anything any doubt from anyone regarding this question equilibrium point else will be moving to the next question uh someone says when I am registered here after what I have to do here sir can you tell here so after registrating after registering over here Au will be like able to see different different events you'll be having the details let's see what else do we get okay so I have registered so after registration you will be getting notified on the email as well you can visit this page right so event has not yet started on 1st of July attend this and you will be able to see what all details are provided over here okay explore the event and let's click explore the event see the details are already given over here this is about the problem of the day now Geeks for geeks gfg weekly let's explore you'll be getting the weekly coding contest uh let's say God of problems let's explore this is going to be God of problems over here and let's see the other part live stage so this will be available the sessions will be available on YouTube regarding this so try to explore let's not uh spend much time over here so you get hired job Arena you can visit this and you can see the upcoming job posting over here okay I hope this makes it clear so now let's get back to okay uh what the future demand in software developer Okay so I will I I will definitely attend this session okay most welcome so the sessions will be starting from Tomorrow itself uh and I would like everyone who are attending this code Camp Daily and I want you guys to visit the I I want you guys in this session okay basically I'll be hosting one of the session on uh Sunday that will be on backend development if you guys are interested about back-end development and you want to hear from the industry expert uh what actually is going on in industry in the backend development and how what to follow and much more interesting things will be discussed right ah okay so I got one more in Python we have a collection data types like uh list the Pulsar dictionary is it necessary to learn DS like linked list stack queue yes exactly see in Python everything is like abstract you don't know the internal working this functionality is kind of a good part of python and it is also a bad part of python because if you directly start learning Python and if you don't have any idea how internally this data structures work then you will not be able to understand or implement it an interviewers want you in the understanding of this data so they don't directly want you to use the inbuilt functions and apply and build methods right okay so I see many of you are interested so do visit uh you'll be able like post your every doubts and every query over there and get the things replied from the mentor okay so let's start let's again get back to the question part okay so the next is a very interesting problem and a very famous question of Aries okay so I'll be giving you I'll be explaining this part this Credence algorithm in a very interesting way so that I will be able to guarantee you that in future you will not able to forget like you will not able to forgot this Cadence algorithm okay so I'll be sharing the link of this in the chat box a python framework for backend okay so according to me I would go for Java Java back-end development is very much famous in the industry okay I'm also interested in backend development uh which Tech used in backend okay so you can come to this session that will be for Java back-end development and in Industry Java is very much famous for back-end development and other Technologies are also famous I'm not saying they are the list common one I've shared the link of the question in the chat box start adding the problem statement I hope I was able to answer your question my favorite I'll go sir G okay so we got okay so Cadence algorithm is favorite for Pawan good okay so start reading the problem statement a very small statement is there in the question okay so let's start so Credence algorithm the difficulty level given to us is medium basically if you don't know the algorithm then obviously this is going to be difficult for you if you already know then you will be saying Okay so this difficulty level does not justify the equation right so given an array of an integers find the continuous sub array containing at least one number which has the maximum sum and return its sum okay and this is the example let's go through the constraint Eric can be as large as 10 to the power 6 so nested for Loop will not work obviously done to the power 6 and root and to the power 6 will be 10 to the power 12 that mean iteration is not allowable right and the array can be as large as 10 to the power 7. and minus 10 to the power 7 as small as minus 10 to the power 7. and go from node and something used in Java okay that's great you can follow that as well Pawan Kumar okay so now first of all before directly understanding about the ocean I want uh you to explain sub array is everyone aware about this word sober what does it mean by subarray because this has been very much confusing for lots of you okay so Subaru sabari is a contiguous part of an array with no elements or no nothing has been so now over here inside the sub array let's say if this was the uh error given to us in this array if I'm saying that I am saying that this is a sub array 5 10 and 9. extract the elements 5 10 and 9 this is a sub array if I say 10 9 and 1093 this is a sub array if I say 1 5 10 and 9 it is a sub array if I say five it is a sub air if I say 9 it is a sub array what if I say one let's say what if I say one and ten it is not a suburb it is a subsequence what if I say one and five and three this is not a sub array it is a subsequence not a sub-barrate is a subsequence I hope everything everyone for everyone it's clear what is this a Barren what is a what is not a sub array basically we need to know what is the sub variant what is not a sub array a contiguous part of an array okay so now I have to find out continuous sub array which has the maximum sum and inside the Contigo server at least one element needs to be included and over here the array will contain positive as well as negative elements right obviously if there are only positive elements now then obviously just that it will return the sum of the entire array gotting are you getting my point if there are no negative elements then there is no need of doing anything just directly return the sum of the entire array and that is the uh maximum sum right Indigo sub array which has the maximum but there are negative elements present over here so how will we solve this let's see let's see the example number one it says one two three minus two and five so that says one two three minus 2 1 and 5. 123 one two three minus 2 and 5 okay minus two and five so n is equivalent to 5 and for this I have to find out which submar is maximum sum so one of the approach can be I can find out all the suburb is 1 1 2 1 2 3 1 2 3 and minus two and the other one is one two three minus two and five this can be the sub array starting with index 1 that is the first index now I am writing down the list of the software starting with the index number uh starting from the index or the element number two these are the sub arrays and now all this over is starting with element three all the sub arrays starting with element number minus two all the elements all these are very starting with the element five I have listed down all the sub arrays so this will be having some 1 3 6 let me change the color this has some 1 3 6 and this will be having four as the sum this will be having 4 plus 5 9 as the sum this will be 2 5 and 3 and this is eight this will be having three minus two one three minus two one five six minus 2 and 5 minus two three and this is having some five now what is the maximum from all of this I can see 9 hence the output for this comes out to be nine let's see and output comes out to be nine and these are battery contains the entire array one two three minus two and five yes exactly what we got right now is the question understanding clear to everyone what actually uh we have to do a quick response from everyone if this part is clear yes or yes or no in the chat box okay confirmation from million what about pratik what about everyone else Pawan Kumar 21 already has learned right arushi confirmed that the confirmed okay so now what I want the reply from you guys what can be the Brute Force approach I guess the Brute Force approach is in front of you isn't it and The Brute Force approach what you can do you can find out each and every sub array and for each and every software I get the sum of these of that sub array keep a global answer variable keep on comparing the sound with your answer variable one initially answer variable will have minus infinite right 1 minus infinite which is greater one and the other one I got will be 3 which is greater 3 is greater 3 and 6 which is greater 6 is greater so three six and four which one is larger 6 is larger so answer you mean six as it is and 6 and 9 which one is the larger one nine so nine is present over here so in this manner I can find out the maximum sub array sum this is going to be my glucose approach right so what will be the like let's say this time complexity will be very much like it will be uh somewhere around n Square I can take it as n Square for each and every element you will be going through it will be basically quadratic time complexity will be uh reached by the Brute Force approach okay so now I want to do something better than this I want something better than this so what I will be doing C over here these are different different sets just give me a minute let me reopen this OneNote okay so now what Over Here If You observe I have written down the sub arrays uh in sets right so this sub array set contains all the elements starting with the first Index this sub array set contains all the elements starting with the index number one two three and four this is a set containing all the sub arrays starting with the index number two this sub set contains all the elements starting with the index number three and this is for the last one fourth index so what I can do actually instead of starting from the first element I will be keeping track of the maximum Subaru sum ending at the ith index so basically what I'm trying to see if I am saying that I want to find a maximum subaruism ending at the index number zero so how will I get I am saying that maximum subaruism ending at the index 0 that means the last element is compulsory you have to include the current element inside your sub array including the current element inside a sub array what is the maximum sum of some among all these are batteries so for that I can get the answer as 1. because only one element is required now what is the maximum sub array sum ending at the index number one that means last element will be the part of your sub array so what are somewhere is ending at index number two at index number two two element itself is ending and the sub array 1 2 is ending so what is it sum it's sum S3 what is it sum it's sum is two so this will be which is maximum one three and two the maximum one is equivalent to three so now over here for this element I'll be doing the same thing maximum Subaru sum ending at this index at the last index so for this one the element the sub air is ending at the index number two are three you can include two three you can include one two and three okay so I've included one two three it will be having some six five and three what is maximum so the maximum is six so now I have understood what is maximum subaruism and ending at the higher syntax now how quickly can I find this value how quickly can I find this value was the part uh was it clear to you regarding maximum sub array sum ending at the ith index uh is it clear for all of you is this part clear what is this value 1 3 and 6 is it clear okay keep the sum as we move along the array change maximum if required in case we reach negative or zero start some for that position and move forward yes that can be one of the cadets algorithm but I want I'm explaining it in a different manner you are exactly clear uh you are exactly correct pratik so I will be finding maximum sub array sum ending at the ith index so now I was talking about this index now I want to find maximum submarism ending at this index at the index number three how many sub arrays are ending at this index so sub array minus two sub array 3 n minus 2 so 2 3 and minus two so one two three and minus two this many sub arrays are there right so I don't need each and every sub array see if I'm going to find all the sub errors ending at the Earth index then what is the difference between the Brute Force approach and my current approach there is no difference you know right so basically actually I need maximum sum right I need maximum sum from all these sub arrays so what I can do see for this index number two I have got the maximum Subaru sum ending at the index number 2 as 6. and now I am finding the maximum Subarus I'm ending at the index number three so what I can do in order to find directly the value in this I'll be utilizing the value 6 so the value 6 says that starting from the index number zero till index I minus 1 the maximum Subaru sum whichever sub error you are including that is ending at I minus minus index has some 6. now I want to find what is the maximum sub array sum ending at the ith index so what I can do either I can add 6 Plus array of I that means this sub array I need to compare the value of this sub array or I have to Simply compare the value of the single element in itself these two values needs to be compared only these two values are required this two this this values are not required because previously I have got for the index number two I already have maximum of some ending at the index number two and that value was 6. I I my task is to find maximum sum so for index i1 I minus 1 I have answer is six now for index I if I want the answer I'll be adding the element uh array of ith element to 6 or I'll be considering array of I in itself because these two sub arrays are not been uh concluded are not been included all this will not give you any kind of Maximum answer then we have excluded it in this manner okay okay so Pawan are you leaving okay so sorry presentation so do what the recordings and I guess you have already learned curtains algorithm right so you can yeah but do come back again to watch what was the question I have given you in the homework okay you're going to continue or you continue your work okay so for the rest of the people is this part clear all right you are also everyone is saying bye okay bye bye everyone say bye to Pawan [Music] okay so uh I was saying that is this part clear regarding this is this part clear that how to find maximum Subarus I'm handing at the Earth index I will utilize the value which I've already calculated for I minus 1 of index okay I'll utilize the value I'll utilize the value which I've already created I have already already calculated for the previous index so now for each and every index if I want to find the uh so what I'll be doing in order to calculate this value first of all I will be finding out what is the maximum Subaru sum ending at is index for each and every position okay so let's start so I'll create one more array and that array will be utilized to get the idea about the sum of the maximum sub array adding at the ith index okay so zeroth index one of the index 2 is index three and four so for the first one if I want to find the answer basically I will be adding let's say I call this array as let's say what do you want me to call this array as let's say some array okay and for any of the position for any of the position sum of I is equivalent to what sum of I is equivalent to a maximum of maximum of sum of I minus 1 plus the current element because only two sub arrays will not be included that is the reason I am calculating these two values or the current element as a sub array itself so this is what I am going to store at each and every index and along with this I will be having an answer variable which will be initial equivalent to minus infinite so now let's begin let's start so starting from the first position so for the first position we know that nothing is present on its left hand side sum of I minus 1 is not possible so what I will be doing for the first index I'll be putting 1 as it is I'll be putting one as it is now I have got one of the uh answer right that is maximum Subaru sum ending at the 0th index that is one compare it with answer variable which is larger obviously one so answer updated to 1. moving on forward next what is next next is index number this one so I want to find maximum sub address I'm ending at the index one so that is sum of I minus 1 that is 1 plus current element 2 and comparison with The Elements value itself that will be comparison between three and two what is maximum I can see three so sum over here I'll be storing three compare with answer N3 3 is obviously greater update the answer variable moving on forward for this one for this element for this element I want to find so I'll be getting sum of I minus 1 is equivalent to 3 3 plus current element is 3. and current element maximum of this 2 will be equivalent to 6 comma 3 and is equivalent to 6 so at this position I'll be storing 6 answer and 6 which is larger uh 6 is large update the answer moving on forward with the next index index number three for the index number three I will be doing the same thing and the same thing is a maximum of sum of 6 plus minus 2 and array of I that is minus 2. which is maximum that is comparison between 4 and minus two four obviously so 4 will be stored over here and what is the uh should I have to update the answer variable 6 and 4 no no updation is required so moving on forward next element index number four and now for this what I need to do maximum of sum of I minus 1 that is 4 plus current element is 5 and the current element is 5 itself comparison between 9 and 5 what is maximum 9 so 9 will be stored over here and compare 9 and answer variable answer variable will say 9. now anything remaining no other elements are remaining hence the output comes out to be answer and that is 9. is it clear this uh process this algorithmic part is this clear or not yes or no we need a proper understanding of this process because from this process you will be able to understand Credence algorithm okay if you have any doubt in this process then do mention it right now okay I don't want anyone to stay confused in the Credence algorithm just quickly write down yes or no in the chat box if this approach this part was clear to everyone okay so I got one answer from Milan what about other else other people pratik arushi [Music] is it clear to everyone okay Milan and pratik says yes so now let's try to convert this into algorithm okay so the algorithm looks like this okay so now let's start let's understand this looks nice huh is it looking good sir we can can we connect with you after this classes are completed yes you can connect me over LinkedIn as well you can look for jazz alsanya and I will be like replying you if you have any queries you can ask me over there as well okay you can find me on LinkedIn okay so now let's uh write down the algorithm so algorithm is what first of all I need some variables so the first variable is what the first variable is the sum variable so I need a sum variable I need the sum array I need the sum array and I need an answer variable so first step is to get an answer variable answer variable will be storing minus infinite initially and I need an array that goes by the name sum initially it should be equivalent to uh it should have size equivalent to the input array and all the elements should be having zero the initialize initial the anti-sum array should be initialized with zero and after this what else do we need for the zero syntax as I mentioned initialization step can be considered so for other part sum of 0 will be equivalent to array of 0. now for the rest of the indexes I'll be iterating from I is equal to 0 to so for I is equal to I is equal to 1 2 I is lesser than n now what I'll be doing I'll be simply copying these steps sum of I is equal to maximum of sum of I minus 1 this area of 5 plus r of 5. this part and what else I after calculating sum of I I need to compare that value with what I need to compare that value with answer so answer is what answer is maximum of answer and sum of I and the last step is to print the value of the answer variable correct so this is the entire algorithm now this algorithm what is the time and space complexity let's observe over here Order of one order of one order of one this will be taking order of end time anything else this is constant this is also constant nothing else so the time complexity is constant I mean it is linear not constant time complexity comes out to be order of n what about the space complexity over here constant over here Order of n constant nothing else right so the space complexity comes out to be order of n over here nft yes see there are two nfts then so this and other one as well which one is better what do you think is this one better or this one this one which one is better write down in jet box one or two okay okay so now this is my time and space complexity so will this algorithm work yes absolutely this algorithm will work do you want me to see do you want me to code this part auction okay so pratik says to Milan what are you voting for you are voting for to this one algorithm this part I guess this is far better this one it seems to be like 3D kind of I guess [Music] okay so now let's uh quickly code this approach this is not actually the Cadence algorithm but the concept of a used over here that is finding maximum uh like finding the maximum banding at the Earth index that concept is used inside algorithm okay so let's quickly code this approach and let's see if this approach gets accepted or not okay this is not the final cuttings algorithm you will be still optimizing it okay so now here is the answer variable so again regarding the data type regarding the data type we need to okay so everyone says to okay okay so regarding the data type what will be the data type of our answer variable let's say I'm initializing it as minus infinite answer variable what will this answer variables do it is possible it can show the sum of the entire array so now again seeing what can be the sum of the entire rate and to the power 6 into 10 to the power 7 12 plus 1 13 it can be as large as 10 to the power 13 so it won't work and data type will not work so let's keep it as long and what else do we need I need a sum array so is it after this let's observe the algorithm okay one by one so initialization step the first step sum 0 is equal to array of 0 Let's initialize see the process see the way I am coding you know see first of all what was my Approach I was going through the problem statement and then I thought of brute force and then I optimized it and then see the most important part which I uh suggest every student is that have the habit of writing algorithm in this manner first of all note down the algorithm uh on your pen or on your copy and then only then start coding okay so if there are going to be any kind of mistakes any logical or anything or any part will be missed you will be able to observe in the algorithm written in your notebook itself and directly debugging the code is very much stressful and it is very much irritating it was for me back then but now I have the habit of doing the code in this manner okay so I suggest you guys as well follow this process try it once you will be seeing the uh benefits of it so now iteration is required I is equal to 1 to I is lesser than and I plus plus and what is this step sum of I is equal to maximum of sum of I minus 1 plus area of I sum of I is equal to maximum of sum of I minus 1 plus array of I and array of I now I need to update the answer variable answer and sum of I and at the end just return the value of the answer variable this is the entire code for the algorithm which we saw right now let's see compilation error no compilation error let's try to submit and see if it gets accepted time and space both of them are linear order of n okay we got a wrong answer why is it so minus 1 minus 2 minus 3 minus 4. okay so see over here we did a minor mistake are you guys able to observe the minor mistake which I did over here okay code debugging skill debugging is also kind of skill okay are you guys able to observe that why I am I getting this wrong answer so this test case I need I made a minor mistake and some initialization part I made a mistake in this three lines okay let's see if you guys can figure out if you guys can find the mistake which I did over here this is the test case minus one minus two minus three minus 4 output is minus two according to my code but it should be it should be -1 what mistake uh did I make over here in this three lines 42 43 and 46. anything any anyone anyone a small mistake is there I'll explain the reason of this thing see the initialization part sum of 0 is equivalent to array of zero I have initialized the sum of 0 as I have zero now sum of 0 if let's say the first element is your output just like in this test case the first element itself can be concluded as a sub array and its sum is -1 and it is having the maximum uh sum right so over here you can observe in the output the sum in the output the we can observe that the correct output is the first element and the code is giving us minus 2 so answer variable should be initialized to let's say the maximum of any obviously anything is going to be greater than minus infinite right so it can be initialized as array of zero instead of keeping it as minus infinite now it will work perfectly fine let's say do submit directly and the problem has been successfully submitted okay so we got replies sum is equal to answer Dinesh and some yes exactly Milan you got it initialization initializing long answer no okay my Milan got it right uh Dinesh you didn't got it kind of sum is equal to answer sum is an array cannot initialize or give an array is anything hi I okay so now I want to optimize it a little bit okay so this is my time and space complexity I need to optimize it little bit how can I do it so where do you think the optimization can be applied uh can I optimize the time complexity can I optimize the space complexity I can somehow optimize the space complexity time complexity at least you need to iterate over the array at least once no this is not a quadratic time complexity or not anything exponential at least a linear time complexity is expected from you expected from the approach so time complexity no reduction space complexity definitely I'll be able to reduce the space complexity can you explain that error Thing Once More yes arushi see the error see initialization is answer has been initialized as minus infinite and what I did sum of 0 was equivalent to array of zero that's perfectly fine initializing the uh zeroth index of sum array as array of 0 but what if in this case just like the example or the test case for which our answer was wrong so in this kind of in this kind of test case your sum array will look like this minus 1 let's say something something okay I am not calculating the entire area so basically the answer is this sub array the answer contains only a sub array containing minus one so basically whatever is the value stored at the zeroth index was not at all compared with your answer variable it was not compared with your answer variable so what I did I initialized the answer as array of 0 because answer was initialized as minus infinite and anything is going to be lesser than minus infinite so I have compared answer with array of 0 or sum of 0. or you can add this part as well simplifying it to the ground level okay see for the zeroth index we were not comparing it with the answer variable that is the reason we were getting wrong answer because the for Loop starts from index 1 and ends with the last element so for zeroth index we were not comparing it with answer variable now if the comparison is done then each and every element is being compared hi yes pratik says since we only need the previous sum we don't need an array exactly that is what the Cadence algorithm is okay so now let's understand what Karthik is trying to say okay let's see see as I mentioned time complexity no reduction can be done space complexity definitely can be reduced how let's see see if You observe over here no let me point out this is the sum array which is occupying order of n space so do you see the use case of any other element of your summary let's say uh while finding while calculating the answer for this array let's say uh at some point this was the condition and now I wanted to find the maximum surprised I'm ending at the index number four so some of 4 will be equivalent to what it will be equivalent to maximum of sum of I minus 1 that is 4 4 plus array element that is 5 and the array element maximum of this two so do you see that this elements are being used anywhere for calculating the last some value do you see this elements are being utilized anywhere else do you see the use case of this elements no I cannot see so what if I somehow keep the track of the last sum of I every time what if I keep the track of this sum of I somewhere in some variable then I can get rid of the sum array itself I can get rid of this summary itself so that is how I'll be optimizing the algorithm is it clear is it making sense is this making sense yes or no or uh do you want me to explain explain it again okay clear to Milan what about other else okay clear to arushi what about pratik pratik already got the idea a Milan also clear okay so I don't think I need to explain it again so let's uh reflect few of the changes in this algorithm so now completely eliminating these some variables I mean completely eliminating the sum array so instead of the summary I will eliminate it as an array and keep it as a so the sum will be equivalent to what sum will be equivalent to zero initially let's say let me make it clear let me clean this okay sum will be equivalent to 0 initially now sum of 0 is equal to error of 0 this step is not required so sum of 0 is equivalent to zero now answer will be yet answer will be compared okay answer will be what yet answer will be maximum of answer and array of 0. this is I am going to do it for sure now over here this Loop starts from index number one so what I can do if this Loop is starting from index number one your sum will be equivalent to array of zero y error of 0 because every time I need sum of I minus 1 and for the index number one I need sum of 0 and we know what is sum of 0 it is array of zero so some variable is capable of storing the value of sum of I minus 1. okay so initially some variable will be equivalent to zero area of 0 because my for Loop is starting from index number one and answer has been updated or you can keep the initialization part of answer to array of 0 over here itself okay so this part can be eliminated as well now it looks more clear now sum of I has been removed so sum of I is not an array it is a variable so remove it is equal to maximum of what it is maximum of sum of array of I plus array of I and over here eliminate this this is optimization of our algorithm space has been optimized to constant order of one wasn't it very simple now do you do you guys see that Cadence algorithm is very easy to understand yes or no is this clear to everyone a quick response from everyone if this was clear so let's reflect these changes in our algorithm or the code which we wrote previously right so let's reflect these changes so long sum is now not an array it is a variable now sum of 0 is equal to area of 0 this is not required so sum of 0 is equal to area of 0 will be initialized over here and answer will be initialized as area of 0. so now answer is equal to Method Max of this step is not required now sum of I minus 1 will be now sum and this sum will be equivalent to some variable itself and this and let's try to compile and run yes some arrays was never needed it's exactly roshi see this works completely fine now also and now let's try to submit it again and the problem has been successfully submitted right see this is order of one space complexity time complexity remains as it is time complex it is still linear and this is actually the Cadence algorithm so if I want to give you a key point about Credence algorithm that is you should remember that how to find maximum subaruism ending at the ith index maximum Subaru sum ending at the I Authentics see if you remember this point for Cadence algorithm never in future you will be able to forget credential okay you will not forget it okay so this is our Cadence algorithm any doubt till now yes or no and if anyone any doubt so we have completed two of the questions now I'll be having a chit chat with everyone like let's have some of the discussion okay so do you have any kind of doubts or any questions you would like to ask me after this will be I'll be sharing the link of the homework question and then the session will be ending so till then we have ample amount of time to discuss your problems and whatever solution I feel will be right for you I'll be sharing it with you last session today yes yes Milan this is last session code Camp 21 day 21 is the last day and this is day 21. yes the series ends the playlist and the recordings will be available obviously you can look look down the video recordings it will be available okay this Camp helped me yes I was able to see many of you were consistent uh consistently attending this session and consistency is the key to master DSA basically it's not like if you focus on solving n number of questions and you expect that I'll be good at DSA after few days that's not the case consistency leads to good problem solver yeah I used to watch videos by now they're too useless okay yes melon that's exactly it so I see uh anything anything regarding any of the uh part of your let's say DSA Journey or anything so Milan says yeah I used to watch videos by now that too useless sir made me do good utilization okay you're welcome Milan okay so let me share the last question and then after that we'll be ending the session so the last question is very very important from interview point of view okay so the last question is very very important from interview point of view I'll be explaining the question the problem statement is pretty short enough very much self-justifying problem statement so the name of the question is median of two sorted arrays of different size there is one more variation there is no one more version of this question I would also recommend you guys to solve that question that is median of two sorted arrays of similar sizes okay and the other is median of the sorted areas of different sizes this is a difficult version of the uh earlier one which I mentioned okay mid enough to sorted arrays of similar sizes okay so try to solve both the questions first of all solve that question and then you can jump down to this question you you'll get a better understanding why this question these two questions are different okay so given to sorted errors array1 and error two of size M and N respectively find the median of two sorted arrays we need to find median okay so after uh let's say uh combining both the arrays arrays one and array two you'll be getting a completely different array that will also be inserted and in that sorted array try to find the median so if for the median I don't need to explain it again and again I guess you already know what is the median for odd the median is the middle element and for E1 you need to uh at the mid that is n by 2 and N by 2 plus 1. and you apply the logic to find we have seen the K at the element of two sorted arrays okay something can be done I am okay so we have seen the case element of two sorted errors yes we do not to sorted arrays with different sizes can we apply that logic to find for K is equal to length plus one uh length plus 2 divided by two okay so no actually that thing won't work directly okay we need some modification so I hope this question was clear because let's see example number two as well four six uh one two three five combine both of them so we'll be getting one two three four five six and that array will be one two three four five and six so what will be the median of it it will be median of three plus four divided by 2 7 divided by two will be equivalent to 3.5 and the answer needs to be if the answer is in double then you should print uh decimal values as well if it is uh integer values and print the integer value so basically if you if you if I give you an idea on how to solve this question first of approach is to merge both the arrays array one added two if you know merge sort you know how to merge to sorted arrays and then you can find the mid element and if this is not the case what else you can do you can use binary search over there okay you can use binary search try to think how binary search can be used that is the beauty of binary search in problem solving it can be it can be implemented at many places but it's very difficult to see that how and where and in what Manner can you utilize binary search algorithm okay so I'm living that part on all of you I want you guys to brainstorm a little bit although this has been uh we have been in touch from 21 days and consistently uh practicing the DSA questions so I want this question for for you guys like you guys practice this question and try to solve it okay I've mentioned the other important questions as well mid enough to sorted arrays of similar sizes is the uh easier version of it but not that much easy and midi enough to sorted areas of different sizes different sizes is the other version part two is it clear okay so that was it for today's session I hope you really enjoyed this session if you really like this video then do like the video and share it with your friends as well right and do share the uh video with your friends if they are looking for the same content and do not forget to subscribe to this Channel and about the column picks okay so explore that page I've shared the link as well it will be beneficial just like see if you are successful in maintaining consistency for 21 days why not one more month it is going to be beneficial to you know so try to maintain consistence in this kind of things okay that would be fun as well that would be fun and interesting way and you will not get bored in between as well okay I hope everything was clear and best of luck for the upcoming future so this was the last day of our code camp thank you everyone thank you for joining this session and have a good day and good night bye bye