LIVE Solving Leetcode Weekly + Biweekly Contest

[00:00:08]Hi. Hi. Hi. I'm live, right?

[00:00:13]Yes. So, today we have today I will try to solve to try to solve the questions of two contest weekly contest and bi-weekly contest.

[00:00:25]This is bi-weekly. Let me just open both side by side.

[00:00:31]Okay, cool.

[00:00:36]And let me just update this. So, let me just first count how many we have easy problems.

[00:00:47]We have one easy here.

[00:00:50]We have one two easy, four medium, two hard. Cool.

[00:00:56]two easy, four medium, and two hard.

[00:01:06]Okay, so we'll keep track of this thing and trying first lit code easy. We'll start with easy.

[00:01:28]Okay, cool.

[00:01:36]Audible, right? Oh, wait a minute.

[00:01:40]I guess my voice is not louder enough.

[00:01:49]Yeah, I hope this is fine now.

[00:01:55]Let me just scroll here.

[00:01:59]And let me just update this line. Let me just scroll here.

[00:02:06]And let me just update with this line.

[00:02:10]Let me just wait for a few minutes so others can join. Then I can just update with this line.

[00:02:17]Just wait for a few minutes so others can join. Then I can start. Let's update.

[00:02:47]Uh, should I begin? I guess now what's the time? 6:45.

[00:02:54]Yeah, it's fine. Let me uh wait. Let me quickly open the live chat also.

[00:03:09]Okay, now we can start.

[00:03:30]Okay, let me just start quickly.

[00:03:36]So I will take first question from bi-weekly then one question from weekly.

[00:03:41]Likewise will follow one weekly, one bi-weekly, one weekly. So we have two two easy question today, four medium question and two hard question. Okay let's go. So the first is the question from bi is rearrange string to avoid character pair. Okay. So question is you are given a string s and two distinct lowerase English letter x and y. Okay.

[00:04:08]Rearrange the character of s to construct a new string t such that t is the permutation of s. Okay, every occurrence of Y appear before every occurrence of X in T return any value string T. Okay, so the point is they want every occurrence of Y should appear before every occurrence of X. So they want all the Y character. Let's say all the Y character should appear before X.

[00:04:37]Right?

[00:04:41]This is what they want. And we are we doesn't like we don't care anything else other than these two character. The simplest way we'll print all the y character print all the x character and then print the rest of the characters.

[00:04:57]Right? This is the simplest solution.

[00:05:02]So count let's say count Y or what we can do is I don't I want I don't want to make it complicated but you can we can use a custom we can use a custom sort here also but let me first first tactic that I will discuss we'll print all the Y character then all the X character F then remaining characters. Okay, this is how we can do.

[00:05:37]So for that let me just count how many X character are there and how many Y character are there or we can simply do like this. If if you don't want to go in details like just bring answer like this then write three for loop I / S.

[00:06:00]If I = Y then answer plus is equal to I.

[00:06:10]So all the Y we have appended in our answer. Similarly all the x we have appended in our answer. Similarly if y is not i is not equal to y and i is not equal to x and we have then we'll return our answer. This is the simplest solution.

[00:06:33]See then you just submit and we got accepted right there. See what we did is read the question you find out the pattern like the easiest way how we can solve this and this is order of n right if if some see there's the lots of this is a easy problem that you don't need to apply your bra you just just need to think like how you can submit as fast as possible if you are in a contest okay so we have done with the first easy question let me quickly update the question count here this all one and let me just quickly bring back yeah this is using trying second is a question I have one more tactic to solve this question also what we can do is we use comp uh custom comparator uh and in custom comparator we tell the comparator give the priority give the y as the lowest uh highest lowest priority x as I can like for example what I can do is let me just quickly summarize if you want if you don't want to write three for loops so what you can do is assign x to zero assign y to one and assign rest of the character to two then sort then sort the string so what y to zero and x to one and rest to rest character has two then you what you can do is then sort all the character and definitely your So all the zeros will come first, all the one will come after and all the twos will come at the end. So this will solve the what the question ask right all the y character come first all the x character like this. So for that what we can do is sort s dot begin comma s dot end and here you have to write your custom comparator and I forgot the syntax something like this right uh care let's say 2 a care b what the syntax of custom comparator is like this only let me Just quickly compile if B. What the syntax of custom comparator?

[00:09:10]custom compare in C++ just want to know the syntax this is what ah so yeah we are here have so I wrote this is the correct syntax okay this is the correct syntax so what we'll do here is uh we'll give the priority If uh how can we give priority return uh a = x a = y or y uh b = y or a = x or a is equal to b = x x I don't think so this will work but I'm we have to assign like this then it will work but here we need to number what we can see we already have a solution this is the easiest solution but in case if uh if you see we are using every language has some specification right so C++ has a specification in sort like you can use a custom sort and so you don't need to write three for loop. This function itself serves the purpose.

[00:10:44]So the point is what you can is you can modify this like this uh sort what you can use string temp is equal to null and what you can do auto x over like auto i / s. If you find I = Y then tan + = uh zero.

[00:11:12]Else if I is = X then tan + = 1 then what you can do here is else t + is equal to two. Right? Now you can sort this 10 right now. What you can use? Now you can bring your answer. Now you can bring uh build your answer string answer is equal to now for auto and person I over 10. Now what you can do is if I is equal to zero then you can do answer plus is equal to uh y else if I is = 1 then you can do answer plus is equal to x else.

[00:12:14]Uh but here you'll here you up right? We don't know what to means.

[00:12:23]Why did this why I am the only one who do in Java? No crazy answer. No, it's not like this. C++ why everyone choose C++ because C++ is a fast test like it has a good runtime.

[00:12:41]So you don't need to worry about the runtime optimization. You just need to worry about logic building. Rest of the part is done. For example, if you use Python, so sometime the recursion if you write recursion in a Python, it can goes into a 500 millisecond. But the same recussion can bring your runtime to 200 millisecond.

[00:13:03]So for every language has some specification, right? Python is very good for ML and machine learning because it provide lots of library there.

[00:13:12]See I'm not going like I don't want to go in this. The my main concern is instead of this we can write the similar solution using one sort function using comparator where we have to treat each character like this.

[00:13:28]We have to I forgot like how we can assign the charact value to character in a sort. We'll discuss that later. For now we'll go with this only.

[00:13:42]Okay. So I don't want to waste much time in the problem. That's otherwise at the end of stream we can try to code if you want prime second. Okay.

[00:13:59]Okay. The second is the problem. So what is problem is saying even number of night moves. Okay. So it's a chess problem.

[00:14:08]The problem is you are given a two integer array start and end where each array is a form of x that means you have given a coordinate of start and end in a form of x and y 2D coordinate in a 8 + 8 chess board return true if knight can move from start to target in a even number of move otherwise return false.

[00:14:30]So we have to uh say can knight move from start to end in a even number of moves or not. A valid knight move is you know right knight can move like this two and one two straight and one from left or right and it's an easy problem. So brute force of course work right. What you can do is you'll find all the possible way from start to end from start to target and for all the path possible path you'll check which does there any path exist which has a even number of n if that exist you'll return true otherwise false that the brute force but can we do in the simplest way or not let me just think for a while let's say start position is this our end position is And does it always possible key we can reach from task to end? Does no it's not always possible. Right? So firstly we have to check uh does we like do we reach actually reach or not from start to end.

[00:15:42]So there are few pos few test cases. Let me just quickly summarize. So what we have to first look is we are given a start and end right. We have start position and end position.

[00:16:04]Okay. Correct.

[00:16:07]And apart from this first of all there are options like first option is can we reach from start position to end position then we return true otherwise we'll return false. Okay. Now, no till if if we not see here we can say if we if we can't if let me first write this if we can't reach then we'll definitely say we have to return false here right in this case return false. Second case we may reach we may reach end position.

[00:17:04]Then our second constraint is the number of move is even. Then we have to check does does we have reach even number of move or not moves or not. So these are the possible scenarios right and knight can move at a time eight direction.

