Transcripts
1. Introduction -Getting Started: Hi, everyone. Welcome to, according intra preparation data structures plus algorithms. We all loan data structures and algorithms are bread and butter off according interview. If you want to get a job at Amazon, Google, Facebook or Microsoft, then according must be very strong by according I mean data structures and algorithms. All these companies ask the test of Jason and got Adams and their technical introduce. So in this course what we will do So I will try to cover the courting questions from many platforms like week old Inter bit hankering geeks for Geeks, Cold Chef Court Forces and many more. We will discuss many different solution for according interview. We will discuss the time and the space complexity for every chord for every problem. Okay, so the present quiz it for this course is basic understanding of the structure and algorithm is required. Okay, So C plus plus is also a prerequisite by because I will be according in C plus plus since I am cording and C plus plus. So I hope you have a good understanding. I will not say a good understanding, but you have a rough idea in C plus plus. Okay, if you do not know C plus plus better is also not a problem, because once you're in the strand a logic you can call it in any language you want. OK, so you can call it in C plus. Plus you can call it in Java. You can call him Beytin, so C plus plus, if you know simples person that also discord if you don't know C plus plus, then also to school, because the logic is more important. Okay, so after finishing the schools, I can assure you that you will be able to face the technical interviews off all the Big Four companies, and you can also succeed in those cording and Proview's I myself have correct the interviews off Amazon, Microsoft and Samsung and flip card. The best part about this course is basically I will keep adding more and more videos about recording and precautions. So let's get started. I will meet you inside. Thank you
2. Length of Last Word: I have. Even so today we're going to solve this question. Find the length off the last world. Okay, so the input will basically be a string input will basically be testing, and we have to find the length off the last word. Okay, so they're just consider some example, So if I wouldn't Portis Hello. So desert spaces. Okay, so So if our importers Hello, space space world then this is the last word. OK, so this is the last road and the length of this word is basically five. OK, so our put for this example will basically be a five the length of the last word, which is world and its length is five. Okay, now this is an empty string. So for them protesting obviously the last word does not exist. So are put will be zero length of the last word is basically zero. Not it has considered this import. So for this import, we have spaces here. Then we have a word. Then we have a word world. Then we have spaces again. Okay, so which is the last word? So this is basically the last word. And this is also the first word and this is also the last word. So basically they lent to the last word is five. So our are put for this import is basically a five. Okay, so this is simply an implementation problem. Okay, this is simply I implementation problem. So what we will do, So we'll start from the beginning off the string. So I suppose this is a very lasting So what we have to do? So we will start from the beginning of the spring. We will I treat. We will maintain a variable count, which we will update. OK, so as soon as we encounter a space estimation contra space. So what do we do? We will make this count variable zero. Okay. And then when we will encounter the variable again a 1,000,000,000 called another character , we will inclement. We will abate discount Very well. Okay, so this is simply implementation problem. Now let us right the cold. Okay, we can likely the court. Basically, this is a little cold problem. Okay, So you can read the problems treatment so they import will basically be a string. There can be empty spaces and we have to return the length of the last world. Okay, so now let us right the court. So first, let us create a variable count which will store our answer. Okay. Discovered to enable will store the length of the last word. So what I'm doing here is so basically, there are many ways to implement the solution for this problem. So what Other ways? So first, what can do? You can reverse the string, so if you will reverse the string So the problem is very simple. You have to find the length of the first word. Okay. You have to find the length of the first word if you will reverse the string. Second approach is basically start are hurting from the end of the string. If you will start, are treating from the end of the string what you have to do. You have to find the length of the first word from the end. Okay. You have to find the length of the first word from the end. If you will start dating from the end, okay? You have to find deal into the first word from the end. If you will start dating from the end of the string and the second the third way to implement this problem is basically started dating from the first. Okay, Started dating from the first. So there are many ways to implement this problem. So let's say I am implementing this approach. Okay, so these two approach are very simple to implement, So this is a little bit difficult? I think so. Let me implement this approach. Okay, So I have a variable count, which is initially zero. No, let us find out the size of the string, so as dart size. Okay, so let us take appointed so the irritating from the start of the string. So I called zero. So while I is less than in Okay, so first of all, check whether this character is a space character or any other character. So if this character is not space so if disconnect there is not space, I can safely do commonplace place. Okay? Because this character is not space. So I can do complex place I can do. I place press move ahead. Okay. Now, in the else part. So the current character is basically be so the current character is a space. Okay, So vile. The current characters a space. So while the current character is space. What can I do? I can do I bless place. Okay, so what I'm doing here is so what I'm doing here is for example, you have a string Hello then you have space and then you have multiple spaces and then you have the world the blue. Okay, So if you will encounter a character So at this point, if I if I encounter, reconnected with a space so while that while the character space I am moving on So move ahead, move ahead, move ahead, move. I move her and here I will stop. Okay? Because this clinic based not space OK, but while writing the score you have to also ride the condition. I is less than n Otherwise you may get her anti matter Ok, we have to write this condition and raised You can get segmentation fault or you can get some time out of So now let us right that condition also So why I is less than in and basically the characters space What you can do you can do I plus Plus now there are two ways to break this way Loop first the I becomes a quest to win. OK, so if I becomes a quest to end, that means we teach the end of the string. OK, so we have reached the end of listing Avalon. Serious present in the variable count, so you can return Count. Okay, so we have reached the end of the string. Okay, So and our answer was present in the variable count, so I will have done count now in the else part, I have not reached the end of the string and there are still correct us. So what I will do, I will make count equals zero. Okay, So the meaning off this is basically you have You didn't reach the and a string and there are still characters. So basically, we have toe make the counter variable zero because there are still correct us president. Okay. And finally, what we will do. So when this y looked island, I can return my answer, which is present in the current variable. Okay, so now letters first or another record, and then we will try to summer travel called. Okay? No, What? It does somewhere double. Good. Okay, So our gorgeous working fine. Now let us discuss the time in the space complexity for our solution. So as you can see clearly, we are just creating only few variables. So the space complexity is basically constant. So this is order off one big off one. And the time complexity is linear because we're just I trading over the string. OK, so we are simply I'd rating over the string. So that time complexities big off and and the space complexities hard enough one. Okay, So if you have any doubt in this question, you can ask me. Ok, thank you.
3. Reverse String: Hi, everyone. So today we're going to solve this problem. Reverse string. Okay, so the imported will be basically a string. So then part assisting and what we have to do we have to reverse death string. OK, so after reversing this string so our our put really become Oh, and n e h Okay. And similarly, if they importance this after reverse industry output will be a only the output will be only. And if then posting is broke, then our port will be so b R O c k. OK, so basically, we have to reverse the given string now how we can solve this question. So basically the first way. So there two ways to solve this question. So the first rate to solve this question is with the help of a strike. Okay, so the first is basically with the help of a strike now alerted. The input is Hello. So if then protests. Hello. So what we will do so I will create a strike steak off. It will be a stack of characters. Okay, so I will have a stack off characters. Now. What I'm gonna do is so I would I do it over the string. So I'm standing a touch. What I will do I will bush edge e push inside the steak every l So push l l o. And finally this thing will be over. And this will be our dick. And this will be the condition of the strike. Okay, so what I'm doing, I am pushing every corrector. So I am pushing every character off the string into the hash map into this track. Okay, So, Bush, every character in plastic. Now what I'm gonna do is I will prop every character. So this was the first step. Now the second step will be pop every corrector, and that will be our answer. Okay, so, pop, So Bob O, then l So l then l then e then etch. Okay, so the stack will become empty. Stag will become m pretty and this is my reversed string. OK, so this is my reversed string. So this was very simple. OK, you can take one more example. So suppose the string is very simple. Sting is the only. Then what will happen initially? Steak will be in pretty now. Let's I state so a bush a and then the string becomes m pretty. So after pushing, I have to pop the characters after popping my output will be a Okay, so this is very simple. Now, what will be the time in the space complexity? So basically the time complexity is just were I dating over the string so it will build in here, and the space complexity is basically over and because we will be creating a strike. Okay, so we are creating a strike and is basically the length of the string. OK, and it's basically the length of the string. So now let us right the court. Okay. So what they have to do, I have to create a stack off, correct us. Okay, so this problem is basically present, don't you? Court? Okay. So you can see this is the same problem that we have discussed. So what I'm doing here is I'm grating a stack of characters. And let's see, the name off stack is esti. So what? I'm gonna do it. I have to write it over the string. Okay. So let us I paid. So I equals zero. I listened as start size and I bless place. So I have to push every collector inside the steak. Okay, So what I'm doing here is Bush every corrector inside stick. So this was the first step, OK, that we have discussed So s D dark bush. So let's change the name. So I'm changing the name Toby. Okay, so I called zero. I listen a lot size So stag George Bush A off I Okay, so after the first step, now what we have to do so that this is the second step, we have to pop every corrector. Okay, so I have to pop every character. So let us. I'd rate so far and I call zero. So how many collectively present inside the strike? It will be in characters and it's basically the size of the weapon. Okay, so I called zero i Liston a dart size. I bless bliss. So if I is basically stack dot stop and then stabbed Artpop Okay. And that's all. So you can see here. So basically the return type of the function is weighed, So do not have to return anything and basically what we have to do, so you can see it is passed by reference. Okay, so the given vector is past benefits. That means we have to do changes inside the victory. Okay, so we have to do changes inside the victory. We have to modify the victory. Okay, so I am here mortifying director, you can see here I am mortifying if I is basically estate or top and stabbed artpop. So at this lane lane number 15. So I displaying the that Paris reversed. Okay, so basically, let us again. So if you want, you can drive in, for example, of the string is Let's see. H e h. So this is pastor by defense. So inside the steak, so the first loop push every corrector. So h e h Now the second step pop every correct so pop Etch Bob E and pop H one more example . Let's say ABC So this is initial s take is empathy than Bush A Push me bush. See, Then what I'm doing here is pop. See? Put it here, Papa. Be put it here. Poppy. Put it here. And this is my answer. C b. We do not have to return anything. Okay, We just have to change. We just have to modify the given vector. Okay, so now let us try toe, submit our record. Okay, so I record is working. Fine. Now let's see the question again. So the question says it, we have to do using it, using over an extra memory. Okay, so here we are using a steak. So basically, we're using big off and memory, and we have to use constant, constant extremities. So how we can solve this question. OK, so let's see. So this is a very simple question. What you can do here is we will solve this question with the help of two pointers. Okay, so this is my input string. I will take two pointer, start, pointer and pointed. Now what I'm gonna do is swept, start and end, step, start, pointer and pointed. So what will become so? Or will come here? It will come here. Then I will lose start plus plus and minus minus. So this is my new start. This is my new end again. I'm gonna swept, start and end. So after stepping so this will become ill. This will become e. Then start will come here and will come here. Then what I'm gonna do is I will swept, start and end. So l will be swabbed with l. And then start will come here and we'll come here. So then start becomes greater than end. I will stop. Okay, so basically what we have to do, we have to slap, start and endpoint that only so let us take one more example. So if they input is, let's say ABC Lee. Okay, so what should remember output? So that oil portrait B D c B A Okay, so let's take two pointers. So this is my start point er this is my end. Pointer swept started. And so they will come here even come here. Okay, now start will start plus plus and minus minus. So this is start descent swept, starting in so it will become. See? It will become Be Then start will become good than end. So basically start will come here and will come here. So when start is good and we will stop And this is my output. Okay, you can compare So our our potus correct Now what will be the time in the space complexity . So that time complexity will be lenient. Ok, so scrap operation. This is constant time over time and we are not taking any extra space so the space will be open. Okay, So time is linear and constant extra memory. Okay, so let us right the court. So first let us comment out this one. Now, if we have to do I have to take two pointers Start pointer which is at the beginning and and pointed which will be a large size minus one. Okay, because the indexing starts from zero now, I would have to do so While start is less than articles to end, I will lose stepping operations who swept if start. So, basically, step is inbred function inside c++. Okay, so I'm stepping. Start and end then would have to do start plus plus and minus minus and that's all. Okay, so let's try to summit. Okay, so our record is working. Fine. Ok, now there is one involved function also, there is a little bit function which is called rivers. Okay, so we haven't will function diverse and I will pass a dart, begin a shortened. So what? He was a door begin. You're not and okay and our vector will be reversed. Okay, so let's try to submit. Okay, So our court is working fine. So this reverse function This is inbred function inside the C plus plus Okay, so it can diverse anything. So here it is reversing Better Now if you have a string for example, if you have here string A then also this reverse function will work. Ok, so this is the first function is an inbuilt c++ function. So finally, the time in the space complexity time is linear and we are using constant express trees. Okay, so if you have any doubt in this problem, please ask. Okay. Thank you.
4. Spiral Order Matrix: Hi, everyone. So, in this video, we're going to solve this question. Spiral order metrics. Okay, So what is input? So in port is basically a metrics and what we have to do. So we have trip rivers, the metrics and spiral order. Okay, we will traverse the metrics in spiral order. Now, let us consider this matrix. Okay? They're just going through this example and let us try to find it. Spiral order. So spiral order will be okay. So this is the spiral order. So it's output Should be 123 then 69874 and five. OK, so this is the output. This is this pile ordered reversal for this metrics. Okay, Now let us perform this pile order driver cell for this metrics. Okay, so let's start. Okay, So this is the spy Leard reversal for dis metrics. So its output should be one, then two, then three, then 48 Well, then 11 then 10 then nine, then five, then six and then seven. Okay, so this is this piloted reversal for this metrics. Okay, now that does perform this pilot travel cell for this metrics. So this will be than this then this than this, then this. Then this. Okay, so it's Spilotro will be so. 1234 Then I have 8 12 16 After 16 I have 15 then 14 then 13 Jardin, then nine, then five, then six, then seven, then 11 and then 10. Okay, so for this metrics for this metrics, this is this pile order reversal. Okay, Now let us consider one more example and large. Just find out this pile order for this metrics. So this will be so this one. Okay, so its pilot areas basically 123456 then 12 then 18 then 17 16 15 14 13 789 10 and 11. Okay, so what? This Murdoch's this is this pilot? Relatively. OK, so I hope you were the idea. So I have to traverse the medicine discretion then inside. Okay, so I have to preface de metrics in this fashion. Okay, so we're traversing the Murdochs indiscretion. Okay, so this is this pilot that I was certain. Now let us consider now let us discuss how we can solve this question. OK, so basically, this is just implementation problem. So what I will do? I will take four vegetables. Okay, so this is simply mint implementation problem. Now, to implement this spy alert reversal, what do we need? So we need four variables. We simply new four variables. Okay, so start true. Andrew, start column and column. Okay, So with the help of these four variables will be able to solve our question. OK, so let us consider a metrics. So Okay, so let no do not consider this type of my took, so construct this metrics. So I have this metrics. Okay, so we're dealing with a value of start Brousseau, start trouble. Be here. Okay, so start role will be here. We're two with the value of Andrew. So Andrew will be here. Start column So start column will be here, and column will be here. Okay, so whatever, Lou first awful. I rely trait I have to print in this vision. Okay. In this fashion, then inside. So first I have to print this start true. So let us print this astride through. So after printing start what I will do, I will print this end column after printing the sand column. I will print this Andrew after printing this Andrew What I will do. I will print this start column. I will print this start column. Okay, So after doing this, what I will do I will do basically start hopeless place. I will do, Andrew. Minus minus started. Plus plus because starter has been printed. Andrew minus minus because Andrew has been printed. Okay. Start column. Plus plus, because start column has been printed. Okay. And the column, we will do End column minus minus because the and cola mastering printer. Okay, I'm emigrating myself. I will lose start troop plus plus, because the star true has been printed. I will do Andrew minus minus. Because the Andrew has been printed, I will lose Start column plus Plus, because the start column has been printer, I will do and column minus minus because the end column has been printed. Okay, So after doing this, what will be I situation? So this will be my new metrics. Okay, so this is basically this is basically the start, because I have done start, look listless. This will be my Andrew, because I have done Andrew minus minus. This will be my start column because I did start column plus plus and this will be my end column. Because I did. End column minus minus. Okay. So again, we will follow the same approach. I will print the star. True. I will print the end column. I will print the Andrew. I will print this start column. Okay. After doing this, we will perform these four steps again will perform this four step again. So again, this will be my inner metrics. I performed. Start replace place. So this will be my start. True. Similarly, this will be my start column because I did start calling. Plus. Plus, this will be my end column because I did and call a minus minus. And this will be my Andrew, because I did, Andrew. Minus minus. Okay. So again, we will do the same thing. Brent the star True print the end column. Print the Andrew and print the start column. Okay. And again, we will update this values. So how long I have to perform these operations? So start true. Basically, starfruit should be less than or request to Andrew, obviously. And basically, start column start columns should be less than or a question and column. Okay, so this will be my condition. I will write this condition inside of my loop or inside the for loop. And I will perform these steps and I will perform these steps. Okay, so very simple. Implementation problem. Okay. Very, very simple implementation problem and let us take. We will also take account variable. So initially discount available will basically will be zero. But I have to do so. How many elements will be present inside the metrics? So either dimensions RM. Aaron. Okay, so this is the dimension m cross in. So how many elements will be present inside the matrix? So mn elementary present? So as soon as the count will become a quest women, I will stop. Okay, so this is one stopping condition. This is first stopping condition and this is second stopping condition. Okay, so count will store how many elements I have printed. Okay, so this we're able will store how many elements has been printed. So as soon as the account of the elements become a question women, that means I have printed all the elements of the Matrix. Then I can stop. Okay, So I have post op in condition. This is the first to stopping condition, and this one is this second stopping condition. When the count become bequest women, that means I have printed amon elements. So I have printed all the elements of them are Turks. Then I can stop. Okay, Very simple. So just when you're 40 variables start true. Andrew, start column and column. Okay. Initially, my start trouble B zero. Initially, my end column will be zero and Andrew will basically be m minus one and and column will be n minus one. Very simple. So this is the question spiral metrics. Okay, so then put us basically a Tory metrics. And I do not have to print anything. I have to return back profit teachers. OK, you can see. So if this is the metrics, so I have to written that profit teaches. Okay. Now, if you ever destroyed the logic, now let's start writing the cold. Okay, so, as discussed, renewed four variables. Okay, start. Okay, so let us first find out the size. Okay, Let us first for a note size. So in em is basically medic. Start size. How many rules are present? So my text, right size and some really let us find out how many columns are present. So this will be metrics off zero dot size Simple. Now let us construct our answer. So construct answered above. Okay, so I have this vector often teaches. I said OK, so I will push every element inside this answer variable inside this on selector. Okay, After finding out the size, I have to take four variables. Start true, which will be zero Andrew So? And there will be a minus one, and then I have to pick basically start column So start column will be zero start column will be zero and and columns. So what is and columns that this is an minus one. Okay, so we initialized our variables, and I have to will also take account variable. How many elements has been printed? How many elements has been pushed into this? Answer vector. So initially, this really will be zero. Okay, Now let us write our condition. So while basically the start row is less than or equal to Andrew and the start column should be less than or equal Strand column. Okay. Where the simple condition. Now what I have to do. So see carefully. First of all, I have to print the start room. Okay, Spiral, order this one. So this is the spiral order. So what I have to do? I have to first print the start room. Then I have to print the end column. Okay, so this is Step one. This is Steptoe. Then I have to print the Andrew third step, and then I have to print the start column. Fourth step. Okay, so in this order. So this is step one. They're desperate from step one. So what I have to do So let's print basically the star Drew. Okay, I am printing the start group. So for printing the starter live toe, I'd read over the columns. So start column I less tonight Equestrian column and I place place I would have to do so once Adored pushback afterward. Pushback metrics. So this is the metrics. Okay, So, metrics, so start true. And column is variable again. Column is a no. I also have to do count plus plus Okay, because county storing how many elements have been printed? Okay, so after printing the first after printing the star, true what I have to do. So I have printed the start also start true plus plus. Okay, started has been printed. Go to the next room and you can also check. So basically, if the value of count, if they really have come to become a questo m and doing that means old elements has been printed. So basically, you can return. Answer. Okay, you can get an answer. So this is the answer you get, er done the answer. So step one is done. Okay. So what is it, Steptoe? Steptoe is very simple, This one. I have to print the end column. Okay. I have to print the and column. So the desperate the End column. So for printing the and column, I have dried rate over the rules. Okay, So start true. I less than our request to Andrew. I place place again, so answer dot Push back what have to do. So metrics off. So row is variable and I have to print the end column. Okay. And column. And again, I have to do count. Plus plus. So let me read the commentator's. So what I'm doing. So the second step is printing the ankle. Um okay, I'm printing the end column. So after printing the end column, let us go back and Gholam minus minus. Okay. And column has been printer. And again I will write this condition. So if the number off elements is a question women, that means all the element has been printed. So in that case, you can return the answer our on say, 30. We can return our answer. Okay, Now that tired step would have to do so. This is the third step. I have to print the Andrew. Okay, this is the Andrew I have to print Andrew, so I have to sprint. Andrew. So for printing the andro, I have to paint the ruined reverse order. Okay, You can see I have to print their O in this order, so I will start from and column. I will stop at start column. Okay, So I have to start at End column. I should bigger than a request to start column I minus minus Again. Answer dart, push back Metric self. So I am printing the Andrew and the column will very okay. And again, I have to look around placeless and again. After printing, the Andrew would have to do Andrew minus minus. Okay. As I have printed the Andrew again, we will write the condition. So if Countess equals two m and win, that means all the element has been printed. So you can return the answer. Okay, now, ever step food. So step foot is very simple. So I have to print the start column. Okay. I have to paint the start column, so I will go from. So this is the start. True. I will go from Andrew to start. Okay. From down to up. So now let us sprint the start. Call him. Okay. What I have to do, I have to go from down to up. So I have to go from Andrew. I will start from Ando. I will reach the start room. I am minus minus. Okay, Morgan, answer. Don't push back. So what I have to do So metrics off, rival various Always I and I am bringing the start column. And again I have to do count plus plus counter storing or how many elements has been printed. So again, after printing the start, called him, I will lose Start column. Bless bliss. Okay. Start column. Plus plus. And now you can again check. So if the value of Countess basically em in 20 That means all the helmet has been printed. So in that case, you can return your answer. Okay, So I think we have done everything correctly now for the compilation purpose since I have to return back proffering teachers. So let us right Return answer here. Okay. So let us right or done. Answer heralds. Okay. Okay. So we did spelling mistakes somewhere. So this will be count. OK, now let's turn our court again. Okay, So you have a cord is working. Now, let us try to some metal cooled. Okay, So I have to check. Basically of the med techs is empathy. So if basically m zero, that means Maddox's empathy. So in that case, you can be done. Empathy answer. Okay, so at this point, So this on say, is m pretty. Okay, if you will run again, I guess you have a gold is working fine. Otherwise, you can also write one more condition. So if the number of columns are zero, then also you can return the empty answer. Okay, Now that summit. Okay, so have a court is working. Fine. Now let us discuss their time in the space complexity. Okay, So another does discuss their time in the space complexity. So again, this base complexity is basically order off one. Okay, space complexity is order off. One. We are not a locating we're not creating any extras were not taking any extra space. So spaces between Lord Roughan and time complexity is basically ordered off mn Okay, we are going through each and every element of the metrics. We are going through each and every element automatic. So that's why the time complexities mn and miss a number of rules. And it's the number of columns. Okay, so it is very simple. Logical get very simple implementation problem. I am predicting the start. True. So this is the first step grain to destroy brew, then start hopeless place. So print the end column. So I'm printing the End column, Steptoe. Then I'm doing and column minus minus. Then I'm printing the Andrew, so I'm bringing the end road. This is Step three. Then I did and ro minus minus. Then I'm printing the start column. So this is step foot, print the start column and then here I everything start calling place place. So what will happen? This will be my new metrics again. I will do Step one. I will lose Steptoe. I will do Step three. I will do step for Okay, So very, very simple logic. Okay, so this is step when this is Steptoe. This is Step three and this is step four. Okay, time and the space complexity is big. Often men and big often. Okay, So if you have any doubt in this question, you can ask me. Ok, thank you.
5. Search in Matrix: Hi, everyone. So today we're going to discuss this question such in metrics. Okay, So input will basically be a metrics and our target value that we have to search inside the medics. Okay, but this metrics is not a normal metrics. Okay, so this is not a normal medics. That metrics has a property. Where is the property? So this metrics, each room is sorted and each column is sorted. Okay, so you can see. So this is sorted. 267 11. This is a sorted through 38 10 12. This is a sordid room for 9 11 13 This is a sort of 5 15 16 and 18. Okay, so in this matrix, each always sorted in descending order. And similarly, each column is assorted. Okay, so this is do then three, then four, and then five. Similarly, 689 15 7 10 11 and 16 Sorted. 11 12 13 and 18. Okay, so each row and column in the given metrics is basically sorted, and the question is basically given our target value. So in this case, the target will lose nine. So, given a target value, we have to return to war falls So we will. We have to return a Boolean value. So this blend value will be true if the given target is present inside Dima tricks. And this will live false if the given target value is not present inside the metrics. Okay, so this question is basically present or Luke, or Okay, so you can see here. Okay, so each always sorted and each column is sorted. Okay, so how we can solve this question? So the first ways to solve this question that we just discussed the approaches. So the first approach is the brute force approach. Okay, So what this approach will say is just I traded over all the metrics just I trade over the metrics, basically go through all the elements. If you will find the target will return through the visor. Turn falls. Okay, so we will go through each and every element. So what will be the time? Complexity. So let's say the dimensions of the metrics alum and twin. So the time complexity will be Eman and the space complex that they will be our draft one. Okay, so this brute force is go through each and every element in the Matrix and compared that element with the target, will you? OK, if you found the target value return, throw the resident falls. So this is the time in this space complexity. The second approach is basically by any research by any search each other. Okay, so we can see each row is assorted row, so we will go through the first row. We will apply the binding research come to the second row applied to buy new research come to the third row applied by the research come to the fore through applied by new research. So we are hydrating over the rules so that time complexity will be so since we're irritating over the rules. So we have Ambrose and for searching what we are doing. So this is basically an columns before searching were using buying in search. So it will be m into Logan. I m into Logan because we're using by any search. Okay, so we are optimizing our time complexity, and we're to less waste Convexity. So it'll still this is order off one. Okay, now it does discuss the best approach. So this is this method is called staircase search. Okay, this is called staircase search. Now what this metal say's is basically you move at the move at this element. Basically top right element. OK, so move to the top rate element. Move to deter operate elements. So this is 11. Now compare 11 with nine. So 11 is bigger, then move left. Okay. Compare seven with nine. So this is smaller. Moved on. Now compare 10 with nine. So 10 is bigger than move left. Now compare it with nine. So it is smaller. Move down now compare nine with nine. You got here. Element returned true. Okay, so it stays. Moved their top right element. Now compare the element with the target value. So if the element is greater than the target value, what he will do so basically, you will move left. So for moving left, we will look call a minus minus. Okay. And if the element is smaller than the target value, we have to move down. OK, so for moving down, I will Louro plus plus. Okay, so this is 11 11 elements. So the element is good in the target value, then were the nine mil. I obviously nine will lie in the left hand side because in the left hand side of the 11. The elements are smaller. We cannot move down because if you will move down than all the elements will be good than 11. And we have to find the nine. Okay, so nine element can only be present in the left hand side off the 11. Now compare seven with the nine. So seven element is smaller than nine. If you will move left, then you will get smaller element than seven. Okay? Because that Ruiz sorted so we cannot move left. We can only move down now. Compare 10 with nine. So 10 is bigger. If you will move down, you will get bigger element than 10. But we have to find nine. So the only option is to move left and 80 smaller than nine. So obviously you cannot move left if you will move left. You can not. You can never find nine. So the only option is to move down. Okay, so this staircase up, which this staircase approach is basically making the use of the property of the metrics. Row and column Botel sorter. Okay. And now why? It is called steak a supposed because you can see, So this resembles the staircase. Okay, so this shape the way nvr searching this is nothing. This is just a staircase. So that's why it is called ST Kitts approach. Okay. And the logic is very simple. If the current element is great in the target value, then obviously you have to move left. If you want to find out, the target value cannot move down. So for moving left, I'm doing call a minus minus. And if this is the case, obviously the only thing. The only way to find out the target value if we will move down. So for moving down, I'm doing rope less place. Very simple. Now we're through the time in the space complexity for using this approach. So space complex, it is nothing. This will be our draft Mint and thyme. Convicted is basically in the worst case. What will happen? So I will go through this and then I will go through this. So, in the worst case time complexity will be implicit when the element is not present. Okay, so you can see first ever time. Complexity was mn Now it is linear emp. Listen. Okay, so this is also example it has used straight is approaching this example, So we have to find the target value five. Okay, so let me draw here. So I have 147 11 15 then 23 10 18 56 Tardini and don't even 89 14 23. Well, 16. 17. Grant Essex 1922 24 and 30. Okay, so the target will lose Basically five. So according to a staircase approach, come here at the top. Right element. Now compare 15 with three. So obviously 15 is bigger. So the only were to find Fife is to move left again. 11 is bigger than five. So only way is to find Fife is basically move left again. Seven is good than five. So five can lie on the left hand side. So move to the left. Now compare for with five. Obviously the five element can be present. Downside only. So move down And now we will get our element five. So we will return through. Okay, Now let us find out this element, which is 20. Okay, so I am standing here 15. So if you want to find 20 you will move down. Because if you really move down, You will get all the elements which other than 15 So move down. So 19 obviously, If you want to find out 20 move down so I will move down now 22 is bigger. So move left. 16 new, smaller. So moved down 17 This smaller moved down from the success. Bigger move left 20 trees Bigger Move left. 21 is bigger than 20. Move left. 18. A smaller than 20 moved down. Okay, so if you will move down our my tax will finish and we will stop. And what we will do, we will return False. Okay, so you can see this is a staircase approach. This resembles the shape of a staircase. Okay, so that's way this matter of searching is called staircase. Okay, so now since you have understood the logic, I think according will not be a problem. OK, so now let us right the cool. Okay, So the court will be very, very simple. So now let us find out the rules and the columns. Okay, so who is basically how many rules out there? So this is metrics dart size. And now let us find out Di columns. So this is nothing but my takes off zero dot stays. Okay, So let us handle first case. So if the target value, it's basically smaller than the smallest value in dramatics. Okay, So you can see this is basically the smallest element in the metrics. Okay, this will be the smallest telling them attacks because it will move right, or you will move down the elemental increase. And similarly, this is the largest element. So this is the largest element off this matters. And this is the smallest element. OK, so basically, if the target value is smaller than the smallest element off the metrics or the target value is basically bigger than the biggest, the largest element in the Matrix. So this is basically euros minus one and columns minus one. So if the target value is greater than the largest rail you, then obviously you can die clear. It unfolds because the element will Lord be present. Okay. Okay. So no letters I'd read over the metrics. Okay, so let us take two variables. So I this related over the rules, and I have a very ability, so this related over the columns. So this is nothing but so I have to move to the last column. So this is columns minus one. Okay, so but with the condition So Vile Baru So why lie is Lester Nautical store was minus one and viol j is basically greater than or equal to zero. Okay, so what I have to do compared the current element. So this is basically I'm moving to the top right corner. OK, so move to the top rate. And since I have to do so, I will do rule Plus Plus I I will look call a minus minus. So that's why discrimination. Because I will Louro plus plus And that's what this condition Because I would look columns minus minus. Okay. So if the current element which is takes off easy So they had three cases first cases, very simple, were farmed out the target element. So in this case, I can return through. Okay. You can see there turn type of school so I have to return either for war falls. So if you have farmed document the target element, we can returned. True. Now there are two more cases. The second case can be if the current element is smaller than the target value. Then we have to do I have to move down. So for moving down, I have to do rope less bliss. Okay, so the name of the variable is basically I So I will go. I plus plus And in the terrorist case. So if the current element is good in their target value, then would have to do so I have to move left. So for moving left, I have to do column minus minus. So here the variable column is basically G variability. Okay? And if I reach the end of the loop, I can return False. Basically, their target really is not present. Okay, Okay. So now that doesn't make a record. Okay, so we found their taxes empty. We're getting runtime error. Okay, So what I have to do, I have to handle the situation here. So if basically ruse is zero, if they're not any rules, but can I do take under 10 falls? So again, if the columns are zero, then I can also return false. Okay, So our court is working. So as we discussed the time in the space complexity for using the Stakis approaches spaces or drop one earned time is m pleasant. Okay, so if you have any doubt, you can ask me. Ok, Thank you.
6. ZigZag Conversion: Hi have Even so today we will solve This question is exact pattern. Okay, so the input will basically be a string. And the second input will basically be than a moral fruits. Okay, so these are dinner tomorrow flows Now what we have to do since the number of rows is basically to So I will make two rows. So this is Roman and this is Roto. Now I'd read over the string. OK, so a so right in the first row. Then I have be so right be in the second row then I have see so right c in the first row. Then I have been so I d okay. And this is my first true. And this is my second row. Okay. And then first right, first row. So this is a C then. Right? Second row. So this is baby. This is beauty. Okay, so this is the output. Okay? And this is the output for dis input. A see beauty. Okay, now it does consider this string OK, and then tomorrow Fairuz is basically three. So this is my first road. This is my second row, and this is my turtle. Okay, so now let us I dread over the string and fill this ruse. Okay, so this string is basically people is hiding Okay, people is hiding So I have be so right. Be then I have a Then I have way again Be then a then l So people then i IHS is hiding So itch I all right? I and N g Okay. And now for producing the output. So for writing the airport, right, The first rule. So first Roy's b A h And so this is first row b a edge and then ride the second row So this is a pl s i g So a b and as I i g then right, the third row, which is why I are so why I are okay. Why I So this is the output for this input. Okay, so I hope you understood discussion. Let us even more example. So this question is basically a lead core ocean. Okay, so paypal is hiding, and then the motor flows is basically food. Okay, so we will create four rules, So I have the system first rolled. This is second row, third row and full. True. No people residing soapy a way be a and IHS It's I all right, I and and G Okay, So we will write the output of the first rule, which is speak again the north part of second row bitches E l s I e g in our plot hydro. Which is why a h r in the ar put off for true, which is B I Ok, so this is the output for this input. Okay, You can match B i n a l s I gv h r b a Okay, so our POTUS basically correct. Okay, so this is the question Now, how begins all discussion. So this question is again a simply implementation problem. Okay, so this question is basically a simply implementation problem. Now, let us see how again solve this problem. Okay, so let's just consider this example. People residing in the number of rows is basically three. So in the middle, throws is basically three, so number off rose is basically three. So what we will do, we will create, so we will create energy. Okay, so we will get in a day off size tree. Okay, so this is basically the zero to index the 61st index of the area and this is the second index of the area. And inside the each index, I will store a string. So they didn't expel story string. The first index will store a string and the second index will store a string. OK, so basically I will write something like this. I want to create our area off a string. So let's call it string then let's say the name is str and the size will be the model froze . Okay, So if you want to create the anti Asia area what you write, you write and airy and size three murders. We want to create an a day off string. So the system Syntex string First of all, little right, the data type. So the type is individuality, diapers string than the name off the area and then the the size of the area. Okay, so first of all, I will create this area so each index will store a string, OK, and then we will fill the values in these indexes and after were filled this value in this in Texas I will. I trade over the area and what I will do. So let's call It answered So I will. Right? Answer Bless questo. So the cyst string the name off the areas. Basically str so I will write str off I OK, so this place operator where they can do so With the help of this plus operator, you can append boosting for example String A's ABC and they have in a district. Let's call it the e f Okay. And I would answer you physically s bless the so we feel right Plus operators So this plus operator can upend two strings so this answer will contain a B c d e f. Okay, so initially this after answer will be empathy. And when we have filled this completely But we will Louisville I'd read over this area and then we will write on surplus it. Questo string off. I okay, I scared. It's basically the name of the area. Now let us see how we can fill this area. Okay, let's consider an example. Okay, so I have the string people is hiding. So in this example, the number of flows is basically three. Okay, since the number of flows is basically tree what have to do? I will create I agree. I really create an area off size three and inside these area. But I will do I will store a string. OK, so this will store a string. This will store a string and this will store a string. So this is zero. This is one and this isn't next to So now let us I'd rate over the string Soapy Right. Be here then. I have a sore right here. Then I have I so right. Why here then? I have be so I cannot write be here because I have reached the an interesting. So I will move up. Er I will move about So I will write. Be here. Okay then I have a So I will Right here then I have l. So I cannot write l here because this index does not exist. So I have to move down. So for moving down I will write l here. Okay, so I have s I can write. I hear I have s again. We cannot write as here. Okay, so we will write s here then I have etch so right edge here then I So again we cannot write . I hear so I will write, I hear then hiring. So I and n and G Okay, so what is the situation? So basically the zero to nexus containing the string b e h n The second The first index is containing this string and our third in Texas basically containing the string Now what we have to do So we have to I'd rate over this airy and suppose our answer is basically empathy. Then what we have to do we have to right on circles on surplus. Now this place operator can upend two strings So let's say the name of this area's str So what I will write. I will write STS off I OK, so I am a pending this thing. So this is the first string which will be upended. So this is ph in now this string will be upended so it will become a B l s I g. And then I will upend this a string. So this is why our and this will be our output. So this is basically the ancestry. Okay, So very simple. This is just the implementation problem. Okay? Only implementation problem. Now let us right the court for this. Okay, so now let us right the core. So input is basically a string and we have dough Return a string, OK? And this is the number off ruse. So first, let us handle some very simple cases. So if the number of rows it's less than or a question one if there is only one do okay, you can diet later, turn the given input sting because you don't have to do any changes. Okay, so now let us find out the length of the given string. So this is as dart size. Okay, so now let us create this area. Ok, so I have to create this area. Okay, so you've want each index short stories, strings to the Syntex will be that it I first string than the name of dairy. Let's see, the name of the area is basically a okay and then the size of the area, which is basically the number of rows. Okay, if the number of rows is basically three than the size of the areas, basically three. So this is the view to create a straight victory. But we know whenever we want to create a area and whose size is basically a variable The better way to create batteries with the help offered Dynamic a location. Okay, So instead of creating a started Carrie have been created dynamic carry Sosin textually string. Then start then the name of that A which is new. And then the new type, which is string and then D Saiz. Okay, so why we have to create this dynamic area by North started Kerry? Because this value is variable. Okay, so whenever you have a variable size, the better way is to use dynamical location. Okay, so string start the name of the area. So new operator And then the red tape and then the size. Okay, so string start led to the name of is a So this is new that it type string and size basically Andrews number off those. Okay, so now let us I trade over the string. So I'm taking available room, which is initially zero, and let us take a variable step also. So now let us I trade over the input string. Ok? So far, our trading I am using a via loop a four loop. Ok, so now what you have to do. So the name of there is a so a at what Index I have to push. So for choosing the index, I have created this variable room. Okay? At work, bro. I have to push the current character. So that's why I have created this variable through. You can see this is index zero. This isn't next one. This isn't next to so basically for moving these indexes for storing these indexes, I am taking a very bold room. Okay? So initially have to put at indexes it also. That's why Ruiz, in its last with zero dinner table do so I will Louro plus plus for going to index one. Then I will go to index to So I will again do row plus plus after reaching the index to I have to move above I have to move above. So basically after two room minus minus. Okay. So basically this plus plus thing and this minus minus thing Soto become to make this thing easy. What I'm doing, I'm keeping a variable step. So this step is basically one. So if I will write, Roy equals rope less step. So this is nothing. It is simply rue plus plus. Okay. And if the value off step is minus one. Then what is the scenario? And I am writing rue equals true bliss. Step then, this lane will become room minus minus if the value of a step is minus one. Okay, Simple. So don't do this rope less blasting and then again moving upward. So we have to do a plus plus and we have to do so minus minus for doing this place blasting . And this minus minus thing I am keeping I'm maintaining a variable step, which is initially one. Because we have to move down initially. Okay. And when we will reach here, when we will reach at the last index, I will update the value off a step to become minus one. Then when I will do roll call surplus step, this will become room minus minus. Okay, simple. So I have to push at their next room. Okay, so this is basically a string and for pushing the element inside this thing. We have a function pushback. Push back and you can give the character so correctly is basically s so phi. Okay, so now what we have to do so either I have to move down. Hopeless place or I have to move up. Room minus minus. Okay, so how to decide? Let's see. So basically, I will simply right requests through Bless step. And now let us check. Either we have to move. Then we have to obey the value of step or not. So if basically I am standing at zero true, then obviously I have to move down. So if I have to move down so I will let step acquits one so that it will become ruthless. Plus, so this is you're the value of step is one. This will become ruthless place. Okay? And if I am at the last two index? Okay, So else, if I am at the last index off the area So basically, Roy, it cost equals and rose minus one. The last index of the area. You can see the area is off size and does so the last indexes basically and rose minus one . If I am standing at the last index, then I have to move up. OK, so for moving up, the value of step should be minus one. Okay, so this is to move up through minus minus. We have to move up and This is simply Royko's rope less step. Okay, so when we will reach the end of the four loop, our is basically ready. So this Eddie Okay, so this area is basically ready. Then what I have to do? I have to create a string, and I just have to retreat over this area, and I have to append these strings. Okay? Not a desk idiot. A variable answer, which is initially empathy. Okay, now we have to I dread over decided, Okay. And this side is basically, really know little side treat over this area and what you have to do so on circles on surplus so this place operator can upend two strings. Okay, so on cycles and surplus than ever, there is a and the index. Is I okay? And when we will reach when will come out of the loop, we can do done our answer. Okay. Okay. So our code is working now, Lord, Somebody Okay, so I look over it is working fine. Know what you can do? So instead of creating this industry, we can like a break district also. Okay, So do not create the new string. Let us update the previous one only. Okay, so this is s So s his empathy. So I have a better distinct empathy. Then I'm abdicating the string. So s acquis s place. I and then I am returning us. Okay, so I'm not creating new sting. I am just abating the given string. Okay, so now let us discuss the time in the space complexity forever. Solution. Okay, so one thing first. So what I'm doing here is so this is day input string, So I'm updating the importing. I'm not creating any industry. Okay. So s equals empathy. Okay. You can also write IR function clear. So s dark. Clear. So this clear function and this amputating they both are same. Okay, so the space complexity basically what we're doing So we are creating a new ERI. Okay, So be accurate in this area. So the space complexity is basically Andrews off and rose, and then a Madoff ruse, okay. And the time complexity is basically we're just trading over the string. OK, so here we are, just a trading over this string over the given string. So this is order off and bless. And then we are a trading or what? This new Eri. Okay, we irritating over this new address. So the time complexities, Andrews, because the sizes and those time complexity is basically order off and and ordered off Andrews. Okay, so this thing will be very small. This will be like either 345 or six But this will be very, very large. For example, this can be 100. This can be like 1000 characters. This can be 10,010 k and so on so basically and is gooder than good and and is much, much bigger than the number of fruits You can say that time complexity is nothing. It is just big off an A Lee. OK, so the sister time complexity and also the number of rows This will be basically like either one or two or tree. So these really will be very, very small. 456 Generally, this will be very, very small, so you can also say like MySpace where complex reason I think it is just order of one. OK, you can say because this will use will be very, very small. Okay, so you can see the space complexities or rough one. And if you're not comfortable with this. Then you can say the space complexities. They go off number off those and the time complexities big off. And okay, so this was simply an implementation problem. Okay, So if you have any doubt in this question, you can ask me. Ok, Thank you.
7. Single Number: I have. Even so today we're going to solve this question. Single number. Okay, so what is the problem? Statement So blustered want is very clear. So we will be given. So the input will basically be area I indeed array and what we have to do. So basically every element will appear twice inside the area except for one element. And our task is to basically find that one element. OK, so they're just consider some example. So this is our input, Terry. So see every element disappearing twice except one element. So this is occuring on liver in time. So our answer for this in port will basically be even Okay. Now, see to is appearing to times when is appearing to times. So four is the element that we have to find. So in this case as possible before, because every element is appearing twice except one element. And we have to find this one element. OK, now that I said this example, So when is appearing? Two times two is appearing to times. So I have this elementary. So three is a painting or live in times. So our on several bigotry Okay, so I hope you understood the question. Now let us discuss the approaches to solve discussion. Okay, let us discuss approach number one. OK, so first approach is basically it involves sorting. Okay, so what we will do so we will sort the area. OK, so after sorting the area, what will happen? So, like, that's consider this example. Okay, so this area will become one. Do so basically what will happen? So if the elements have same, they will appear in the descent manner. Okay, so in this case, I will enter it over the area and I can see when is the different element. OK, so first I will sort the area and then I will I treat over the area. So what is the time in the space? Complexity. So spaces will be or drove on and time is first. I'm starting the area. So in Logan. And then I am are hurting over the area which isn't so basically, this is nothing but. And Logan Okay, some relief. You will sort this area. So what will happen? All the elements which are same, they will appear in the They will come up in the air. Dysentery. Okay, so they said they will become 11 Tau Tau and full. So basically, when you rely trait, they are same. Move ahead. They are saying move now the sister different element. OK, so in this way you can find out the element now for deciding if you will apply the sorting approach for to happen. So this will be 11 then again to toe and then three. Okay, so these two elements are same. The story with the same This is according one time. Okay, shower on several, but this so in this way. But we Lou first sword theory and then to find out the answer and just I tripped over the area and find the unique element. OK, so this is the time in the space complexity Time is and Logan and space complexity is basically order off one. Okay, so now let us discuss the second approach. So the second approach, basically it is it uses hash map. Okay, so in the second airport or two blue. So basically, in the second approach, we will create our hash map. Okay, So what we do, we will take a hatch map. Okay. So the key will be element and the value will be basically the count off. Great element. OK, so this is the key value appeal that I will store in the Hashmat. Okay, so now let us just I tripped over the area, So let us consider this example. Okay, for 1 to 1 toe. So I have 41 again to one and two. Okay. So initially, my hash map is empathy. Now I trade. So I have element for its count. This one, then I have element one. So element one, it's Countess one. Then I have to. So I have 11 toe. Then it's Countess one. I have Element one. So increased the count, so it will become too. I have this element to so English. The count it will become too. Okay, so once you light right over the area, you're hash. Map is ready. I would have snipers ready. Then where do we look? We would like to read over the hash map. Okay. With the light rate over the hash map. And if there is an element present whose count? This basically, even then, our answer will be basically the key. Okay, so in this case, around several before because it's Count this one. Okay, Now let us consider one more example. So suppose I have one toe toe, three. Anyone. Let us prepare our hash map. Okay, so I have this element one. So when it's count is one Okay, now element to its countess One again. Element toe. So I will increase the count again. I have elementary, so push inside the hash map. Count this one. No, I have element wants to increase the count. Okay, so after doing this, our hash weapons ready after I'd reading over the area. Our hash map is ready. Then I will. I treat over the hash map, and G three has count one. So that's why our answer will be three okay and similar. Leave it this one also, if you will prepare the Hashmat. But will we like element to count one? Then again, elementos. I will make the count two. Then I have element one. So element one and count is one. So this is the hash map. Now I trade with the hash map and you will be able to find the answer, which is one. Okay, so in the hash mark, what is the time in the space complex city. So basically, time complexities big off. And so we are assuming that the UN ordered so overtly will use. We will use an order map and in order map the time complexity is basically order often. Okay, you can insert you can search. So all this time complexities are basically order off one. Okay, so the time complexity is just toward rough. And we are treating over the area and preparing the hash map. And the space Convexity is basically or the Ruffin. Okay, So this is that time in the space complexity for using the hash map. Okay, So you can see we are optimizing on time, but here we are using extra space here. We're using extra space to prepare the map. Okay, so now let us discuss the best approach for solving discussion. Okay, so it does discuss approach number three. So we have X or approach so x or is operated. Okay, so this is the symbol. So what is X or so basically the truth table off exercise. So you have to reduce nb. So if this is when When When? 001 and 00 And this is basically the output way. Okay, So what they are doing, why is basically a X r b? Okay, so you know when you will apply the operator, what will happen? So if the elements are same, then the output will be zero. So in this case, the elements are same. That protests zero. And if the elements are different, that would put is one. Okay, so this is what X orders. Okay, so suppose is basically you too, And these basic military. So what will happen? So this is a bit twice. Operator. So how bad guys operate? Double work. So it will convert toe into it by the reform. So which is basically one and zero will convert three into its by no reform, which is nothing but a one and one. And then we will apply the X or operator. So the elements are different. Our POTUS one, the elements are saying it's with our POTUS. It'll and now we will convert this band early in tow. It's decimal form, so it will become one. Okay, so, basically to Czar two x or three, it's nothing but one. Okay, So this is how it works now. There some properties off X or Okay, So what are those properties? So in order to solve discussion, you must know those properties. So the first properties Suppose you have an element. So the first properties, if you will x or to same elements, you will get zero. Okay, second property. So you have an element A And if you will take the X are with zero, then you will get itself. Okay, So this is the first property. This is the second property So tired. Property is basically the exhort operator. It's basically associative. OK, so if you will right like this a x r b x r a then basically this am this a will be zero. OK, you can see if the elements are same. They are zero. So what you can write so a X or be X or D. This is nothing but a eggs are a X r b okay, and this will become zero. So I have zero x r b and then we will use the second property. So this is nothing but be okay so you can write a X or be X or a so and they will consider out each other. You will have be. Okay. So these are the true property? Is that you should know. OK, so these are the 1st 2 properties and this one is too tired. Property. Now let's see how we can use this excerpt. Property toe. So lower question. OK, so let us take some examples. So 412 went toe. Okay, so I have this area 4121 toe. So this is for this is one. This is two. This is one and this is too Okay what they will do. So every take the X or off all the elements. Take X art off all the elements. So what it will look like for ex servant X or two X are one extort toe. Okay, so what will happen? This one And this one They will cancel out each other. This too. And this too. They will cancel out each other. Why? They will cancel out each other Because I know a If the elements are same and we will take the sword output will be zero. And if you will take the door with zero, you will take you will get itself. Okay. So what will happen? Only four will be the remaining element. So our on several before Okay, Like that's considered one more example. So I have one, then I have to. I have two and three and one. Now let us take X or off all the elements off the area. So, what did you look like? One exhort toe exhort two x or three X servant. Okay, so this too. And this do they will cancel out each other. This one will cancel out this one. Sour output will be three. Okay, So very simple. So, what did we the time, this waste complexity of using this approach. So space complexity will be ordered off when? Okay. And the time complexity will be what we're doing. We're just tired waiting over the very so the time complex. They will be big off. And okay, so this is the best approach. Okay, this is the best approach. So what we will do? We will take a variable initially, that variable will be zero, and then we will take the door off old elements. Okay? This has to be Zito. Okay? This has to be zero because we're pullin what you'll write. You will write like something So answer equals Answer X or let's in any of daddy's A If I Okay, so basically, when the value if I zero that is the first element. So that's why you have to initialize with zero. Because you can see this is the property Zito X or any element is basically that element only. Okay, so you have to initialize your on set with zero. This is compulsory. Okay, Now that that's right, the good. So basically, this is a live court problem. Okay, so now let us right the court. Okay. So let's change the name of the area to be a So we have to return that in future, That is appearing only one time. So first, let us create a variable answer which will contend that unique element. And this has to be initialized with zero. Okay, so now what we have to do, we're just treating over the area so you don't Saiz. Now, you just have to take the ex, sort off all the elements, okay? You just have to take the exit off all the elements and finally, where to look, you will return. I would answer. Okay, So what I'm doing here So let us consider this example for 1 to 1 toe. Okay, so I have four. When? When and then toe. So this is one. Okay, so my answer is initially zero. Okay. Our answer is initially zero. Then I will take the extra with the first element. So it will becomes zero X or for so this is basically for Then I will take the I will take the czar vidi one element. So this is for X or been so this is basically for excellent. Only then I will take the exit off to So this is four. Exhort when and then. Okay, so this is the value of fun, so you can see answer. Oh, but it did at element. So this is the answer. This is the operator and this is the element. OK, so then I will take eggs or with one So answer. What is the answer? Answer is four excellent exhort toe. Okay, So this is the answer then the operator and then the area element, which is when Now what will happen? This one and this one day will cancel out each other. So this is basically for exhort to okay and then this element to So I went on civility, which is? The current answer to our current answer is four x or two, then the operator X or operator and then the element off the area to so this too, and this to devil cancel out each other. So basically, when we will come out so I will reach here. So basically, we will come out off this four loop saffron, several contained for which is the right answer, and we will return their cancer. Okay, very simple. Now, let us submit our good. Okay. Okay. So of a court is working fine. So let us some rays. So basically So basically, we have discussed three approaches for solving this question. First approach was basically the sorting approach that time complexity was basically and Logan and this space complexity was ordered off. One. The second approach that we discussed, it involves the use off hash map. Okay. The time complexity we discussed was big off and and the space complexity was also big off . And so we can see here We are improving on their time, but we're taking more space. Okay, now that 30 that the elevators, all this question is basically with help off Exor. Operator. Okay, that time complexity is basically big off and and the space complex, it is basically big off. Okay, so this is the best approach for solving this question. Okay. And what are the properties off x or so? Any element. Excellent. With the same element. All put will be zero. Any element exerted, zero basically will be that element only. And the third basically is the associative property. So a eggs or be X or a is basically nothing. It is same as a X or a X or be so this will become zero. So I have zero x or be. And this isn't a thing, but be okay. So in short, you can write this A and disabled cancel out each other, your output will, baby. Okay. So I hope you industry this question. Thank you.
8. Two Sum: Hi, everyone. So today we're going to solve this question gruesome. Okay, So what is the problem? Serpent, So promised in rate is very simple. You will be given I in prudery in Dejan Pernetti, and you will be given our target value. So what you have to do, you have to find two numbers in the area. And if you let those two numbers the some off, those two numbers will basically be close to the target value. Okay, so in this case, the target will lose nine. So we have to find two number inside this area. Who? Some. If you will add those two numbers, then we will reach the target value. Okay, so in this case, you can see if you letter to and you will air seven, then seven plus two. Okay, So two plus seven. That is basically nine. Okay, so what? We have to return. We have to return. The index's off these two numbers. Okay, so this is 0123456 and seven. So, basically my answer basically be it will contain index four and index seven. Okay, so my answer will be four comma seven. Okay, so I hope you understood this question. I'm repeating myself. You have to find two number inside the areas such that if you lead those two numbers, you will reach the target value. Okay, so target value will be provided by the user. And Okay, so this will be input. The target will lose nine. You. If you were lead to and seven, then you will reach the target value and what we have to return. We have to return the indexes off the elements. Okay. Off the area. Now. Have a console. This question. So the first ray, this is the brute force. Are you against a naive approach? So what do we do? We will just I told over the area. OK, so pick one element. So what I'm trying to say here is pick one element. I am picking 11. Okay. What is the target value? So target will lose Basically nine. Now what we have to find, we have to search for minus two inside the area. Okay, so this naive approach says, pick one element and find the other one. Pick one element. Let's say this element is the never There is a Let's see this element is if I and then it says after picking that one element search for the other element in the area. Okay, so search for other element inside the Harry. And what is the other element? So that element does nothing but target minus a fee. So in this case, if I will pick 11 then target this. Basically nine minus 11. So basically, we have to find minus two inside the area. So what I will do? I will. I trade over there. Harry and I will try to find minus toe. Obviously minus two is not present. Then what I will do? I will pick 15 after picking 15. What we have to do, I will search the area. So nine minus 15 is basically minus six. So I will search this area for minus six. Obviously minus six is not present. Then I will pick this element. When? Okay. Then I will search the Eddie for the element it because one plus eight days. Nine What? It is not present. Then I will pick element for And then I will search the area for the element five. Because four plus five is 9.5 is not present. Okay, then I will pick two. I will pick two and then I will search Dari. I will search this area for the element seven because two plus seven is nine and seven is present. Okay? And we will get our answer. So I will return the index off to and I will return the index off. Seven. So that's how I will be able to solve this question. OK, so the approach is very simple. You just have to pick one element and then you have to search for other element. Okay, so what it will look like. So you will have four loop. You will have two loops. Okay, So one lope is for picking the element. So this will start from zero. And let's say this is I less than and and I plus plus and what they have to do. So pick one element. And after picking. So this outer loop is basically picking one element. This is for picking element, and then you will have in a loop. And what this Inner Lupus. So, basically, what is what we have to find for? Let's say its name is key. Sochi's nothing but target will loom, which will be given by the user minus the current element. The element that we have picked. And then you will have one loop. So the slope, let's say the name of variables, Jay. So this will start from my placement. It will go till the end of the area. And it will check if the every element which is aging if very element is question the key or not. Okay, so what is their time in the space complexity? So time complexity. Basically, there are two loops, so that time complexity is and square. And what is the space complexity? So we're not using any extra piece so that space complexities basically big off when. Okay, so this is the brute force approach. Okay, so obviously we can do much better how they can do much better. So what we're doing here is we're picking one element. We are picking one element, so it will take order off end time, and then we are searching the area for the second element. So it will also take big off and time. So can we optimize this time, Toby Golf One can research in one time in constant time. Yes, we can do the searching. We can do the searching in constant time with the help of hash map. Okay, in high strip, searching is big off one. OK, we can assume in hash map. Searching is basically big Goffman. So we are picking every element that will take or different time but for searching, but for searching inside the area, we will take constant time. So basically, our time complexity will become all drop in and the space complexity since we're using hash map so it will become order a friend. Okay, so we are improving on their time, but we are taking extra space. But that's not the problem. Okay? Space is generally not a problem now how we can use hash map. So let us consider a small example. And let's see how we can take the help off hash map. Okay, so let's say 47 to 985 entry. Okay. And what is their target value? So let's say the target value is Well, okay, let's hit the target. We'll use 12. Okay. So let's make it 13. This is starting. Okay, So, yes, I have nine. Blustery were testable. Okay, so let's see what we can, how we can use the hash map. So I will create a hash map. What is the key and what will be devalue? Sochi will be basically element given re element. And the value will basically be the index. Because you can see, because you can see in the question what they have to return. So we have to return. Basically, the index's okay. We have to return the indexes, so we have to store index. So in this case, two plus seven is basically nine, so I have to return the index. So this is in next zero. This is indexed one. So I'm returning zero comma one, since I have to return the index in the question. So that's why the valley will be index. Okay, now how we can use hash map. So let us. I'd read over dairy and we will prepare our hash map. And simultaneously we will get our answer. Let's see how so I'm standing here and my hash members m pretty, so I'm standing at four. So what? Every loom, What is the value? So I have to search for So basically 12 minus food is basically it. Okay, now search it inside the hash map. So such it inside the hash map, hash members, empathy. So you will not be able to find it. Okay, then move ahead. So, while moving ahead pushed the element inside the hash map. So the elemental before and it's index zero now I'm standing at seven. No, but we have to do so. We have to find the element. 5 August five is already present. Let's change its value. Toe six. Okay, so this is basically six. So I am standing guard. Fife. Now I have to find Element Fife now searching the hash map. So element five is not there. Then move ahead. And when you're moving and pushed the element inside the hash map So the element of seven and its indexes one now you're standing there, too. So, four to my target, Errol Louis, 12. So find a 10 office lieutenant is not present inside the hash map. Okay, so I am doing searching inside the hash map. Then there's not present. Then move ahead and push to inside the hash map. So element is too. And it's a nexus to no nine. Okay, so for nine, But I have to do. I have to find three. I have to find three inside the hash map. So three is not present. Then move ahead and push element nine. So I'm pushing, eliminate and its index history. So this is element Hardeen. So for regiment Tartine, obviously, what we have to do. So I will search for minus one. I will search for minus one inside the hash map minus one is not present. So I will push Tartine and its indexes for And then I will move ahead. So I will come here. So this is element six. So for Element six that their elemental basics Okay, six plus six system. So search for six inside the hash map. And obviously six is not present. Then move ahead and push six. So I have six and its indexes. Fife. Okay, then would never lose. So I will reach here. 343 What I will do. I have to find the nine inside the hash map. Find a nine inside the hash. MIP so nine is present inside the hash map. And what is the index off? Nine. Index off nine is basically three. And what is the index off this element. So the next of this element, that's basically six. So our answer will be three comma six. Okay. So forgetting the element off. Forgetting the index off element nine. I'm storing the index. That's why this value has to be Index Gesell. After finding out nine, I will get its index, which is three, and the index off the current element, which is six. So I will prepare my ancestry com a six and then I will return my answer. Okay, So one thing to note here is if you want to search inside the hash map, you can only search element. You cannot search index. Okay. We can only basically hash members. Nothing. It is a key value pair. Okay, It is a two way Lupien. So if you want to find something inside the hash map, you can only do searching with the help of key. You can only search key. You cannot search value. Okay? We cannot search value. We can only so much g. Okay, So our given re element and our value will basically be index. Okay, so now let us right the court. Okay. So what? They have to return So we have written that. Paraffin Peaches. Okay, so let's say I have vector of indigenous answered. Okay, so now let us take our hash map. So I'm using an ordered a map. So I ordered map What? We with a key. Sochi is basically in danger and the value will basically be impeded also. Okay. Name is my map. Now let us just I trade over the area so foreign. Let's change the name. Okay? Okay. So you don't size now. What do you have to do? We have to search for so such what element? We have to search. We have toe search target minus if I inside the hash map. Okay. Now let us search inside the hash map. So my map dart, you can use count function, or you can use find function. Okay, so let us use common function. So Okay, so let us use find function so fine function will take and put a ski. Okay. And what is the key keys? Such So if the key is not present, So that will be my mapped out. And so basically, if the key is not present inside the map than what we have to do we have to push the current element inside dimap. So my map, what is the king is the current element. If I and what is the index in Texas? I okay in the else part were found of a search element inside the map then, but you have to do we have to prepare our answer. Okay, so answer Dart. Push back. We have to push two elements. We have to push through indexes. OK, but through the first index, So first index will basically be You can see here. So the first index is basically the index often nine. Okay. And how again? Obtain Index tree? It does nothing but my map off nine. My mother's name is basically three. Okay, so this is nothing, but my map off nine. And with this 99 basically is is the search element. OK, search and let us push the current index. So what is the current and ex service? I okay. And we can be done. Our answer. Okay, So this is the computer lettuce in our court, and then we will try to some might have a cold. Okay, So what is the problem here? Okay, so what do you have to do for the compilation purpose. See the return type of this function? What is their 10 type? This is Retrophin Teacher. Okay, so for the compilation purpose, I have to get it done answered here also. Okay, so I didn't miss Take care. Basically, this court should be in the if part and this basically let's make it. And OK, so if we are not able to find the search element, then I will push. And if you are able to find, then I will prepare my answer. Okay? Okay. So our court is working Fine. Now let us try to summer travel. Cool. Okay, so our gold is working fine. Okay, I'll court is under percent. Correct. Now let's see how how good is working. Let us dry Another good for this input to 7 11 and 15. Okay, so first thing that we get out of it, it was You do because I have to return a vector often, teacher. Okay, so basically, if we learned right, they return statement here, you will get the compile ation letter and the completion will be Basically you do because you have to return backed off in pages and we were not a turning anything. Although this line will never get executed. Okay, We will always be able to find our answer if there exist one. Okay, Our does die in this input. So this is my map, which is empathy. Okay, so my map is initially m pretty. No, we'll be irritating over the area. So first element is basically two. Okay, so target minus two. So target is basically nine. So nine minus two, which is basically seven. And then what we are doing, I'm using defined function. So find function is the inbuilt function, and find function will take input s key. Okay. I told you we can only search game. We cannot search value. We cannot such well, you know, I can only search with the help of key. OK, so I'm so *** and he's basically seven. Okay, so search G seven inside the map, and obviously you will not be able to find seven because the map is empathy. So what will happen? You will reach the end pointer. Okay, Now let's support this is a map and suppose there cement breeze. Okay, lets say 23 and five. You are finding seven. So seven is not president. Side the map. So this is the end point. Okay? This is not and this is north and this is the end off the map. So what do you know what will happen? You will search seven. And finally you will reach the end off the map. So if you will reach the end of the map, it course equals my map. Horton, if you will reach the end, that means seven is not present. So if the seven is not present what I'm doing, I'm inserting Element and its index. Okay, so my map will look like this. I am inserting the element if I which is do and I'm inserting its index, which is zero. Okay, so two comma zero. Now move ahead. So I will come to the elements. Seven. I will come to the Element seven now for elements seven, what does not target value. But what is my search value? So I have to search for two. Okay, so nine minus seven is to target minus seven is toe. So search to inside the map. My member would find too. So if you will find if you will search for two. Yes, Who is present? So basically this condition is false. Okay, you will not reach the end. This is the end, so you will not reach. And if you're not rich and you will prepare your answer answered hard pushback. So I'm pushing the element so answered or prospect my map off such so my map off. Do so if you will write my map off to, then you will get the answer zero, which is the index. Okay, so I'm writing my map of search, which is basically zero, and I will push the element zero. Then I'm pushing the current index, which is one. So I am pushing when so zero comma one and then I'm returning my answer. So that's how the scored is working. Okay. Okay. So this is basically the key. Which Julian? Teacher, This is the value which will also be in teacher. Then I have to search for the element search. If the element you're trying to find is not present inside the map, then you will reach the end off the map. Okay? If the element do you want to search is not present inside the map, then you will reach the end off the map. If you are reaching the end of the map, the element is not present. That means push the current argument. Okay, so I'm pushing the current element. And if you are not reaching map dot and that means the element is present. Okay, if you are not reaching the end that mies that target, the search will lose present. Okay, So the search value is president. If a search will lose present, simply prepared your answer and return. Okay. So my members search, it will have done me the index, and this is the current index, and then I'm returning my answer. Okay, So, as discussed that time complexity. So what is the time in the space complexity. So, what is the time? Complexity. So as you mean, there are, as I mean, they look up in the hash members big off one. So the time complexities, big off and and the space complexities because And for the hash map. Okay, so searching and hash map takes over time. Okay. We can assume searching hash map takes over in time. Big off. One time. Okay, so this is the time in the space complex sitting for this solution. Okay, So if you have any doubt in this question, you can ask me. Thank you.
9. Excel Sheet Column Number: Hi, everyone. So today we're going to solve this caution. Excel Sheet column number. Okay, so what is the question? So question is very simple. Basically, we will be provided with the column title as it disappeared in the Excel sheet. And we have to find the corresponding column number. Okay, so basically they input will be a string. And this string is basically the column title, and it will contain all uppercase l fiber. It's okay. It will contain all uppercase alphabet's and what we have to do. So basically, we have to find its corresponding color number. Let us take some example to understand. Okay. For example, this is the column title, then the color number. This one. Okay, if the column titled Let's Be, then no color number is two. If the column title is is it, then the column number is 26. Okay, so let's see this this one example. So this is basically when and this is basically during the six, multiply well, and if you will lead these two, I will get 27. Okay, so be is basically to this is basically turned the six month to play in the value of phase one, and if you will lead these two, I will get guaranteed. Okay, so this is the value of a is well, so the value off this is basically going to six. Multiply. Well, the value off this is basically going to six. Ready to play 26. Well, to play one. And if you will lead these tea, then you will get 703 Okay, So the value off way is basically during the faith. The very office that is basically 26 multiply and the values there this run to six. If you will lead these two, you will get 701 Okay, so this is nothing. This is just the implementation problem, okay? It is only implementation problem. So what we have to do? So what we will do? Suppose I've a string? Let's say ABC. So this is basically the column titled What I Will Do. So take the value off D, which is 1234 So it's very well before the value of sales. Basically three and three. We'll multiplied by 26. The Valley off B is basically to, and they will multiply it with guard the six and to 26. Similarly, the value of phase basically one and we will multiply it with 26 multiplied from the six multiplied 26 mark deployment. And then we will add all these fools. Okay, so we will add So basically what we have to do. So suppose this is a very long string then what we have to do. So I will start. I'd reading from the end. Okay. I was started reading from the end. I will take a variable power which is initial even. And each time this power will get multiplied by 26. Okay. And I will find out the value off the character and I will multiply in the valley of correctly with the power. Okay, so let's right the court. So basically, this question is present on lead. Cored. Okay, so now let outside the court. So we're going to do is so the plan is very simple. Let us take one example to industry. So suppose I have this A and a. Okay, so I will start are dating from the end. Let's take a variable answer which is initially zero. Okay, so the value off a is one and initially the value off power is one. Okay, so the value of phase one. So what I will do? I will. Right on circles. Current answer. Bless the value off the corrector. So in this case, this is one. Okay, so one multiply power. So power is also one. So answer requests zero plus one into one. So the valley off insert becomes one. Okay, Now let us come here. So their value off is basically one, but it will get multiplied by 26. Okay, So what I will do? I will. Right here. Violet Equis. Our marriage appeared 26. And now execute this line again. Okay, so this is basically on set equals the current really off answer, which is one. So the value off a is one, and the value of power is basically a 26. Okay, if you like these two, you will get going to seven now for this one. So the answer is basically a 27 plus. So what will happen at this point? I will multiply power, my grand basics. So the value of power waas already 26. So the sister into 626 basically turned the six square. So this will be 676 Okay, so 676 multiply the very off a which is one. And if you will lead these two. So this really basically so. 76 13 7 to 9 and 10. So this really basically 703 Okay, so let's see about So 703 is the right answer. Okay, so another just write the code. So as discussed initially, my I said, is Tzeitel. And initially I have a power variable which is initial even. Okay, I will start a dating from the end. So that is find out the size off the string. So as darts size after finding the size we have toe, I dread from the end. Okay, so now let aside rate. So the last indexes and minus one and the first index is basically zero. I remain this madness. So what? We have to write. So it's a quiz answer place. First of all, you have to find the value. So this is a Sophie s. If I will give me the character minus 64 by 64 because the ask I really off capitally. Okay, so I'm writing. Here s so Phi I minus 64. So this is basically will give me a character. Okay? And this is 64. Basically, the ask Everly of Capital is 65. Okay, but here in our problem, the value of phase basically one. So what I will do? I will lose 65 minus 64 so the value of fate will become one. Okay, so basically, this is connected. Minus in Peter. So whenever the situation is krypton minus in pdf, what will happen? So this corrector will be converted to its ask a value. For example, if this character this be so the ask, I value what will become so it will become 66 I am subtracting 64 so it will become toe. And obviously the really off be in, for our problem is basically to okay. And now what? We have to look so we have to multiply with the power. And now the power will increment. So power equals power Multiply during physics. Okay. And finally, when the loop will end, we can return our answered. Okay, So very simple. Okay, so now let us submit our answer. Okay. So what is happening here? is We are getting runtime error at this lane. Power equals power. Amount of light 1 to 6. And why we are getting runtime error. So basically So basically we have impeded the type. So the in digital type, the maximum number it can Stories are brutal to the power tart even. Okay, in surplus place. So this is nearly 10 to the power nine. Okay, Now, suppose this power number is a very big number and what we are doing. So we are multiplying this big number with 26. Then what can happen? So this resulting number, it can become greater than 10 to the power nine, which is the range of the in future. So if this is the scenario, what will happen so we will get a runtime error because this big number cannot be stored in an integer variable. And this power is basically are nt jitter type. Okay, so what does all this question where you can do so? We have a data type long, long so the range off long under the type is basically it can store numbers which are a prudent to the power 18. OK, so this is the range for long, longer the type. So if you would use long, longer type for the power variable we will not get her anti mirror okay, because this big number can be stored in the long longer the type. Okay, so let's change to the type of the power variable. So instead, off using and teacher, what we will use we will use Long, long and hopefully they should work. Okay, now let's summit. Okay, so our gorgeous working fine. OK, so now let us discuss the time in the space complexity forever cold. Okay, so basically the space complexities order off one. We're just creating only free variables, okay? And that time complexity is basically order often big off. And we're and this t basically the size of the string. OK, so we are just hydrating from the end of the string towards the first. Okay, so we are dating from the end of the string. OK, so the time complexity is basically lenient and the space complexities basically big off when. Okay, so if you're having it out in this question, you can ask me. Ok, thank you.
10. Intersection of list: Hi, everyone. So today we're going to solve this question. Intersection off to link list. Okay, so we are provided with their to link list. So this is our first link list link list, and this is our second linguist linked list. Be okay, so we have to find in the section point and the intersection point is seven. Okay, so this should be our output. Okay, so this is the first link list starting from even. And it tends at C three. And this is our second link list starting from even. And it landed. Sit three. Okay. And basically, our intersection, we have to find the intersection. So then the section is see, even. Okay, so this should be our are put. Okay, We have to our put this note so this question is present on lead. Cored. Okay, So intersection of the two link list. So as you can see here. So this is the first example. So link list a 41845 and link list be 501845 So our our port should be eight. Okay, Now, let's even more example. So link list in which is 09124 and link list being which is 3 to 4. Southport should be too. Now, hear, This is special case. Now, In this case, the link list do not intersect. Swelling close days to 64 and the linguist bees one in five. Okay, so in this case, are our portrait venal. Okay. And these are some of the notes. Okay, so what we have to do? So first of all, if they're to link list, do not intersect. Okay? If there is no intersection point, then Avatar butchered venal, okay? And we don't have to change the link list. OK, we do not change the link list. We will. Large is a link list. The destructor off link list must remain the same, and we can assume there are no cycles. Okay. No sanctuary. For example. This is the first link list, even you to a tree. And suppose there's a cycle A for this pointing towards a tree. OK, so this is a cycle now in this problem cycle will not be there. OK, we can assume there are no cycles and probably have a call. Children at one time and open space. Okay, so we have to take linear time and constant space. Okay, Now let us try to solve this problem. So how we will approach this problem. OK, so first of all, let us think about the brute force approach that are very naive approach that we usedto never used in area. OK, so what we can do here is so first. But it will do so. Let us discuss approach number one. Okay, so brute force approach. So the first orbit for the first operate sees pick the first Nord and then I'd read over the second link list. Okay? They will not be any match. Then pick the second note off the first link list. And again I drilled over the second link list again. There will be no match. Then pick the turn old. And then again, I did over the second Linguist. Now, in this case, they will be a match. Okay, so if there is a match, we can output ourselves, okay? And similarly, at this point, our program will stop and we will return seven. Okay, so this is a veritable Luso. Suppose we have to Aires Area A and Area B. So every has some elements even it to end a three and ever be even veto be tree and before So the approach is very simple. Pick the first element. I told over the secondary pick the second element again I told over the secondary like the third element I told over the secondary pick The fourth element photo element is not there at a finished and would not find an intersection point. So that means at a A and B do not intersect. So in this case, we can return them. OK, so this is the brute force approach. So what will be their time in the space complexity? So in the case of brute force approach that time complexities what we're doing here, Let's see the list. Let's say the length of the first link list is M. And the length of the second link list is in. So time complexities. Emma Udwin. Okay. And the speeds complexity is over. Okay, constants. Peace. Now let us try to court this. Okay? So I will. But I didn't c++ so we are provided with the to link list link list A and link list be okay . And we have to return the intersection point Okay, So what is our approach? So let's say violence is not a questionable. I am iterating over the first link list. And now what I will do. I will select the first, nor I will select every north off link list A and then I will hydrate over the link list. Be okay. So since we have tried it over the second link list so I'm taking a pointer. Now, this pointer, it will point it will point towards the head off. So this is head had to, and this is pointing towards be okay. Now we have to I did over this link list. So while head to it's not the questionable. Now we just have to check. Okay? So we will check if a equals equals Had to. Then we can have done There is an intersection point, so we can have done a okay. Otherwise, what you have to do so had two equals. Had to edl next. Okay. And outside the loop equals next trophy. Okay, Now, if the vilo pins so we can safely say here, so if they've I loop end, then we can say there is no intersection point. Okay, so we will eternal. Okay, so this is our very simple cold. Now, let's try to another. Good. Okay, so this will be heading to Okay, so our guard got accepted, not a destroyed to submit. Okay, so our good is getting accepted, but it is not very good Cold. Okay, so we can do optimization. So what documentation that we can do here is so first of all the time complexity off discord. So we discussed the first approach, which is the brute force approach time complexity is Eman and the space complexities over. OK, knowledge just discussed the second approach. So the second approach will make use off map. Okay, so what we're gonna do is so let us take an example. So the distinct one example. So for one year for five, so four when air for five. And we have second linguist 501 So this is 50 and what? Okay, so our output should be eight now, with the help off map. How can you solve this problem? So what they're gonna do here is So this is our first link list, and this is our second link list. So pick any link list for example, I'm picking. Let's a second link list. You can pick you also. But let's say I am picking me. Okay, now what they will do, we will take a map and the structure of the map will be so the key will be north and the value will be Let's say a 1,000,000,000 little power falls. Okay, so a bullion value through our faults. Now we will I date over link list. Be okay. Suppose I am. Choose England Clizbe. So we light over the second link list. So what? It will do. So Fife 1st 5 So five through zero. True. When drew it through food through and five group. Okay, so this will be the structure off our map. Okay, so this will be our map. So when sour map is ready, but it will go. We will. I'd read over the second link list the remaining link list, which we didn't choose. Okay, so I choose be for making the map now. I will. I'd rate over the link list. A Okay, so four. So it's four present, so these are not values. OK, so this is value, But I am starting, Lord. Okay, so basically I'm storing five. And I'm also starting the address off its next note. Okay, I'm not storing the value. So this four and this four, they're not equal. Okay? I'm storing the node. I will store note. Okay, So this four and this four, they're not equal. Okay? Please don't get confused. So the structure off north is so it will store the value, and I have a pointer next. And this is the address. Okay, so then I am comparing the north. We're storing north. So when we're comparing than or we're comparing the value and we're also comparing the next pointer. Okay, so here I am Story into things. Five and the next pointer. So this four and this work, they're not equal. Okay, then I will compare when I will compare one. So is one present. Yes. When his Lord present one is present. But their nautical okay, not equal by nautical, because the next pointer is different. It now eight present. Yes, it is present. So here, what will happen? Value will be get matched. And the next pointer will also get matched. Ok? Because we're storing the north. So since both the values get matched so we can return. Okay, so here we will return it and have done it. Okay, so this is how we can use map. Now, we're doing the time complexity, so their time complexity will be so first awful. I am making this map. Okay, so we will use an order to map. Basically, we can assume the access time is constant. Okay? Over in excess time. So, first of all, I am I trading over the linguist be and let's say it's lent to them and it's letters. And so first off alarm trading over the link list be to make the map. So in, then, I've illustrate over the first link list. And so the time complexity is basically implicit. Or you can say legal time complexity. Okay, clean here. And what is the straight spunk? Laxity. So let's say if I'm choosing B so the space complexities order often. Okay, so I am assuming here the access time off using the map is open. Okay, we are using an order to map. Okay, So basically, there are two types off maps. 1st 1 is theon ordered map, and the 2nd 1 is map. Okay, so on order means basically will use hash table to implement the an order map and for implementing them that basically we use a balanced BST. Okay, basically red black three. Now, that doesn't prevent this approach. So I will come into school and we'll write the court again. Okay, So first of all, we have to make an order to map. No. Then read a map. The key value will be the north, and the value is bull. Okay, so let's say the name is my map. Now what? We have to room. We have to pick any old let's say I am picking be so to make our map ready. So while b is not a questionable, I am are treating over the second link list and what we have to do. So my map off me, it's true. Okay? And then B equals next. Overbey. Okay, so at this point, our map is ready. Now, what we have to do, we have to hydrate over the first link list. So vile is not a questionable. And now we will check whether the node off the first link list is present in the map or not . Okay, So if my map right count. And I will give a so this corn function what it will do. It will check whether the North is present in map or not. Okay, so if it is present, if the North ace present in map If the North is present in this map, that means this nor was also present in the second link list. That means this is the common north again. This is the other intersectional, so we can simply return a The raise will move ahead. So equals a I don't next. Okay? And if there's no intersection, we can simply tunnel. Okay, so at this point, there is intersection. Okay, so what this current function will do this current function will check whether this Nordea is present inside the map or not. Okay, so if there's no days present inside the map and that that means this Nord was also present in the linked list be okay, that's then only they can be an intersection. Okay, so this is our complete cold. Now let us try to the narrow cold and then we will summit. Okay, So our court is getting a separate. Okay, Have a good is right now we will discuss the best approach. Okay, I'm go ending this court now. It does discuss the best approach. So we have discussed to approach the brute force approach. And the 2nd 1 this map approach. Okay, so this is the time complexity. So the time complexity is linear. We do not have any problem with the time complexity. What we have problem is this space. What do you want to do here is we want this space to be constant over in space. Okay, so this was the property of the problem. OK, so the problem access to solve this problem in linear time space. So with the help off map, we can solve it in linear time. But it is taking or in space and the space is due to map. We're make me a creating map. So the spaces due to map, we want to optimize it. Two constants. Peace now how we can solve this problem. So what you're going to do here is so our approach will be very simple. So the sister first link list see, once you do see three. And they had said to serve a second link list. So Beaven Mido B three and before and then 17. 23. Okay, So what will you do? We really likes it. This is linked List aired. This is Linguist me. So we will use a very simple approach. Okay. And approach will be. First of all, we will find the length off link list. So let's say this is M. So M is basically land trophy leant offline. Christie. So in this case, it will be 1234 and five. So this will be five. Similarly, we will find the length off link list be. So in this case, it will be when 23456 and seven. Okay, so this is seven, then ready. Will do. We will subtract these two. Okay, we will subtract. So basically, we will do and minus m. Okay. So what will happen after the subtraction? After the subtraction, we will get to Okay, so when we're subtracting So this is the commenting, okay, despite this common in both the link list. So when we're subtracting the length of these to link list, so this part will get diluted. Okay, So the difference is basically to only so and minus. I miss too. Now, what is the value? What is the significance of this two? Let's call this D. Okay, so d is basically the difference between the difference of the length between the two link list. Okay, let's quality. Okay, now, this is the bigger linked list B. So what we will do? We will make. We will jump two steps ahead. Okay, so we will jump two steps ahead. So first to jump and the second jump. So basically, we are here. Okay, so we are standing at this point. We are standing at this point, Okay? Now what they will do. So this is a And this is where we are currently standing. Okay, so these other two points now, now what we will do, we will move ahead in both the link list. Okay, Now, these two points point this 1.81 endpoint between both these points are equidistant from the intersection point. Okay, so both even and Vetri, they are equidistant from the intersection point Why they are equidistant because their difference was to Okay. The difference was two and in the bigger list. I made two gyms. Now there is no difference. Okay, we are standing at a equidistant from seven. Now we will move at in both the link list, so I will move ahead, then move ahead, move ahead and hair will be our intersection Point. Okay, so the approach is very simple. So step one. Find the length off both the link list. Finding length of board the link list. Second, take the difference off the link list. Big difference her step Move ahead in link list. Be okay. I'm assuming bees the bigger list. So move ahead and B, how much we have to move defense. Okay, now, fourth point, they are equidistant. OK, so both the points are equidistant from the intersection point. And the fifth step is move ahead in both the link list. Move ahead in both lanes list. Either you will get the intersection point all there's no intersection point, then we will redundant. Okay, so I'm assuming that be link list is bigger One. So if the a link list is bigger than every loose lamp, Okay, Now let us right the court. So first of all, it is First write a function to find the length. Okay, So I have a function lent What? It will take it will take a list. It will take the head of the legs and little Lord undulant. So initially the count is zero. Okay, so now let the side street. So while head is not equal tunnel, we have to look on plus place and then head equals next off, Ed. And then we were done. Count. Okay, so this is our land function. Another time complexity of this land function is when Okay, No, what we discussed we will find the length off board the link list. So M is basically the length of the first link list and is the length of the second link list. Now we have to take the difference. Okay, So difference absolute function. I am taking the absolute function because I don't know which one is bigger. Okay? And let's do and minus him, you can go and minus. And also so absolute meets our deservedly re positive. Okay, this is the significance off absolute now, since we assumed that lent their link list B is bigger, so I'm checking my assumption. Um, so if and Mr than in, then we will simply scrappy and be OK. Well, simply sepia and be Now, basically, at this point, we can safely say B is bigger. Okay, B is a bigger link list. Now, if you have to do so, as we can see here, we have to move ahead and be okay. How much more weird defense. So their defense was D So their defense was d basically And I call zero I list in the and I plus Plus I have to move be steps ahead in the second link list. So basically V equals next off B now it display. And what is the scenario boat? Both A and B. They are equidistant from the intersection. Point A and B are equidistant from the intersection Point Ok, simple. Now what they have to do, we will move ahead in both the link list. Okay, So vile A is not questionable. And simply b is north questionable. I have to move ahead in both the link list. OK, so if a quick squeeze be that means the intersection point. So if it is intersection point, we can simply returned a what? We can simply it and be ok. Other ways equals next trophy and B equals next of B. Now, if the Vilo pens. That means days. No intersection. So we'll simply tunnel. OK, now let's turn our good and then we'll submit. Okay, so line number sent to do. Okay, So Okay, So now let's summit. Okay, so our gold got somebody. Now see the difference. First, you're 20 milliseconds, then 76 millisecond. And this is a village decimation 40 for milliseconds. And you can also see them a muddy. Okay, 16.9 memory. Now let us. So in this case, where is the time complexity. So first this land function, it will take women name and again. Who in time then we are moving ahead, basically all the time. And then in the worst case, when there's no intersection, it will take, let's say, basically criticism over in time. So basically, they're time complexities, linear okay and blessing time. Complexity is linear and space complexities over. We are not using any extra space. Okay, so this is the best solution we have. Okay, this is the best solution. So this was here. The time complexity was mn and the space complexity was over. In this case, the time complexity was linear. Basically, when and the space complexity it was due. Do the map we have created. Okay, so this was lets it when? And this is our best solution. Okay, Time complexity is linear. And the space complex it is over. Okay, so this is all we can solve this problem. Okay, Now there is one more way to solve this problem. So the 43 we will not implement this way. But I'm just giving you more. If I did it, there also exists a four to me. No, how we can solve this problem. So even you do. And let's say this is Stephen and pseudo so again be even butto b three and then see what else you do. Okay, So what we will do really start from even We will reach the end of the link list. And after reaching the end, we will save this note. Okay, So we will save this Lord and then I will make I will make a cycle. I will make a loop in the link list. Okay, So what I will do? I will simply do see Tuero next equals a Okay, so this was a So now we have I live in the link list OK, now there is a problem. Detect cycle in the link list. Okay, Detect cycle in list. Okay, so this is a very famous problem. I will also solve this problem. So detect cycle in a list. This is a famous problem. OK, so with the help of this problem, if you have solved this problem, so what we will do, we will be able to find this even. Okay. With the help of this problem, we will be able to find seven. Okay, so this is our list will start from Beaven. And if you have solved this problem, you can understand that hole. We will be able to find Steven. Okay. If you don't know this problem, if you are a neighbor of this problem, then don't worry. I will solve this problem later on. OK? Best here. I just want to tell you that this is a very famous problem. And with the help of this problem, we will be able to find this even. Okay? Now what we will do after finding this even after we have the result. So what? We have to move. We have to remove this loop. OK? We have to remove this link. Okay? Because in the problem, it mentioned clearly that we do not have to change your business structure of the problem. Original structure of the link list. Okay, that's why I saved suit to here. Okay. So that we can do see Tuero next is no. Okay, now, after we know the solution of the problem after we get through this, even we will lose you to enter next question l so that the structure of the link list for donor or changes So a structure flink list do not change, Okay, because this was a requirement of the problem. Okay? No, let's Okay, So if the question was detect if there is an intersection point OK? Now the question was you have to simply return true or false. Okay, You have to return to our first. The return type of the problem is bull, and the problem is very simple. Detect intersection point, basil detection problem. Okay, We have to reject the intersection point. Now there are two link list even here too. And 72 c three, this is Beaven Butto B three and seven. C two c three. Now the problem that we have sold that problem asked us to find this even. But now what? I'm trying to Siri's. You have to return through our faults. Okay? You have to return through or you have to return. False. Basically you have to detect whether the tooling list intercept or not. Okay, so one days you can use the above a protest. Great. We have discussed. Okay, But since it doesn't ask us to find see even then why we should find Steven. Okay. We simply have to detect whether to north intersect with their to link list and protect or not. So what I will do, I would start. So this is a I will reach the end point off. Okay, So the endpoint off A's c three, then what I will do? I will start from B. This is B and then I will reach the end point off. Be so then point of being sc tree. Now if the endpoint if the tail off a is same is that they love be that means there is intersection at the race. There is no intersection. Okay, simple. You can also take this an example. 12 and this is five. And similarly. Let's say three, four and five. So in this case, the endpoint off the first link list is five and similar. Leader and burned of the second link list is also five. Okay, So if the endpoint of both the linguist, our steam, this intersection if then if then parents are different, there is no intersection. Okay, right. A simple problem. Okay, so in this case, But you have to do start from the first link list the standpoint Start from the second link list the standpoint. If then put the same these intersections to their time, complexity will 1,000,000,000 year and listen. And basically the space complexity will be constraints. Piece. Okay, over in space. So I hope you got gaiety of this problem. If you have any doubt in this problem, you can ask me. Okay. Thank you.
11. Reverse a List: Hello everyone So true. David will solve the problem. And the name of the problem is reverse a linked list. OK, so this is our original ink list. So the original in clusters went 234 and five and we have to reverse this origin link list . So after reversing the original ink list, this will be our answer. 5432 end one. Okay, so this is our input, and this should be our output. Okay, We have to basically reverse a link list. Okay, So how we can reverse a link list, So this is very easy problem. OK, so I suppose this is the scenario. Okay, so these are the nodes of a link list, okay? And suppose we have reversed some part of the link list. OK, so let's say the name of this notice previous North, The name off this note is current Nord, and let's see the name off this notice and okay, and this list goes on. Okay, So we're here, isn't it? Okay, so later says, um, we have already reversed this part off the link list. Okay? Now we have to reverse the remaining part of the link list Okay, So what it will do here is first truffle. We have three pointers previous, current, and Okay, so we have three pointers previous, current, and so the first step first ever table what we will do. We will save this. No. Okay. I have to save this note, so nor start in what? This end. This is basically the next off the current ignored. Okay, so I created this point that end. Now, if we have to do so after reversing what should happen? This current pointer, I should point towards this. Okay, So the second step is very simple. The next off current. It should point towards the previous. Okay. And this note, this link will get broke. This language get broken. Okay, so this is our second step, and our link will get broken at this point. Okay? Now, if you have to do so, but he this will become current. Okay, So this previous will come here. Okay? No previous is pointing towards current. Then we will do current equals. And Okay, so now current is pointing towards here. Okay, So this is current to no, and we have reversed this part of the link list. okay again we will We will put discord inside a loop. Okay, So what will happen? So this is current. This is previous and this will be our end again. We will break this link and we will make this link again. This will become previous. This will become current and it will go on. Okay, it will continue. No, I am liberating one more time. So let's say this is my previous Nord. This is my current in order and this is my next Nord. And let's see, there's one more north and then the end of the link list. Ok, so the first step we have to save this node. So for saving this node, I'm creating a pointer So North star in, which is basically the next off current. Okay, we have to save Distort. We have to save this Nord because we're going to break this link Now The second step is break this link and make this link So basically next off current is pointing towards the previous Okay, The next off current is pointing towards the previous node. Then I will make previous here Okay, previous ful point the words the current in order Okay, so this is previous? No. And then what we have to do Current will Come here. Okay, so this will be current. So current is basically in. Okay, so descend that we have saved. So current is basically this. Okay, Then again we will We will execute the same court. Okay, so this is current. This is n This link will get broken. I will make this link. Then it will become previous. It will become current. Then this will be in basically anvil Bennell okay and is no Then I will make I will break this link. Then it will point here current the next next off current disappointing towards the previous. Then previous will come here and then current equals end and was not so. Basically the current will become now. Okay, so when the current becomes no So I will make the condition of the Lupus. Vile current is not questionable. So when current becomes null, that means my link list is reversed and this is our head. Okay, this is our head of the reversed like list. Hide is basically nothing. It is previous only. Okay, how? It is basically nothing of this previous so after this loop, our head is nothing but previous. Okay, now what with the initial condition. So initially. So now let's say this is averaged a link list. So basically, current is nothing but head. This is previous, which is basically no so previous will be null initially. Okay. And this will be our end. Okay, now this question is present on lead hood. OK, reverse link list. This question is present in the liquor lead cordon. Now let us right the court. Okay, so we need three pointers. Okay, We need three pointer previous, current and and so current pointer, which is head initially. We need a previous point, That which is basically no. And we need a pointer. And Okay, so first let us right the loop. So while current is not the questionable, but you have to do we have to do four steps first, save the next world. Okay, First step saved the next note because the next Nord, because we're going to break the link in the next lane. So I have saved the next note and no, we can break the link. Okay, So the next off current is previous. No, we have to move ahead. Okay, so for moving ahead, the vesicles, current and current tickles Next. Basically in. Okay. Next Miss. And And when the loop over, when the Lupus finish. Basically, the head of the basically the head of the reverse Ling list is nothing but previous. So we will return previous, and that's all. Okay, now let's amid the court. So what is their time in the space complexity of our solution? So they're time complexities, linear, and the space complexity is over. Okay, so the time complexity is linear and space is constant. Open space. Okay, so this was very easy Problem. Okay. Thank you.
12. Add Two Numbers as List: Hello, everyone. So today we're going to solve this problem. Add two numbers as list. Okay, so basically, we are given to link list. So, linguist first and link list second. So this is our first link list to 43 So this is basically a number, and the number is 342 Okay, so to obtain the number, what we have to do, we have to read the link list in the reverse order. Okay, so this is our first number. So this is number one, and this is our second link list. 564 And to obtain the number, we have to read the linked list in the reverse order. So basically, this is 46 and five. So this is our number two. Okay? Now, if we have to do we have to add these two numbers? Okay, So after adding these two numbers, so direction will be a simple addition. Simple mathematical addition. So we will obtain five plus 276 plus forest 10. So we will have one carry and 431 so this will be it. So this will be Our answer is 07 is the number, okay. And What a real English. So the linked list will be 807 Okay, so this should be our answer. Okay, This should be our answer. This is the new link list, and we have to add those two numbers and we have to return this new link list. Okay, so this is nothing. It is bust. It is just basically an implementation problem. OK, so this is essentially an implementation problem. So one other variable straight we will need. So we will need a carry variable. In this case, when is the carry Okay? Okay. So when we are reading these two numbers six plus four. So we are getting tennis output. Okay, we will store this zero, and we will forward this one. Okay, so, basically, for storing the zero. So let's say this number is n okay. Okay. Call it some. So for obtaining zero. What? We will do some Martin. So we will get zero. And for one, basically, for carry what you will do, we will do some biting. Okay, So that's all we can obtain the carry, and we're gonna play in the desert that we have to put. Okay, so this is nothing it was just an implementation problem. And we have toe handle some cases. OK, so what can be the cases? Cases can be. The length of the linguist is different. For example, the length of the first link list is greater than the length of the second link list. Basically supposed the first link listers 243 and seven and the second Link Listers basically 564 Okay, this other cases similarly, the left the second linguist is greater. Okay, so basically, this is just on implementation problem, and we have to handle some of the cases okay to what they have to do. We have to create this new link list, and then we have to return this new link list. So this problem is basically a little cord problem, and we will ride the court. Okay, So first of all, if is not basically the first link list doesn't exist. Then what? We can do a particular result, So that is a little baby. Okay, now, if the second linguist is Nelly, we can return a Okay. Now what I'm planning to do here is Okay, So what we will do? I will keep one pointer here and I will keep the second pointer here, and then I will add to these two numbers. Okay. Simple mathematical addition. So the output will be seven. Okay, so the output will be seven. So I will make a new link list and I will start. Output is seven. Okay, then. This point that will come here. And similarly, at this point, that will come here. Then I've led these two numbers, so six plus four, which has been so I restore zero and I will get even. Okay, so I will store zero. Basically, I'm inserting ahead. So this was my head off the new link list. So what I'm doing, I will insert at the head. OK, so dissolute. My scenario and the head will come here. Then what I will do. So we have carry quits. One. Okay. At this point, my get is one. Then it will come here and this will come here. So this is three. And this is full. So I will add these two numbers. So four plus 37 and we have one carry. So that output will be eight. So I will put it in front off head. Okay, and my head will come here. Okay, so this is my result and number 807 So it's seven is the result in number, and but our output should be 70 It. So after getting this link list, what we have to do, we have to use the reverse function. Okay, well, we will use the reverse function, and then we will get our output. Okay. 70 It Okay. So this is how I am planning to solve this question. Basically, we will insert at head, and then after this link list is ready, we will use very worst function, okay? And everything else we can handle. Okay. We can handle this case. We can handle this case. Okay. No letters. Right? The cold. Okay, so we need a carry. Variable. Okay. Initially, the carry will be zero, and we also need every able some. Okay, So first, what do you have to do? We have to run the loop while board the linguist exist. Okay. So violates north. Questionable and vile. B is not a questionable. This case is too. So, for example, my first link list and my second link list. Let's say the first ring classes went toe and the second link listers 345 six and seven. Okay, so first of all, we have to solve this part separately, and then we will solve this part separately. Okay, so in this case, what will do? So we re led three plus 14 then four plus 26 And then every become ill. Okay, so when a becomes know what we have to do, we have to simply copied this part 56 and seven. Okay. Obviously, we will took care off, Gary. So if there's any carry, for example, it's that this is true. And this is nine. So nine plus two will be 11. So I will put one. And this woman one will be getting so five plus one. This will be six and then 66 and seven. So basically, we will propagate the carry. Okay, we will propagate the Gary. But when the first link list becomes null, then this is the scenario. This is the case is that we have to handle OK, so this is basically an implementation problem, okay? Just took care of cases and they will be able to solve it very easily. okay. And do not forget about the Caddy. Okay? We have to propagate the carry. For example, if this was also nine so nine plus one, it will become 10. I restore zero. I will propagate one. Let's say this is also 99 plus one. Then I will propagate carry and seven pleasant will be it. Okay, So this is how I am planning to solve this problem. Don't forget about the carry. So first I'm make I'm writing loop for this part while both the linguist exist. OK, while boat the link list exists so vile is not a question of land. While B is not a question of that means both the linked list exist. So what will be our awesome south? Some will be the value of a Okay, so this is you can see here value. So I'm using value here. Okay. In some, sometimes it can be data. OK, so value off a plus Really off b and please do not forget about the carry. So carries initially zero Okay. But it will not always be zero. So after calculating the some what you have to do, we have to create a new old Okay. We have to create the node, So list Northstar n. We are creating north to store the data. OK, so this will be new list Nord and what you have to do? We have discussed it will be some Morton. Okay? And what will be our carry? So our carry will be in basically some button Now we discussed that we will insert at the head. Okay, so I didn't created head pointer. So list Northstar, Let's call it head The head meets. This is the head of the original link the link list that I am creating so initially decisional initially the new linguist doesn't exist. So you re prepared. So I told you we will insert at head. Okay, So how do inserted head? This is very simple. And NATO next his head and then a beard. The head. So basically headache Wilson. Okay. Soviet inserting. Er, Ted, since we're inserting at the head position, we have to return. We have to reverse our link list. Okay. We have to reverse our final link list Now, at this point, what will happen at land number 24? I learned number 25. What will happen? So one of the link list finished. Okay, so one of the link list doesn't exist anymore. Okay, So one thing I have to move forward in both the link list so equals the next trophy and vehicles the next off being okay. Now, after this loop, one of the link list doesn't exist. So as we discussed here, So even if the link finished, we have to use we have toe right the court for the remaining link list. OK, so vile while a exists so basically violates. Not questionable. So what we can do? We can cooperate this much. We can co operate the school. OK, Control, seeing controlled me now, since Butte doesn't exist, so I will remove. Be, let's nor starting. I'm creating the new node. I am inserting ahead. Okay, Headache. Wilson carry some button than equals next trophy. And then we will move. Be now. If so, there are two scenarios either the evil finish or the B finishes. So if the be shorter than this court will be executed Now, if a finishes and be exist. So now viol B is not questionable. Basically, that means that B was longer and ever shorter. Okay, so this will be and this will be be base next of B. Okay, now I think everything is fine, but one condition is still remaining. Now what if the carry is not zero? Okay, so what if the cat is positive? So now we're dis planed. Now, suppose this was mine and this was one so nine plus one instants. So I will store zero and it will. One will begin the carry. So if the carries Nord zero if the caress positive, we have to copy the carry also. Okay, so if the car is not zero, we have to copy the carry so you can write If Getty s positive. Then again, you can cooperate the school. So basically, this will be you can simply rate carry here. Okay. Okay. So everything is fine now what we have to do, we have to reverse our link list. Okay, Now we have to reverse our link lists. Solar just right. The court for reversing. That includes two because we were inserting at the head position. OK, you can see here we are inserting at D head. Okay. Now for reversing the court, we need three pointers first. The previous which is initially inal the second pointer. Current point averages initially the head only. And we need 1/3 point that next. OK, so let us I trade or the link list. So while currently is not questionable, then the first step save the next node because I'm going to break that link. So I'm saving the next note. Now let us break the link. So the next off current his previous. Now let's move forward. So for moving the forward three bicycles current and currently CWilson. Okay, so we are moving forward. And finally, the head of the link list is nothing at this previous. So let us update the head. So where this previous and then you can return the head. Okay, so this is the computer code. So what is this time in the space complexity. So time complexities, leer and the space complexity his constant. Okay, so, Constance Piece. So what is happening here? It is. First off, while it is just an implementation problem, okay? It is just an implementation problem, and we have to handle few cases. Okay, so this is very simple. If one of the linguist doesn't exist, return the second link list initially the carry zero. So this is head had is basically know. Okay, this the head of the other, This is head off our linguist that we are making. Okay, So while board the link list exist, Okay, so scenario can be like one link list is bigger than the second link list. So if the Linguist days, let's say 123 and the link list bees one. So, in this case, I will lead these two. Okay. So some will be the addition off the value of faith and the valley of being. And obviously the carrier, at this point a zero, I'm creating a new node. Okay, so the new nor will be one bless one which is to next off in his head had is basically now . So basically the next off to is now then headed quiz. And basically this is head. Then carry some beytin. So some is basically went. Listen to So to buy 10. Obviously this is zero. Move ahead, move. Be ahead. So even come here and we will become them. We will become nearly so sense be becomes No, this loop is over. So is not a questionable we will execute this part and business so we will not execute this part. So it is not a questionable. Some is the value of a plus, Carrie, Carrie zero and the value of phase two. And I'm inserting a different overhead. So head was pointing towards too. And this isn't any. So this is to and next head so and then headed Question. So basically, this is head and Gary's against it because nobody and zero and then evil move ahead. So it will come at three. Then 32 and then head will come here and then able become ill after three. Every become Nell decisional and have a loop is over. So this is do you to do. But we have to reverse this link list. So after reversing the link list, it will become too to entry. And this is our output. Okay, so that's how so. This court is very simple. Okay, so go tell discord. So that's the first function is very simple. And then these are some cases that we have to handle. Okay, some cases that we have to handle, and yeah, I think everything is fine. Okay, so this is very this is very simple. Cold. Okay, So if you have any doubt in this problem, you can ask me. OK? Them complexity is linear and the space complexities constant space. Owens, Freeze! OK, thank you.
13. Partition List: Hi, everyone. So today we're going to solve this problem partition list. Okay, so the bonus treatment is very simple. We will be provided with the link list, so input will be a link list and a very off X. So, in this case of the value of X history now, what is the problem? So the problem is very simple, what we have to do. So we have to partition this list in such a way that all the values which are less than X should come before the values which are gooder than X. Okay, so in this case, what will be our output? So one do and toe. So there are. These three values are less than three. Okay, so when go to so all these three values, they should come before the values which are granted entry or request a tree. So this is for this history, and this is five. So 43 and faith. Okay, so this will be my let's say less and less values. And these are more values, okay? And what will be our our port? So our people, we will make this a link list. So one due to and this is 435 and then we will upend this part. Okay, so this should be our output. Okay. And one thing you cannot change. Daughter, For example, you cannot write like this to do when or similarly you cannot write. Like you cannot sort this part 345 You cannot write like this. This is wrong, because in the question, it is mentioned that we have to preserve the original order. Okay, so what do you mean by preserving the original order so you can see four is coming before tree. So in the output, four should come before three. Similarly, three is coming before five. So in the output, three should come before five. OK, so this is the meaning off preserving the original order. Okay, so we are preserving the original order of dealing list. Okay, so this is the question. So this question is present on Lead hood, and here it specifies that we have to preserve the original order of the link list. Okay, So we will be given a value X and all the nodes whose value are less than X. They should come before the nodes whose values are greater than the X. Okay? And this is my order. So these values are less than X, and these were lose are greater than or equal streaks. Okay, so we have to solve this problem and the expected time. Complexity is basically linear, and the expected space complexity is over. Okay, So constant space and linear time. Okay, so how we can solve this problem. So basically, what we are trying to do here is so what we'll do. So let's take about example only. So we have 143 to 500. Okay, so this is the example given on the lead court and the value off excess tree. So what I will do, I will. I will separate Evel partition this list into two parts. Okay, So I will have less held less tail and Morehead and Morten's more till so all the values which are less than X welcome in this part. Okay, so this is less than expert, and this is good an expert. OK, so this is more head, basically the head of the linguist, and this is more till basically their tail off the link list and similarly less head and less still. So what will be. Will I draped over the link list. Okay, so we will I treat over this link list. Now what do we will compare the value. So compare one with T So one is less than three. So it will be the part of the left hand side. Okay. And initially, all this will be no initially linked list doesn't exist. So all these Arnold Okay, no one is less than three. So we know this will be the part of the left link list. So it will. One will come here and what we will do so less Head and Lester vote will point towards one initially. Now we will compare for with three. Okay, so four is good than three. So it will be the part off the right hand side. More. Okay, so four will come here, and I will update my Morehead and more till then. Compare three with three. Okay, so it will come in the right hand side. Now I have the option. I can write three here, or I can write three here, since we have to preserve the original order of the linked list. So this is wrong and this is right. Okay, So basically, what we're doing here is we are inserting at tale position. Okay, so we are inserting at tale position now, after inserting, but will do, we will abate our mortal so more tail will come here. Okay, Now compare to so obviously or two will go in the right and left hand side. So who will come here? And I will abrade my left tail. So left till then, compare five. So five will come here and I will obey it. My motel. Okay, now, compared to with three, so too will come here and I will obey it. My left tail. Okay, now then, this link list is over after I dating over the link list. But we have to do so. This too will point towards for Okay, so basically what we have to do. So the next off left Bill, it should point the words The Morehead. Okay. And now what we have to do, we have to return. They heard of the link list, which will be left head. Okay, this will be our head of the new link list. Okay, So this thing we have to do after my left after my less healthy and less still more ahead and more dill. All these four variables already. Okay, Now let us right. Discord and violating the court. They will be like few cases that we will handle. OK, so first of all, I have to create four variables. Okay, so let's head, which is basically no similarly less tail. We need less still, which is no renewed Morehead, which is Mel. We need more tail, which is also Nelly. Okay, so all my four very was already now what we have to do. Well, simply, I'd read over there over dealing list. Okay, So while is not the questionable, okay, Now I have to decide whether this nor will go in the less part or indeed more part. So if the value off a is less than X so it will go in the left part. Now in the left part I have to check first If the left half equals a questionable. So we have to initialize our left head. Okay, so we really initialize our left head and we will also initialize our left so the the boat will be okay. And in the else part, that means they have been living in this list, so I have to insert at detail position so insulted deal. So what they have to do so with some bread dough left till next is basically a And then we will move the left tail. Okay, So left l equals or you can also write left. Bill equals next off. Left it. Okay, so you can write boot now here. What we have do what we have done. So I think you understood this part. So initially. So initially. Left head and left till the boat Where pointing towards Nell. So first of all one welcome here. So when one comes, I have to update both left and left till boat will be abated And Vince the left and left till their normal. Then I will insert at the tail and then I will abate the left tail. Okay, so this is how it is working. And we have to do the same kind off operations with the right part. Also. Okay, so in the else part, what we have to do So I'm coping this part. We have to do some minor changes only. Okay, So if the Morehead if the Morehead is No. So I will update my Morehead and I will abate my motel. Similarly, it should be more till and it should be more till Okay, No, but you have to do so now we have to move ahead. Okay? Way are dating over the link list. We have a bi loop. OK, so we have this My loop. So for moving ahead, we have to write this lane. OK equals next off a Now once this by Luke is ready. Our both left and right wing list. They're ready. OK, so both left and both less and more. They already Okay, so less and the more link list already. Now if we have to, do we have to simply append them? OK, but we cannot simply append them, for example. Let's say if my link list is let's it 1 to 13 and let's see the value off access for. So in this case, my left head will point towards one and this will be the scenario. This will be the left Tail and Morehead and more till there will be no Okay. So in this case, what we have to do, we have to simply return the left held. Okay, We will not do any like upend operation. We will simply return the left head. Okay, now that that case can be, let's say I have 56 and seven. So if this is my input link list and the value off X is for so in this case, my left hand and left till the both will be in l and my Morehead will point towards the Fife. And my more tail will point towards the seven. So in this case, what we have to return. So in this case, our output will be more head. Okay, In this case, this will be our output now. And if both the linked list exist, if both less and more link list exist, then what we have to do? We will do this operation. We were upend. We will do this operation and then we're done. The less head. Okay, so we have to handle some cases. So first case left link list exist, okay. And right link list does not exist, so basically righted. It calls it personal. Now, in this case, we do not have to do any upend. Operation with begins imploded on the lift in. Okay, Now the else if in the else if condition lesser does not exist and right head exist because Sorry, basically this is Morehead. Okay, More about it exist so more head is not questionable. Now, In this case, we can simply return the Morehead now in the inspired, both less and more exist. So in what you have to move, we have to first append. So the next off left tail less tail basically. And this is more head and then we can simply done less had Okay, now this is the complete fool. So if you will run this court, we will get time limit exceeded better. Okay, so let's see. Okay, so this condition is wrong. Basically it should be left head less head is null and more. It is normal now. If you will underscore, we will get time limit exceeded. Okay, So we are getting family which exceeded better now let's see. Let's try to understand because as we discussed our time complexities, basically we're not doing anything else. Our time complexity is linear and our space complexities Owen Then also we are getting the time limit exited better Now we will try to understand why we're getting family with ex every letter. Okay, so So let's try another court for this input. 143 n one. Okay. And the value of excess three. And we're getting daily. Okay, so our linguist is when bulls three en Duin. Okay, so this is our link list and the really off excess. Basically tree. Okay, so what we have to do so initially my left head less head less still there now, Morehead, More tail there also. No. Okay, now we relied rate over this link list. OK, so this is the value off a. We will compare one with three. So obviously this will with a part of the less part, So I will abrade my less head and less did. So let's head and less deal. Okay. So I will update my less head and less still, and then I will move ahead. So this is a no. Okay, now we will compare for with three. So now this time, that's really the part. Off more side. So I celebrate my more. So this is no more head and this is more and they will move ahead. So this is a now compared three with one David three. So obviously this will be the part of the mortal. So more tail arrow Next is basically and then I developed great mortal. So this is more still now compare one. I would three So obviously this will apart off, left inside. So what we will do so left tail Aero Next. So left tail Adul Next It's basically a And then we're updating our left till so left tail will come here. Okay, And then what we are doing. So we are doing if an else part. So in this thing both left and both less and more exist. So whether something like this left tail aero next is basically more head. Okay, so we need something like this. So this is my left tail and what we're doing. Left tail Aero. Next it's more head. So left tail Aero. Next is Morehead. Okay, so this is more head and then the other turning the left less head. Okay, so let's head is one. Then one is pointing towards this one. So when this pointing towards this one, then this one is pointing towards before so oneness pointing towards four. Then we can see for his pointing towards this tree. So for this pointing towards this tree, then three is pointing towards one. So three is pointing the words left dead. So basically, this is the left tail. So trees pointing towards one and one is pointing towards three for this pointing Sorry. One despondent towards four for responding towards three threes, again pointing the words one and so on. Okay, so this will go on. So basically what is happening here is this is a loop. OK, so this is a cycle in our link list. So there's a cycle in our link list now how to avoid the cycle. So for avoiding the cycle, we will simply right? So now, once our lesson more already. But we have to do we have to make their next meal. Okay, so left tail Aero next. This isn't and simply what we have to do so more till Adul next. They're not okay. We have to. Okay, so we're making them. And now our less and more already. Now let's in the court. Okay. So now our God is working, Not it's Emmett. Okay, so we are getting runtime error when our input listers and pretty and the value of X zero. And it is showing there is better at this point. Now let us try to understand what this theater so initially, obviously less said less still there now and obviously Morehead and more till they're also known. Okay, since the list of empathy. So this is our via Lupo. So I will not go inside the white loop. I will reach our dis lane. So I display and what we're doing next off left tail is no okay and basically left and is already known. So basically, what is the meaning off the slain? We're trying to do something like this. No, aero. Next is no. And basically, this will give us a ring time around the segmentation fault Now, to avoid this other what we can do So we cannot write like this. So first we have to check whether the less part exist or not. Okay, so we were right here. So if the less part exist, then first make the next point Colonel, make the next off left Colonel and Denver it on the head. And similarly, we will do with this. Okay? We have to right here. Also okay. Similarly, this part, If the more part exist, make the next night. And similarly, if what exists first make them now, then don't do the operation. Okay? Now let's try to somebody. Okay? So if the list is m pretty, we're getting ready Time mirror, so we can handle one more case here. Okay, So what will be the case we have to handle? Like here? This is the case. So else if if both the linguist exist. So if let's head is not good, sternal and Morehead is not the question. Really? Then only we can do the falling operations now in the else part. So we will come. We will reach this line on live in. Neither the less part exist. Neither the more part exist. Basically, when the list is empathy, So in this case, we can eternal. Okay, now it's summit. Okay, so now our gorgeous 100% correct. OK, so this is the computer. I will share the court with you. Okay. So if you have any doubt in this question, you can ask me. Ok, so the time complexity off our solution is linear and the space complexities will win. Okay. Thank you.