[00:17:43]I know like the brute force I know like we can apply brute force but the code is quite bigger right for each point you will explore and it is under the time constraint constraint is too low see constraint is too low here so that doesn't matter here but I'm thinking do we can we do a better we can apply a breath for search or bfs or bfs from the start to end position right and we can check how many moves like does there any path exist with the even moves and will immediately return true if that at such a path exists but you know guys right if you guys aware of BFS then you'll know the code is quite bit uh big right and it's an easy problem so there might some kind of trick exist here and we can say we can reach like we don't need to go for travel self does anyone have any idea like do you guys think we are without any travel self it's So mathematically we can convey like we can reach an even number of move or not. It's not possible or it's possible. Do you guys what do you guys think?

[00:18:56]Let me give a few just think for a while. Definitely traversal algorithm serve a purpose right? But it's a easy problem. So I don't want to go with travel in my like I want to think for a while I can implement travel and that can serve a purpose but just put just put a pressure on your brain and think do we actually need travel in this case or not it will be fun just give a challenge to your brain because currently there's one solution in my mind we can do this like Using BFS or BFS we can solve. We can solve but the cons is board is big quite big.

[00:20:01]code is bit longer for easy problem.

[00:20:13]Can we do something better?

[00:20:25]Does anyone have an idea? I'm open for ideas now or otherwise I can implement this BFS or DFS whatever you guys can suggest.

[00:20:37]See it's a keep in your mind it's easy problem right John if you guys watching my stream do like that can bring new viewers also and more viewer more discussion and that's makes an interesting let me let see meanwhile you guys think let me implement a traer right so what I will do here is uh let me let me quickly write a traverser algorithm so we need a cube of text Q.

[00:21:44]Okay. And we push our Q dot push start.

[00:21:53]Okay.

[00:21:55]While Q dot while Q is not empty. See this is the standard format to write uh any BFS.

[00:22:05]This is a I'm writing a BFS here. So I I solve lots of problem a BFS problem. So it's just a pattern like my mind quickly remember the pattern how we solve BFS.

[00:22:18]You guys you all this I just want to check spelling Q or Q.

[00:22:31]It's a Q right? So what we'll do here is uh it's a zero base or one base.

[00:22:42]Ah so in the coordinates are zero base.

[00:22:45]So we don't need to worry about that. So what we can do here is we take the element and for example say start is this. We have a chess board here.

[00:22:59]Okay. We we want to I'm not this is not a perfect chess wood just for a demonstration purpose.

[00:23:13]Let's say this is our end and this is our start. So we have already pushed this point. Now we have to explore this. If horse is here, how many moment like how many different movement can horse can go from this? It can go like this, right? It can go like this.

[00:23:33]It can go horse can go like this and that. So what we'll do here is we push this points in our queue and start exploring from this point. And if horse is here, how many point it can move? It can move like this. It can move like this.

[00:23:54]It can move like this. And it can move like this.

[00:23:59]Wait just a minute.

[00:24:21]Okay, let me just continue. And from here it can move like this. From here it can move like this. So we again so using this point we get more points like like this. So this is a I'm not like I'm not going into depth of how a travis algorithm look like but this is the high level how tra algorithm look like. So see you actually reach here right from this point to this point to actually raise how many movement how many moves you have did to reach from start to end you have performed uh this one and two and two is even so we'll return true for this test case. So likewise we have to do.

[00:25:08]Okay. So this is what we have to fold.

[00:25:11]Fold it out.

[00:25:13]Any confusion here till now? Do you guys have any confusion?

[00:25:24]I hope there's no confusion. Let me just quickly code it out.

[00:25:28]So what we can do is we take the uh element to x for children childs right.

[00:25:36]So auto temp is equal to Q dot run and Q dot pop right now we have to explore it all the this eight directions right so what are the eight directions can horse can move now let me just quickly replace vector of where direction right. So these are the direction like so minus this is in a vertical right and this is this is y direction this is x direction so + -2 + 1 -2 and + 1 right then -2 -1 - 2 - one right so we have covered this two now let's cover this this is uh back right so in uh x direction we are doing oh sorry this is x coordinate this is ycoordinate right so what we have to do here is wait let me just start from beginning so so I'm relatively we have to write here relative order I'm writing so this is in y direction it's -2 + 1 so x is +1 comma -2 okay now for this point it is again -2 in y direction and minus1 in x direction that is -1 -2 okay then let's cover these two point this is uh +2 in the x direction and minus in the y direction that is 2 and minus1 again this is + 2 and + 1 then 2a 1 okay so we have covered this point this point let's cover this two point this is uh + 2 in y direction and + one in x direction I'm confused now wait so this is to confuse using wait this is our see this is a positive this is a positive direction because I'm considering this is the origin uh this color is not good something like red so if I take this is the origin and if I consider this is the positive direction for me this is the positive direction and this is the negative And this is also negative for me right if something cames here it's positive some so this will a good reference for me okay so let's rewrite the points again so what we can do is thanks uh for join what we can do here is uh let's first calculate these two point so for for this if I take this this is the uh this is the origin for me and if I want this point uh if I break it down like this okay so everything is positive here this is positive negative so you can compare this two as the same so now we need a relative point.

[00:29:46]So for let let's cover this two point that is uh uh in the y direction that is 2 - 2 and + 1. So 1 - 2 this point is + 2 -1 and this is 2 comma -1 and let's cover this point that is y + y 2 and x may 1 right so y this is both negative x is 1 y is 2 so both is negative - 1 -2 then if This if you take this point that is uh two in x one in y both are negative right this quadrant in this quadrant both are negative. So x is 2 and y is 1 x is 2 y is 1. Okay. So we have covered this also. Now came to this quadrant.

[00:30:45]This quadrant y is positive x is negative. Whatever the absolute value that doesn't matter. So if you want this point that is x in x we have 2 y we have one okay so x is negative that is minus2 and one and for here is again 2 in absolute value of y is 2 and x is 1 this is x right that is -1a uh 2. So we have covered six point 1 2 3 4 5 6. Now we left with this. Everything is positive here, right? 2 1 that is 21 and we have 2 this is y2 x1 that is 1 comma 2. So we have covered all the eight points where horse can move right. These are the eight points relative eight points where horse can move. Right?

[00:31:49]I hope I didn't make any mistake here otherwise everything is fine. Everything is fine.

[00:31:58]So now let's explore let me just remove this. So we have TM right. So what we can do is for see this is a easy problem and I make it as as complicated as possible. I don't know like this is the intended solution or not. See traveler doesn't required for this easy problem. Whenever you see a easy tag if you thinking something complicated that means you are not in the right direction.

[00:32:30]That is the first indent telling you like you are not in a right direction.

[00:32:39]Uh but for now I I don't know like what's the correct easy solution for easy problem. This is not a correct solution for easy problem.

[00:32:55]What we can do is let me solve this problem later. We'll do brainstorming.

[00:32:59]See this is not an easy solution for if this is definitely not a beginner friendly solution. Right? It require a understanding of a traversal. If I'm able to if if I code it also if I code it out here you'll not able to understand if you have if you unable if you have not solved any tra problem earlier. So for now let's pause this discussion on this question. We're skipping this for for my skipping second easy problem and trying first medium question.

[00:33:49]Okay.

[00:33:59]Now do we have audience or not for we have a today's India's match right? ODS maybe that's why people are not joined the stream but it's fine let's let's move to the first medium problem today's first medium problem.

[00:34:36]So this is the today's first medium problem.

[00:34:48]Let me just start then.

[00:34:51]Maximum value of an alternative sequence.

[00:34:55]So what question is saying you are given a three integer n, s and m.

[00:35:00]A sequence of integer of length and is considered valid if s of zero is s. The sequence is alternating means that either S0, S1, S_UB_2. Okay. Or this. Okay. For every adjacent pair, their absolute difference is less than equal to M. A sequence of length one is considering alternative. Written the maximum possible element that can appear in any valid sequence.

[00:35:34]Ah okay. So we are free to choose any sequence. But the constraint is sequence will start with this s that's the main constraint we have. Now we can build any sequence and another condition is the absolute difference between two aggresscent pair is less than equal to m and we have to tell what's the maximum say what's the maximum definitely say if you take the absolute difference what's the maximum element you can bring up in this sequence that is what they're asking So it's it's easy right?

[00:36:23]So why why why it feel easy? First of all see they told you to bring uh you want to make has maximum has uh see the question asking to find the maximum possible element that can appear in a valid sequence. This is a one of the valid sequence and we want the any one of the element should have go as max as possible right and you and the first thing is the first element is fixed right s is fixed so how if you want to make the second element as max as possible what's the option you have you have s + one you have s+ 2 you till up till s + m right you can't put here s + m + 1 why why we can't put this element because if you take the absolute difference between these two element then you end up with this uh one right one for example say this this I'm trying to explain in a general fashion I did you got my point or not? For the second value because of this difference, we can't put something that is more than s + m. Maximum thing we can put here is s + m.

[00:37:58]Right?

[00:38:02]So this is my flame. If something is uncleared then I can explain further other I can port it out because of this difference you can't put here some this is not allowed right so the maximum value you can put here is s + m right and what's the maximum value you can put here.

[00:38:36]What the maximum value you can put here?

[00:38:38]That is add + m here. That is what you can put here. And what is the maximum value you can put here is add plus m.

[00:38:46]This is my observation. It might be correct. It might not correct. So let's validate this. Does this correct or not?

[00:38:54]So according to this let's say we have we want four elements right and we have to start with three and the maximum difference we can put between two element that is should less than equal to five. So what we can do plus 8 + 5 we can eat. So you can take the difference between those two elements you will definitely get five right and this is allowed.

[00:39:21]Now next element what you can do is put here anything like um wait why seven the maximum element the sequence is 12 oh we need okay okay we need we need to form one more condition see we can't add plus n mn this is not correct we have to make it alternative right so this is like This right? Now we have to make something this. What we can do is just just one element smaller. This can serve this purpose. Right? This can make the sequence alternative also. And now again what you can do is add + five and should take the difference between these two is that is also less than equal to five.

[00:40:09]Right? Because the difference is one.

[00:40:12]Here add five that is 12 and you can say 12 is your answer.

[00:40:18]Okay. And this can so this is also an alternative sequence. Right. This this we have satisfied. This is also we have satisfied because every difference you'll see is always less than equal to five. This condition is also satisfied.

[00:40:35]And we can return this is our answer 12.

[00:40:38]We can achieve right.

[00:40:42]I think I have explained in a hurry. I hope you guys can like you guys have understood correctly.

[00:40:51]If you have any query do let me know.

[00:40:57]What we can do here is let's say long long start is equal to s right.

[00:41:04]So and let me take bull is equal to zero. If bull is zero that means I will add plus m if bool is uh if okay is one.

[00:41:17]So what I'll do is for in i =0 i is less than n i ++ if okay is if not okay if okay is equal to zero that means I will do start plus is equal to m else I will do start minus = 1 and I will return the start yeah uh wait what This we can debug this right.

[00:42:01]So we start with three.

[00:42:05]Wait wait wait three.

[00:42:09]We start with 18. Why 18?

[00:42:15]We start with this eight right.

[00:42:21]uh we have to change okay is equal to not okay and yes because already we have to run this for loop for n minus because this is our start element right we have to process n minus one element rest n minus one element and yes so that's the solution for this questions then submit we have a wrong answer here. Why?

[00:43:07]Where we have wrong answer? Start is equal to 7. N is this half.

[00:43:17]So this is one of the edge cases.

[00:43:20]You can form sequence like this right or you can form sequence like this.

[00:43:33]So you you have to observe. So for this sequence what we did here is for to make to make to satisfy this condition we did a plus m here right and from here to here transition we did minus one here.

[00:43:50]So we want our uh element the start element we started with s that can grow as much as possible at the end right. So we we have to observe like we want to include as many as minimum as minimum as possible minus one in the answer right. So what you can do is instead of plus m you can start with like this also min -1 + m -1 + m also right and whichever gives you a maximum answer written that answer that can be also possible right so I have tried to create this first right I have tried to create this first sequence let me call it answer one start Right. And let me also bring build the second sequence. That is also possible. Right? We can build any of any one of the possible sequence.

[00:44:52]Okay. And here -1 or + m and let me call it as the start two.

[00:45:05]And whichever is the maximum we'll return that max of start one comma start two.

[00:45:12]And let me use this test case also.

[00:45:17]Wait what the Okay.

[00:45:25]Uh okay.

[00:45:27]Yeah.

[00:45:29]Whichever will maximum will result a maximum will return that. Wait what just happened?

[00:45:38]H long long wait still I'm getting 13 H now we have to look into approach see we have three element right that means we can build one one element two element three element like this.

[00:46:10]Okay. Or we can build like this also.

[00:46:17]Okay. And this element is fixed that is seven.

[00:46:23]This is fixed.

[00:46:28]Hi, how are you man?

[00:46:34]Okay.

[00:46:35]So, should I should I summarize the what question is or should I continue?

[00:46:52]Uh, everyone is on same page. Just let me know quickly.

[00:47:05]John.

[00:47:13]Okay. So what we and we want here see we have we have to keep in our mind to fall like we have to satisfy this condition also.

[00:47:25]So here if you want a greater than so what we can do is we can add 14 here right right or we can make six here and now we have to satisfy this then if this becomes 13 we to satisfy this if we oh we have end up at 13 that's correct we want 14 our answer right that is what the expected answer is uh then what I'm missing am I missing anything here know right how 14 is possible in this case we want three element we have to follow the alternative sequence how 14 is possible wait let me just think for a while how 14 is possible here.

[00:49:02]Difference between these two element is seven.

[00:49:06]Difference between these two element is one. Okay.

[00:49:10]Difference between these two element is one. And difference between these two element is seven.

[00:49:16]Yeah. 13 is what I am able to achieve.

[00:49:23]Uh I'm missing anything. I seem like I'm missing anything. What I'm missing then?

[00:49:31]13 is what I'm able to achieve. Wait, wait. What I'm missing?

[00:50:01]Wait a minute. I got I got a call.

[00:50:11]Wait a minute. Let me just quickly reply to this call.

[00:50:28]Okay.

[00:50:35]What I am missing? Does anyone have figured out what I miss here?

[00:50:44]We want say start element is fixed. So seven for this test case seven is the start element. Okay. Now let I have build both the sequence.

[00:50:56]Okay. If I want to make and my goal is to achieve maximum possible element. So I will decrease as small as possible and I will increase as maximum as possible.

[00:51:08]Right? Greedy. This is like really if you think so this is the possibility.

[00:51:14]Okay.

[00:51:23]And 13. Okay.

[00:51:27]Ah 14 is the answer. Right.

[00:51:31]Wait. See this is what the main misconception we have. See we read question correctly but we have not understand the question correctly.

[00:51:42]They're not asking what is the last element you achieve. They're asking what is the maximum element you achieve in your entire sequence that is 14 right?

[00:51:51]So we have to write like we have to uh return 14 not 13. See we have achieved 14 right in our entire sequence.

[00:52:01]F how I missed this. So instead of this let me just quickly long long answer is equal to zero and in answer I will keep track of maximum element so far up I just forgot my time not realizing the saving mistake okay and here also and simply answer and let's submit and we it up again.

[00:52:55]Answer should be s right because first element is this. See these are the silly mistakes I'm showing you here that we have to avoid. I have to avoid my contest and let's it up in a time complex city.

[00:53:37]Wait, why T and S? We can do this mathematically. We don't even need this for loop. If you see a pattern is repeating, right?

[00:53:49]See constraint is too huge. Biggest mistake I'm doing right now is I'm not thinking of an edge case. I'm not thinking in a term of constraint. So these are the primary reasons uh you have to look while you're solving any problem otherwise you will end up in such a silly and idiot mistakes that you saw here right in front of me.

[00:54:13]Say we know right what's the maximum element we can achieve here and if you start with s and you will do here s + m then you'll do minus one then that is s + m -1 then you'll do s + m -1 + m. So what you have noticed uh if this is a even number if this is a even number then you have nx2 m + m nx2 + m. You have noticed here n by2 time we have did + m. If n is even if uh just just observation you just need to apply observation here see if length is even so what you have noticed here we have nx2 + m and nx2 -1 time we did minus one right and if you have a uh this is about uh for example say we have a even length And what if we have a odd length? If we odd length then we have s plus m. This is our second element.

[00:55:45]Wait let's not make it up. See see I got it. What we are trying to do here is let me just summarize here.

[00:55:55]See n can be even and odd. Right? So let's break down n can be even or n can be odd.

[00:56:04]Okay, if n is even and first element is fixed in both the case, right?

[00:56:11]So what is the second element that is s + m. If you try to build this kind of alternative sequence and what is this element that is s + m minus one right now we want this. So again we do s + m -1 + n and it will continue four. So n is and if n is odd then let me add one more here that is now we want this right r. So we'll do minus one again.

[00:56:54]So what what observation we can make here is see this is definitely the largest element among all of this right and if n is odd you will see this is second last element is the largest element right because this is the same here and here this part is same but here we did minus one Right?

[00:57:25]And if you notice this, so this is the largest element and this is the largest element.

[00:57:32]So how many time we did + one here? uh + m that is n /x2 + m we did here n /x2 * n by 2 * and minus one we did here how many times 1 2 1 2 3 4 one time right and let me let me make more generalized if we add more term we'll had a clear idea here we did minus one then we want to make this so we'll do + one + m right we bring this move so now now we have clear idea right say this is the maximum element ment here right so 1 2 3 this is six term so we did three times plus n and how many times n /x2 - one time n by 2 - one time we did minus one so we'll get this maximum element now if we do do some observation if n is odd so what this is So you see this is our maximum element that is we have to and to make it more visually correct let's add few more term we have to make this greater we have to do + one in this term so we did + one and we want to add one more we have to do minus one here right because we want to satisfy this inequality what we'll do here is we'll do minus1 so this is the maximum element right so let's See what we have to add and minus in our S. So how many time we did + one in this you will see 1 2 3 how many element we have 1 2 3 4 5 6 7 1 2 3. So it's a floor division of the + one we did here is also n /2 time right and minus one we did here is 1 and 2 that is same n / 2 minus one 1 2 3 4 5 6 7 by 2 that gives us So 3 that is 3 m right and n /x 2 - 1 that is the 3 - 1 that is 2 that that means we get here n /x 2 - 1 time. So this you will see there is the claim the claim we are making is same for odd and even cases right this is what my observation is see we are making the claim what we have observed is same nx2 10 we do + one and minus1 we do nx2 - 1* 10 so that is my final so if I want to build my answer that is max element what how does it look like s plus n /x2 * I will do * mus how many time how many one I will minus uh plus I will do n / 2 -1 * -1 okay and let me make it uh let me 1 l to just to convert integer into long long wait what is happening and here also one l and we'll return this I hope this should work so it is working for most of the cases And let's debug why it's not working for n is equal to 1.

[01:02:02]See n is equal to 1 then we don't need to do any such thing. S is our direct answer. Right? If n is equal to 1. So why this doesn't doesn't work here.

[01:02:12]Let's just see. So s n= 1 then 1 by 2 this should become zero.

[01:02:25]uh this should become zero right.

[01:02:30]Yeah. So actually we want to take max of max of this comma zero.

[01:02:52]Wait, what?

[01:02:57]Okay, let's not make it long long here because anyway we are doing type cast here, right?

[01:03:08]Sorry. See it is working right. Let me we are getting time limit exit here. Let me just use this. See now we have converted our entire solution into order of one. We are not doing any computation right? We are just using uh arithmetic operation and let me just submit and you see we get accepted. So this is how you should approach in contest. I I shown you how many like I will bring you right from wrong answer to TL to accept.

[01:03:44]We'll see like how observation help us to crack an order of one solution here.

[01:03:50]Right?

[01:03:52]Any confusion or doubt? Do you guys have?

[01:03:59]And let me first quickly meanwhile update the status. Problem solved. Is this solved prime second medium.

[01:04:16]Okay. So we have solved first medium question today.

[01:04:25]Where we are? We have solved this. Now I have to pick first medium question from weekly contest.

[01:04:34]Should I move to the second medium question or do you guys want to ask anything? Please go ahead.

[01:04:46]redo cut the park going.

[01:04:54]Okay, so there's no question. Let me move to the second medium question of today's second medium question.

[01:05:01]So the question is your question. The question name is count dominate dominate okay node in a binary tree. Okay.

[01:05:14]So the question is you are given a root node of a complete binary tree. If you guys don't know complete binary means every every like you don't have one child. You can have a zero or two child.

[01:05:29]A node x is called dominant if the value is equal to the maximum among all the node in a sub tree.

[01:05:39]Wait. What?

[01:05:43]Aa.

[01:05:46]Okay.

[01:05:48]So, see five is not a dominant node here because there is something greater than five in a subsequ.

[01:05:58]8 is a dominant node because you will see there seven and one. There's nothing greater. So let me mark 8 is a dominant node because if you look behind like if you look in it's a children tree you'll see nothing is greater than eight right so eight is a dominant tree three is not because there is four in sub tree three is not every leaf is a dominant node but for mentioned that every leaf is a dominant node so two so 1 2 3 4 5 so for This test specifies the answer.

[01:06:35]Let's look at the second.

[01:06:42]Let calculate here how many dominant node we have. One is not because three is in a subgr two. Oh strictly greater or what?

[01:06:55]Uh x is a dominant if the value is equal to the maximum value among all the nodes.

[01:07:04]rooted at x. Okay. So what is the maximum value for this two? Two is the maximum value.

[01:07:12]So there is nothing greater than two in it subra. So we can consider this is one. Every leaf node is a dominant node.

[01:07:19]So four is our answer.

[01:07:21]So that's what we have to calculate here. Right?

[01:07:27]So what we'll do here is if you want to know this node is a dominant node or not. So what we can do what is the maximum value from this sub tree. What is the maximum value from this sub tree?

[01:07:38]Let's say this is m_sub_1. Let's say this is m_sub_2. So this one should greater than equal to m_sub_1 greater than equal to this both condition is satisfied. Then we can say the current node is a dominant node.

[01:07:54]Right?

[01:07:56]If we have a tree like this, there is a sub tree here. If we have a tree, so we calculate it from what is the maximum value. Let's say that is m_sub_1. Let's say this is m_sub_2. Then we can say uh this if this condition satisfied for both m_sub_1 and m_sub_2 then this node is a dominant node. So this is what the equation tell us the current root current node is a dominant node or not. So this is this is what we have to calculate. Okay.

[01:08:33]And every leaf node is a dominant node.

[01:08:38]So what we can do here is let let me just quickly code it out then if it is cleared.

[01:08:46]So what we can do here is I will calculate answer. Okay. Now for each node uh let's let me call return solve. Let me pass root.

[01:09:10]Okay.

[01:09:13]Yes.

[01:09:16]and hint solve.

[01:09:20]I have a root.

[01:09:24]Okay.

[01:09:28]So, first of all, I have to check if uh root is a leaf node or not. If it is a leaf node, we'll return + one.

[01:09:38]If wait if it is a lift node we have to return every lift node we have to count and what is the maximum value right so current so from left if left node is present if root left node is present Max M_sub_1 is equal to Z. Then M1 is equal to how we can for this is a long time back.

[01:10:26]I have coded some T recursion solution.

[01:10:30]You want a maximum value, right?

[01:10:44]Okay. So, let me call it as a G maximum. What if it is a root node? uh list nodes.

[01:11:00]Okay.

[01:11:03]If root left is null if and end that means it's a if node right?

[01:11:20]If root left is not present, root right is not present, that means it is a if node, then we have to return the value of root and let me call it get max.

[01:11:39]Okay. And we have to return root values.

[01:11:47]And if max let me call it as max is equal to maximum of max comma get maximum of left root and if right child is present and then we can say get maximum from left right.

[01:12:23]Okay.

[01:12:25]Now we have to return what we have to return that is see let's calculate the separately in answer. Okay. So this function will return what how many dominate nodes other than leaf node.

[01:12:57]So what is the condition that is current root value is greater than equal to max plus.

[01:13:14]If this is uh if this value is true, it will add + one to our answer. Then calculate for root left and calculate for root right.

[01:13:33]Okay. So according to this question, we should have one because we have not added this values, right?

[01:13:42]So let me see are we getting one or not root value.

[01:13:52]Okay.

[01:14:01]And we can do like this also. Wait, if you want to include this also then we can add like if both are null null right and this is also null that means this is a root node but this will change the definition of this function right this function return the maximum value not tell okay okay so we'll calculate separately search things.

[01:14:50]Okay.

[01:14:54]It is not visible, right? Wait.

[01:14:59]I think I have to increase the font size.

[01:15:04]How can I increase my font size?

[01:15:11]It is visible.

[01:15:15]WordPress, can you confirm it is visible now?

[01:15:27]I think it should be visible now.

[01:15:34]Okay, thanks. Thanks man.

[01:15:40]I'm expecting one here because till now I haven't calculated the lift nodes. I have just calculated the dominant element in uh other uh other than lift nodes.

[01:15:56]Okay.

[01:15:58]And we have fogged up.

[01:16:04]We should return one here.

[01:16:07]Ah, got it. Got it.

[01:16:12]Okay. Okay. So, problem is this is one but this written a maximum element right here. It written eight instead of this.

[01:16:28]It should return one or zero then it can serve a purpose. If it is not null, this is also not null.

[01:16:43]Wait, we have to change the definition of this function. This function should return one if the root node is a dominant node or not.

[01:16:55]Right.

[01:16:57]Yeah. So what we can do is we can call this function as a solve function.

[01:17:02]Bro not let me tell you how many question I have solved. Around thousand I have solved.

[01:17:19]Uh wait how many question I have solved?

[01:17:27]I have solved around 932 problems though this my name wait let me just change the definition of this function uh let's be called get dominant get dominant Okay, if I pass root and let me call let me create one more function get max.

[01:18:12]If I pass root the purpose of this function is to get what is the maximum element from a sub right sub tree and the left sub tree. Okay. And this function tells me if my current current is wait like this and left max left max that is get max. I will call get max and I will pass root left right max.

[01:18:51]Uh now this is quite cleaner fold right right and this if my left max if my root value is greater than left max and and my root value is is also greater than right max then this is a dominant the current root is a dominant Right.

[01:19:26]The point is we want to count for each. We need to put a iteration.

[01:19:45]See we need to solve a recursively. We have to go depth.

[01:19:54]For example, if I take Manu, hi Manu. Count left right count one left. max down to right max. Yeah, this is what see the easiest way is to solve for each element you should have what is the maximum from its sub tree right sub tree and left sub tree right and this is a dominant element so it should oh it should return how many dominant element we have find out from this with the count of dominant element from a sub tree count of maximum element this many information we should have at each point. Then we can easily solve this problem. Right?

[01:21:03]Yes. Yes. Yes.

[01:21:11]But the point is how we can implement this easily.

[01:21:16]I want to implement this anyhow. Wait, this is the I completely forgot the trees like tree is the easiest topic.

[01:21:24]See it just required it first go it looks too complicated.

[01:21:32]For me also it's look too complicated right but I solve lots of tree problems that's why I can tell you my experience that tree problems are quite easier if you like if you should not get confused it's just this many function like you have to break down your code into a smaller function and each function should have a specific work to do then it's quite easier right now I'm struggling because I left the practice of for three problems so see for each uh if you look Okay, for the each node if you have information about how many what are the information what is the maximum element from its sub tree and how many dominant element let's say the count if you have this information for this node you can use that information right and at the root you will have the total number of dominant element right so let's just code it out get do get dominant element Okay, we'll pass the root and right now we have zero dominant element.

[01:22:44]Okay.

[01:22:49]And we have to solve it recursively.

[01:22:57]And here we have to do plus Uh or do we require discount? No. Right.

[01:23:12]Wait, wait, wait. I guess I have not added root left plus Right. Okay. And what is the purpose of this function?

[01:23:37]To get the maximum element. Right.

[01:23:49]Yes.

[01:23:51]And how we can solve it? Let's say current max is zero.

[01:23:55]If we have If road left is null and end root write is also null.

[01:24:25]Break down root value.

[01:24:30]This is for lift nodes.

[01:24:33]Right.

[01:24:35]Else if root left we have then max is equal to maximum of max comma root left.

[01:24:55]Similarly for right nice right and wait I hope I didn't make any still we haven't counted the lip nodes Wait.

[01:25:26]Why still we have an error here?

[01:25:31]If this is a root node and return root value, right?

[01:25:54]Wait, what?

[01:25:57]Member access within null pointer. If it is a null, then I'm not accessing right.

[01:26:05]Wait, something is popped up here.

[01:26:09]Runtime error. Why runtime error?

[01:26:14]This is a node.

[01:26:24]Do we miss anything? Did anyone find why it is the left is null? Right is null.

[01:26:35]Then we return both values.

[01:26:48]Do you guys anyone saw what's the cause here? Why I'm getting runtime error?

[01:26:58]It's stating key I am accessing the null pointer but how I'm not accessing the null pointer right member accessing within a null pointer of type t node.

[01:27:17]Okay.

[01:27:29]If root is null, return zero.

[01:27:40]Still wait where where where uh here also we have to put if root is null these are the edge cases return zero and we have a answer here we have answer right I didn't see any clause pause here it will pass. What do you I'm feeling confident. I don't know it can fail also, right? But did you guys notice like how we have break down the problem into smaller function and we have like at least we get fast uh sample test case right and I'm feeling confident like for each I'm calling uh number of node can be 10 ^ 9 it may work we end up in a time limit exit here possibly No number of node in a tree can be 10 to the^ 5 and we run a recursive function here right yes so we we need to apply DP here it will give a time limit exit if I'm not wrong because for each node we are recalculating right we are not using the computation for example say yes we are not for example say we have call for we made a call for this function also we made a call for this this node also so we'll end up in a time limit exit that is what I'm suspecting let's just give submit and we'll see no wrong answer we are not expecting right time limit Something is wrong. Then logically something is wrong because we're getting wrong answer.

[01:29:50]Why we are getting wrong answer here?

[01:29:53]Uh let's just count uh three this and this. Three is our answer. What we are getting?

[01:30:06]What I'm getting?

[01:30:12]Four by Y.

[01:30:26]Let's debug if if you I don't know like why it is failing. So let just debug this is my root value and these are my left maximum right maximum.

[01:30:50]This is off. This is off.

[01:30:56]Uh, this is my left max.

[01:31:01]And this is my right max.

[01:31:07]And we'll see.

[01:31:14]So see uh where is that tree for four? It should be 15 and four, right?

[01:31:28]But I'm getting four and three and four.

[01:31:31]This is not true.

[01:31:34]I let me first draw this tree for a reference. We have a four. We have a 15 here.

[01:31:43]We have a four here.

[01:31:45]We have a three here.

[01:31:50]But four we are getting three and four.

[01:31:53]Three and four.

[01:31:56]That's not true.

[01:32:03]Uh here we have to return max of max comma root values. Right.

[01:32:19]Yes. Now you'll see for four we are getting 15 and four. From the left we are getting 15 as the maximum value.

[01:32:27]From the right we are getting four. So then four become four will be not our uh dominant.

[01:32:35]Right? So let me just submit. Now it should give time limit exit because if I'm not wrong for we are making uh this we're not reusing I have not like if you saw here we we are not not storing the computed value if we want to use in the future calls so DP is the potential optimization should come here if we get time limit exit Oh, it got accepted.

[01:33:14]I don't know.

[01:33:16]I don't know. I think it should give time limit exit but it got accepted.

[01:33:23]Oh, we have a we that this is the optimal solution. Wait if I want to calculate the time complexity nodes for each node I'm doing a function call it and should give time exit right uh but anyway I'm not sure what the time complexity of We can we can we can use this, right?

[01:34:09]Wait a minute.

[01:34:14]The time complexity is n² but I got accepted right that's why I'm also feeling it's n² time complexity use my logic and return count one plus count and plus one if root this is a working solution I I completely understand order of n this uh what's the time complexity of this solution this is also order of n If it is not order of end. Yeah.

[01:35:15]What's your suggestion?

[01:35:18]Written count one plus count two and plus one. What is count one and count two?

[01:35:38]Oh, this that is what I did here, right?

[01:35:42]Say if root is greater than and this is count one and this is count two. This is what you you are telling right man.

[01:35:52]That is what I did here. Oh, that's why it is order of n. Okay. Yeah. Yeah. Got it. Got it.

[01:35:59]So we're calculating the child do what is the num max what is the count of dominant element we're getting from left child what is the dominant uh count from the right child that is this this function will return that count and we are checking if the root is the dominant element does not ah I see I see yeah this is the optimal solution got it got Everyone is on the same page, right?

[01:36:37]Do like the string, guys. Do like the string.

[01:36:46]This is what I did, right?

[01:37:03]count left max.

[01:37:06]Count to right max.

[01:37:16]Solve root left.

[01:37:18]Solve for root right.

[01:37:27]Wait, what I'm thinking is to s the way you are suggesting that's that's what I did here. Actually, this is solve for me. See, wait. Let me give you a terminology. The sol you're telling me this is the solve function.

[01:37:46]I'm I'm calling sol as a get max, right?

[01:37:49]The sole is on left, so is on right. And this return two value from one function.

[01:38:08]Return two values from one function.

[01:38:10]Yeah, I got your point.

[01:38:15]I just want to know the time complexity of my code. H it's order of n square I guess let me just confirm quickly with that beauty it's order of n² right if it is order of n uh siraj kumar my lead code ID is Direction direction underscore direction underscore what is the it should be order k and see it's order n square right but k2 it's a balance Ah, got it. See why this works here?

[01:39:23]Because it's it's never a skewed binary, right? It's a balanced binary. That's why we are not going in a skewed format.

[01:39:33]That's why our time complexity reduce from login. But in see see this is what I'm telling because this is the balanced binary tree that's why the maximum height of this tree is log n so even though yes and maximum you can go 10 to the^ 5 right maximum if it is skewed let's make it a skewed let's say this if tree is like This it's uh this is not possible.

[01:40:11]This is not a balanced binary tree.

[01:40:13]Right?

[01:40:15]This is not a balanced binary. If if balance binary should like this only this is also balanced binary tree. This is also so you'll never have a case like this.

[01:40:28]If if the question does not mention this is a balanced binary tree complete binary tree then this solution won't work here the solution I have implemented is only work if we have a complete binary tree got my point my lo the logic is login because of this constraint otherwise if this is not given in the question then some then taster can the problem center can build a sample test case like this and my logic will failure got my point hello I'm currently in a fourth year and my fourth year will start just now and I am from tired to college but from electronic branch and for DSA part my basis are clear but not graph DP in a full is full left and I need a good package please guide me in which direction to work to achieve my see if you if you target if someone targeting on campus and your college is good enough to bring the companies that definitely recommended firstly clear your CGPA barrier shortlisting barrier that is minimum 7.5 or 8 in some college in my college it's eight if you're 8 plus so your CGPA barrier is reduced and you definitely sit for all the placement right so first part is done CGPA you cleared the CDP short listing it's mandatory and it's always happened in college placement the second thing now second thing is for the on campus placement the mostly questions revolves around four subject that is uh oops concept C++ concept DBMS concept OS concept okay that is also clear because uh that's your curriculum right then the third part is the DSA so if you're targeting here on campus and your there's a good enough placement is going uh like your college is giving you like giving you an opportunity to sit for a good company.

[01:42:38]So to prepare a sty seat that's more than enough. If you completed the driver shift then only you can look for a different uh just follow sheet require seat uh seat has a topic wise concept and it will cover all the aspect easy medium and hard and I recommend that recommend to go with a driver sheet if you have complete focus on campus a good placement because I did that most of the my friend did that and we had we have achieved a good result right one who has an interesting example let's consider three node tree so first go left and then in a single node so return one that's it the value and then go right the same and after that check the root yeah I got your point this is the optimization but I'm not still not convey time complexity if I implement like this also Don't you think so?

[01:43:46]We'll get a same time complexity if I implement uh like this.

[01:43:56]Sorry guys. Am I answer uh I answered your question right?

[01:44:03]Yes. CGPA is CGP is clear. My college has sample and I I did try A to Z and I did around 250 from it and I also wanted to try for off campus. So what things are required for off campus at DX level?

[01:44:22]Uh if you answer this if you're targeting off campus then you need to start doing completed programming and because if you have good command on computer programming see you have mentioned you're not like confident enough for DP and graph right so complete the styus DP and graph section I followed the I I've solved all the DP DP questions for the sty and I'm pretty much confident like I'm able to think at least if I'm not able to solve question I'm able to understand the DP solution and the graph I followed the driver sheet for graph and DP and that's helped me a lot and for the off campus you you have to build your confidence so you have to start giving a live contest anything you can add coder beginner contest every Saturday we have at 5:30 uh p.m. Then attend code forces contest at least due three due three due two then attend code chef contest that's happened on Wednesday the live contest builds your confident so that's help in off campus like off campus is you have a huge competition right and the contest itself now this you will competing with a th00and 2,000 candidate uh 20,000 candidates right no it's only order of n square Okay.

[01:45:45]Okay. Let me implement your solution also for the time being. Let me just update trying second trying optimization.

[01:46:08]Okay.

[01:46:09]So, so what you are suggesting manu uh can you please help me?

[01:46:18]Uh so the point is let me just quickly bring no no will hide my camera will hide right it's fine don't call me sir you can call me vin okay okay so the optimization is can we bring this to an order of n so for that what we have to do is wait what you are suggesting me uh let let just let just make an observation how how we can actually so I made a call for this function right then I'm solving for this and I'm solving for this okay then I made a call for this function right see this is a order of n solution right why why I'm confused this This is order of n solution, right?

[01:47:20]No, this is n square. Ah, got it. Got it. So, we have to get rid of this function.

[01:47:29]How we can get rid of this function is we have to return count from this function. We have to return count and the maximum value.

[01:47:41]Yes. True. True. This is n square solution. Yeah. Because this is order of n because we are visiting each node uh each node in the tree and for each node we are again making a order of n function call here. This will run in order of n order of n. This will also run in order of n. So eventually we end up in n square solution. So this will o of n² right. So we have to get rid of this thing. And how we can get rid of this thing?

[01:48:18]Yeah. So we have to return maximum we have seen so far.

[01:48:29]And for that we have to think I have to think because I'm confused now. How can I return maximum? So maximum what we can do here is ah okay. So what we can do here is left max right max and we have to pass two value here left max is zero right max is zero okay let's say I will not call this function anymore and we are passing this left Max.

[01:49:14]Yes. Yes, I got your point. Yes.

[01:49:18]We need to pass two function uh left max and right max. Right.

[01:49:25]So what I'm trying to do is I'm I'm making my function optimization. So whatever things like for example I'm calling this function right but instead of calling I'll keep track of this function uh track of this value. Okay.

[01:49:38]left max, right max. Okay. So everything else I don't need to change here. So what I have to do here is or we don't or we don't or we just return the count and this and here we have auto answer comma max and this will return a vector.

[01:50:15]vector of int. Okay.

[01:50:18]And we'll return answer of zero here.

[01:50:21]Okay. Cool. So now what we'll do here is uh we have auto we'll fall left on left. Uh let's call it left. We will call left here. And here we'll just maintain a max.

[01:50:42]Okay.

[01:50:45]And we'll call for root left and max.

[01:50:55]Then we call auto right.

[01:51:01]We call on right.

[01:51:10]with this max. Okay. And what we return is what we'll return here. Okay.

[01:51:22]We'll return this thing if root value is greater than max.

[01:51:31]Hi bro, how are you?

[01:51:34]Hurry. I call it hurry.

[01:51:38]Okay. Plus count one, count two. What is count one? That is left of zero. Uh this is vector, right? So what I'm storing in this vector is count and maximum value plus right how many dominant element I get from left sub tree. How many dominant element I get from right sub tree. Okay.

[01:52:05]And anything else we have to do here? Wait, but we are not updating the max anywhere, right?

[01:52:22]Uh how we can update the max? We have Something is up here. Wait, wait, wait.

[01:52:38]If it is a root node, if root is null, then we return zero, comma, max.

[01:52:46]I'm not updating the maximum value anywhere. Right? I'm calculating here this I'm calculating here on the right sub, left sub3r.

[01:52:57]I'm passing the max.

[01:53:10]Wait, how can we handle the max here?

[01:53:20]How we can handle the max here?

[01:53:29]And if it is a root node, yeah, we have to write this logic here. If it is a root node, okay, okay, wait, wait, I got it. If it is a root node, then we have to return 1 comma value of that root node. Okay, that will be my max value. Okay.

[01:53:55]Yeah, this is fine. If it is a root node, see if it is a root node. So, what are the information we passing to a parent is uh one dominant element me itself. I am a root node. That's why one dominant element and the maximum value from my sub tree and for this four what we are doing? I'm returning 1, four, right? This is what this function do here.

[01:54:25]That's it. Right. This how we can update the max and we have to return this is our count and we have to return the maximum value that is max among all three.

[01:54:50]root value then left of one then right of one.

[01:54:58]Yeah. Now we can say we are handling the maximum value also.

[01:55:04]Okay.

[01:55:07]Answer is equal to auto.

[01:55:15]Wait, we have solved something but this is not order of n square. We will calculate what is the time complexity.

[01:55:24]Wait, let me remove this first stuff.

[01:55:27]And we are not using this function anymore. Okay, so where is the mistake now? See, I pass root and zero. Okay, I call for five. I made a call for five.

[01:55:43]Okay. And now I'm solving for this part and this part separately here.

[01:55:49]Max is zero till max. See let let me just quickly write down. So I made a call till now.

[01:55:56]This is in a hanging state. Right? We are here. I made a call for this also.

[01:56:01]This is also three. The call for three is in the hanging phase. Now we are at this. Right? So root is not null.

[01:56:12]root is not null right but root left is null it's root left is null and root right is null right so this is null so it will return 1a 2 so we have written here one this is 1 comma 2 we have written okay cool so now we come uh we came here.

[01:56:41]Okay. So here we have 1 comma 2 in this left.

[01:56:47]So now we made a call on the right. Then yeah from here also we get 1a 4.

[01:56:56]Right?

[01:56:59]1a 4. Now we are at here. So three is not okay. So three is not greater than max.

[01:57:09]Ah I see I see. So we have to calculate now max is equal to current max. Let me call it a current max.

[01:57:22]Max is equal to max comma left one comma right one Right.

[01:57:42]Cool.

[01:57:57]Uh something this is what we have to do something like this. Yeah. And we have right so what's the error here is safe.

[01:58:05]I told you three is not maximum because we have to compare this three with its left max sub tree maximum and the right sub tree maximum right the current maximum is among the this two even though if I don't use this max yeah it still work we just need to compare with these two values and right and for it subsequence call for this call we need to pass the maximum this three value 2 3 and four and that is what we pass here right so instead of this current max and yes that's how we can converted this into order of one solution uh n solution right because you'll see we have visited all the nodes once and we get rid of this function so I hope this is the order of n solution and it will pass all the test cases.

[01:59:08]Let me submit.

[01:59:16]And we have accepted solution guys. And we did it.

[01:59:22]Done. Optimization.

[01:59:25]This is the happy moment for me.

[01:59:30]Did optimization on second problem also solved solved and did optimization guys? I don't know. I'm feeling happy right now.

[01:59:53]Can we make it a like I want to align this. I want to align. Do you guys know how can I I want to align this from right side like I should it should grow this side I don't like this white space here transform stretch to screen center no no alignment where is alignment and one more thing I have to update we have solved two medium question we have solved one easy problem and I want to know guys do you As anyone do you know what's the easiest way to solve this easy problem?

[02:00:36]This easy problem.

[02:00:39]Does anyone the chat knows how we can solve this easy problem? Because in my mind I'm thinking of some kind of traversal algorithm BFS or DFS to solve this problem. But this is a easy problem. I don't want to involve any such traversal problem.

[02:00:55]Does anyone know how we can solve this function? uh question without using our travel cell function any travel cell algorithm.

[02:01:05]I'm open to suggestion guys.

[02:01:08]Do like the stream. Do subscribe if you're new to my channel and we have interesting live streams in the future also.

[02:01:17]We'll learn, we'll solve, we'll grow together. That's what my goal is.

[02:01:31]Hello.

[02:01:38]This will be on order of one solution.

[02:01:40]Let me just confirm.

[02:01:48]We are not using this function, right?

[02:01:49]So let's just remove this say see order of right we are making we make a two false that's it there is no nesting call so there is No state. So using this function we have this is just a traversal in order I can in order or pre-order post order left right and root it's a traversal we're traversing we're visiting every node once that's it there is no nested calls I have a suggestion first of all thanks Till G.

[02:02:51]It's an interesting name. We can calculate the move by seeing the color.

[02:02:57]Okay.

[02:02:59]Something interesting.

[02:03:07]Okay.

[02:03:11]Or if I'm standing at uh oh my god it's a square of 2 + 2 right what's your we can calculate the move by seeing the color what that means we can calculate the move by seeing the color that in bro sorry I didn't get your hint could I look the hint here well the chess would like a standard chess using a parity okay every night change the color of the current cell therefore okay Night must be in a cell of same color.

[02:04:12]Okay.

[02:04:15]Third hint. Since every cell is reachable from every other cell, is it? Oh, this is a good property. I don't know about this property. That's why it's very tough for me. See, this is very good.

[02:04:31]Yes, got it, bro. Got it. I got your point now. But this is the interesting property. I didn't I didn't know about this property of chessboard coloring.

[02:04:42]It's visible, right? Yeah, it's visible.

[02:04:45]So this is one of the interesting property and I don't know about see it's saying that you since every cell is reachable from every other cell on H+ B return whether that's it this will solve a problem if you know the property of this I don't know that's why it seems to very tough for me so I will skip this question I will not sol it's easy for those who play chess huh Wait, I'm noob in chess.

[02:05:20]Black chess liy chess.

[02:05:23]Anyone want to play chess with me?

[02:05:35]Let's see.

[02:05:38]I'm good or bad. We'll see.

[02:05:41]Should should I know? I didn't know about that property, bro. Let me play five minute chess.

[02:06:03]Oh, my camera is hiding, right?

[02:06:06]Let me change the camera for a while.

[02:06:14]Okay.

[02:06:25]Should I move the knight here?

[02:06:28]Guys, do help me. I'm not good at chess.

[02:06:34]Please help me, guys. I don't know.

[02:06:44]Wait first. No, my screen is in danger.

[02:06:52]Ah, pass, bro. pass. My screen is in danger now.

[02:07:09]My ass.

[02:07:21]What do you guys think? I will win or lose.

[02:07:36]the car.

[02:07:39]Oh my god. Oh my god.

[02:07:45]May I suck you home?

[02:07:50]My eyes you did I bring my horse into the game?

[02:08:02]Oh my god.

[02:08:08]My eyes.

[02:08:16]Okay. So the point is I can check Why I feel I don't know guys I will win or lose that's What we have to do?

[02:09:00]Make the opponents think like you are a proof.

[02:09:07]And I won.

[02:09:10]Anyone from the chat? Anyone from the chat want to play with me a chess match?

[02:09:16]We can we can go for it.

[02:09:25]Why? Why this cola cola? I should try the next question. Otherwise, if there is no one interested to play chess seem like my audience is more motivated than me.

[02:09:44]My eyes are Let me try the third easy problem then.

[02:09:55]Third easy problem. It's a fivepointer, I guess.

[02:10:01]This is a fivepointer.

[02:10:03]And this is also five pointer. Which one I should try? Bi-weekly or weekly? Both are five pointer.

[02:10:12]We can play. Do you want to play Goro? Let's play one chess match then I can continue with the problem solving.

[02:10:22]What's your What's your ID, bro? Tell me your ID.

[02:10:32]Tell me your ID.

[02:10:37]Go 5G.

[02:10:44]This is right.

[02:10:49]Let me add you.

[02:10:51]I have sent you a friend request. Just confirm.

[02:10:56]Just let me know.

[02:10:59]May I suck your host?

[02:11:02]May I? Yes. Okay. So, let me just five minute. Okay. We'll play bit blitz.

[02:11:15]Send challenge. saying okay let's start guys let's start my I feel bro is pro player I'm My ass bro is genuinely a good player. I guess I start simplest way.

[02:12:16]The simplest way is to get rid of the get rid of the you guys know, right? Get rid of the material.

[02:12:32]Okay. So, there's something something is going on and we can do like this.

[02:12:39]Why I'm feeling like a noob player here?

[02:12:42]I don't know.

[02:12:47]I think I'm a noob player now.

[02:12:53]What should I do now?

[02:12:58]I'm thinking of something but that will not help me.

[02:13:05]May you may Wow.

[02:13:22]Wow. Wow.

[02:13:27]That's good move, by the way. That's actually a good move.

[02:13:33]Let's materialize.

[02:13:39]Uh, what we can do is should I trade?

[02:13:49]Ah, I buff it up. I should trade instead of this.

[02:14:03]Bro knows he won this match, right?

[02:14:13]What we can do here is this. Ah, Why? Bruno knows he won the match.

[02:14:35]I have nothing to worry about, you know, like understand my assignment.

[02:14:54]Bro has understanded my assignment.

[02:14:58]What should I do now?

[02:15:11]Bro, I have respect for you. I'm noob. I accepted. I'm accepting. I'm noob.

[02:15:25]Just take this.

[02:15:28]Just take this.

[02:15:33]What I can do here is something like this.

[02:15:41]and grow started.

[02:15:44]I see it.

[02:16:02]My eyes are here. I can surrender easily.

[02:16:11]My ass.

[02:16:19]Why? Why you are doing this to me?

[02:16:46]What should I do now? I don't have an option.

[02:17:01]Let's materialize.

[02:17:04]Let's materialize the thing.

[02:17:11]Wait, wait, wait. We can do something, right? We can do something. Yeah. Wait, wait, wait, wait. I got it. I got my point.

[02:17:20]I think I can materialize.

[02:17:24]I it up.

[02:17:27]Let's go all in.

[02:17:34]Thanks for watching.

[02:18:06]I am first step likes me.

[02:18:12]What should I do now?

[02:18:16]It can take my screen but no not now.

[02:18:25]Bro, you should make my checkmate.

[02:18:46]And I am low on time, bro.

[02:18:53]Respect, pro player.

[02:18:57]Huge respect for you, bro.

[02:19:00]Now, let's solve a problem.

[02:19:10]of man. You earn my respect, bro. You earn my respect. I don't want to get up on time.

[02:19:30]I did some blunders.

[02:19:32]No, it's not a nice match. You are a very genuine player. I'm a noob playing a chess after a long time. Long long long time guys just let me know. We'll solve one problem.

[02:19:57]Which problem I should try?

[02:20:02]bi-weekly or weekly.

[02:20:05]It's a fivepointer. Anyway, thanks Gorov.

[02:20:17]By the way, it's a good match after long. I played a match. Street. It's a street match for me.

[02:20:33]I have 200 right that's that's define the level you're pro than me guys just let me know which we'll start solving say we have h we have two fivepointer I'm not sure I'm able to solve or not but we can at least give a try Let me solve this. There's no there's nothing much I can wait more.

[02:21:16]The problem name is minimum adjacent swept to partition array. Okay.

[02:21:25]Minimum adjacent swept to partition array.

[02:21:32]You are given an integer array nouns.

[02:21:40]You are given an integer error nums and two integer a and b such that a is less than b. Okay.

[02:21:48]An array is for good if it can be split into three continuous part in this order such that every element is first part less than a. Every element in second part is in a range of a and b.

[02:22:05]Every element in third part is greater than b.

[02:22:13]Any and any of the three part may be empty. Okay. may be empty in one adjacent swap. You may swap two neighbors element. Okay. Return the minimum number of adjacent swap required to make a nums good. Since the answer may be very large, return it with mod below.

[02:22:39]Okay. So problem state is quite simple.

[02:22:43]It's like we have a an element We have to split into three parts.

[02:23:06]Everything less than equal to A.

[02:23:11]Here everything is greater than equal to B. Here everything is between A and B.

[02:23:20]I'm thinking we have a similar question from code forces one of the code forces font test the question is number of one is greater than equal to number of twos and three here number of one and two is greater than three and here anything What we can do here is uh what we can do here and we want a minimum number of steps to perform this. And let me see the constraint.

[02:24:06]And constraint is pretty good.

[02:24:10]We need some kind of optimization algorithm. We are saying constraint is not low here. Constraint is a pretty high five.

[02:24:20]So what we can do is can we do binary search and answer see we have a option here it can be a DP problem also I'm not Sure. But my suspect my unsuspecting it can be a DP problem also. It can be because every point we have a choice.

[02:25:00]Can we make a split here or not?

[02:25:04]Can we make a split here or not?

[02:25:18]Right.

[02:25:25]It is a DP problem. Yeah, it is a DP problem. Then see at every point we have a choice. Can you make a split here or not? Can we make a split here or not?

[02:25:36]Likewise, what we can do is we can stop the stream here and we can I can do another stream because it's my dinner time. I will not get food after my PG. I will not get food, right? I have to stop this link here and we'll It's a pretty good discussion to it's not bad. It's try too easy to medium right guys make it 290 subscriber currently I have 289 can anyone can subscribe and make it 290 if you have not subscribed yet I want to see the transition from 289 to 290 can anyone subscribe It will be good to watch 290.

[02:26:44]Can anyone make it 290? Just subscribe.

[02:26:47]Please subscribe. It will return into 290. I want to see 290.

[02:26:59]uh it will it will not it's not that easy understand so today we have solved two easy problem two medium problem so four problem right it's done oh 290 it's 290 right it will take time to update or what ah My god, 290 finally.

[02:27:28]Thanks guys. Thank you so much for joining the stream. We will we'll have a stream most probably tomorrow. If not tomorrow, yeah, we'll have a stream tomorrow also. We'll try to solve and we we have a good inter interactive audience today also. It's a fun.

[02:27:53]I am final your Mtech student.

[02:28:01]I'm finally your Mtech master student.

[02:28:02]By the way, do you guys have any anything to discuss or I can end the stream then?

[02:28:24]Just follow me then. That's fine.

[02:28:34]Oh, that's first. Yeah. Okay, that's full.

[02:28:44]Okay. Nice. Nice. Nice.

[02:28:48]Nice to see you guys in my next stream.

[02:28:51]Do join the stream. We have a interesting problem solution. Oh, you're from Gorakur. Mer Gorakur. Okay. Okay.

[02:29:00]Interesting guys. We have audience from all the corners of the India.

[02:29:06]We'll go international guys. One day.

[02:29:13]So that's all guys for today.

[02:29:16]Thank you for joining. Have a good day.

[02:29:18]Bye-bye. See you in my next stream.