Leetcode Biweekly Contest 183 | Video Solutions - A to D | by Vikas| TLE Eliminators

本站添加: 2026-05-24

[00:00:01]So hello everyone, my name is Vikasi and uh today we are going to solve the lead code by weekly 183 and we are going to solve all of the questions of this contest and uh in case you have any doubt you can uh comment it in the comment section and also if you have any like debugging question or something from your code uh you can also comment that. So we will start by from the first question. So our first question is the minimum swaps to move zeros to end. So in this question we are given uh array nums and in one operation I can choose any two distinct indices J and swap nums I to nums J. So it is nothing in one operation I can swap any two elements of the array and then I have to return an integer denoting the minimum number of operation required to move all zeros to end of the array. So, so in the array there are going to be some zeros but after the operation all of the zeros should be in and end like somewhere here as a suffix right so that's what we have to do and uh yeah let's see how we are going to do that okay so let's see ouruh question first so Let's take a test case and uh analyze the test case. Assume that our array is uh this one. It is 1 0 0 then 2 0 and 3.

[00:01:43]Okay. So this is our array and now we have to like we have to somehow move all of the elements like all of the zeros in end of the array. Right?

[00:01:55]So basically there are two approach for this. uh let me discuss what approach I used. So I think that how the like the optimal answer would look like or how the final array would look like. So I know that in the final array it is going to be like so these are six positions.

[00:02:16]Okay. So there are total three zeros. I know that in my final array there are going to be three zeros here and this all of the other position are going to be all nonzero elements non-zero elements right all non-zero elements because I know that all of the zeros are in end of the array right so that's I know so this is was my observation so I can see that this is going to be my position where all of the zeros are going to be. Okay. So, whichever zero is not in this range. Okay. So, this is our range.

[00:02:58]So, whatever zeros are not in our range, which means they are in this range, we have to move it, right? We have to move it. So, yeah, that's just that I counted it. So, I mean like this is the array of size n. Okay. So, this is the array of size n and I remove this three elements, right? like I have I don't have to consider the last three elements. So it is going to be the area of length n minus 3. Okay. So like in this length of n minus 3. So 6 - 3 is three. So like in this three elements I have to see how many zeros are there and that's just my answer. Okay. So there are two methods.

[00:03:36]Okay. So one is like in this range I count how many non-zero elements are there. non-zero elements are there or here I count how many zeros are there so this was my method okay and just for your knowledge let me also share you another method so another method that most of you people should have done is the two-pointer approach because that is the more famous one so what we do here is that let's let's take our test case again so it is 1 0 0 203 this is is our array. So we will move our pointer P1 here and we will move our pointer P2 here. Okay. So my P2 pointer will always like will point to a non-zero element and my P1 pointer will like will point to a zero element. Okay.

[00:04:30]So now let's say this P1 is pointing to this zero and there is P2 which is pointing to this three. So I know that this zero is not in the end. So I will just share this two. Then I will move my P1 to here and P2 will move to here and then I will swap this two and that that's how I'm going to get my answer.

[00:04:51]So this was a simple two-pointter approach and let's see the code of my approach this one. So yeah, what I did first is uh this is n which is the size of my nums array. the CNT which shows me the number of zeros and then I iterate on all of the iterate in the sub array and count how many zeros are there. Okay. So if the element is zero, I do count plus+ then I just count in the left array I mean in the left part how many non zero elements are there right? So I iterate from zero till n minus c and d okay what does that mean? Let's see here. So let's say so let's say in my final array there are four zeros. Okay. So there are four zeros here. Four zeros here. So now I know that I have to only find the number of zero elements in this n minus 4 length subarray. Right? N - 4 size subarray.

[00:06:00]So that's what I do subarray. Okay. So I I iterate on n minus ct of size subarray.

[00:06:09]And if the nums of I is equal to zero then I know that I have to do operation on that element and move it to the right move it to the end. So then I do the answer plus and then I just return the answer. So yeah that was it in the a question. If you have any doubt you can uh like uh you can share to in the comment section.

[00:06:32]uh I hope you have uh no doubt also try to and try to code it with the two-pointter approach also because it is a nice one so we will move uh to the next question now so the next question is minimum operation to make the array module alternating okay so in this question we are given some integer array nums and the integer k okay and in one operation you can increase or decrease increase any element of nums by one. Okay. And the array is called module alternating if there exist two distinct inteious.

[00:07:11]And this word distinct is very important here. So there exist two distinct integers X and Y such that for every even index I the nums I modulo K is equal to X. So for all of the even index elements the remainder is X when they are divided by K. Okay. And for every odd index element the the value at that index modulo k should be y. Okay. So yeah when you divide it by k the remainder should be y. And also remember this fact that this x and y both should be different. Okay. And then we have to return the minimum number of operation required to make this uh nums array module alternating.

[00:07:56]Yeah that's a nice one. Okay.

[00:08:00]So this is our question B.

[00:08:08]Question B.

[00:08:15]Okay. Oh, also I forgot to see what are the constraints. So the constraints are here like the length of the array is till 100 only and also the K is also till 100 only. So you can just use any brute force here. Okay.

[00:08:31]So okay first of all what are what can be the values of x and y?

[00:08:38]The x and y can be from 0 to k minus one right because yeah these are the remainders.

[00:08:44]So the values are x and y.

[00:08:48]So let me give you a sub problem. Okay let me try a sub problem. Let's say this is our array.

[00:08:57]Okay, just a second.

[00:09:14]Okay. So, let's assume that uh this is our subarray or this is our array and uh this is array Okay. And now what you want to make is for all of the odd elements you want to make it modulo k is equal to x. Okay. So for this one like a1 modulo k should be x also a3 modulo k should be x and a5 modulo k should be x. Okay. And this x is given to you. Let's say this let's say k is equal to 10 and x= 3.

[00:09:54]Okay. Uh let's set our array. This array is equal to 5 10 14 um 16 and 7.

[00:10:07]Okay.

[00:10:09]Now you want to make uh like this element mod is equal to three. Right. So this element a1 modulo k is equal to 3.

[00:10:20]So now what you can do this is our question. Okay. So like for this one you you want to make it like this. So what you can do? So either there are two option you keep increasing this element till you get the modulo k is equal to 3 or you keep decreasing this element till you get the modulo k is equal to 3.

[00:10:41]Okay. So I mean what do I want to say is that assume that this element is 15.

[00:10:49]So we know that 15 modulo k sorry 15 modulo 10 is equal to three uh five right.

[00:10:57]So now what you can do is you can keep decreasing. Okay. So let's say this is five. So then you decrease it and now you have the first element modulo k is equal to four. You again decrease and you get the modulo 3. Right?

[00:11:14]Okay. Let me be more clear. So like you we have 15 we decrease it and this is our modulo. Okay. So modulo.

[00:11:23]So the modulo is five here. You decrease it and this now we have modulo four. You again decrease this element. Now we have modulo 3. And another way can be you keep increasing. Okay. So you keep increasing until we get 23. So the module are going to be like 5 6 7 8 9 then 0 1 2 and three. Okay. So yeah you keep adding till you get 23. Right? So these are the two options and whichever is better for us. Okay. So here number of operation are two right okay like the here the number of operation are two only and here the number of operation or the number of increment we have to do are eight so we will choose this meth choose this method yeah so that's what we have to do okay so so this is nothing but okay so like the one cost is going to be what so this is uh so We know that 15 modulo 10 is equal to 5 and but we want modulo is equal to 3. So this difference this is difference 2 right which is nothing but this one and for sure the another method will be this k minus 2 which is nothing but 10 - 2 is equal to 8. So the cost the other cost will be 8. Why?

[00:12:46]Because this is 13 right and this is 23.

[00:12:50]The difference between them, the difference between them is 10, right?

[00:12:54]Which is equal to K.

[00:12:57]And so we know that this is K and this is 2. So this is going to be K minus 2, right? This is so that's it. So let's see here. Okay, this uh so like if you have some value then the minimum cost is like the difference between them and K minus difference between them that's it okay but now let's say what if you want to make the whole subarray okay whole subar or sorry a whole all element indexes is equal to x okay so Like let's say you want to have this right a1 modulo kx a3 modulo kx a5 modulo kx so what so this is nothing you will find the cost of this one let's say it is c1 cost for this one to make it mod is equal to x so and cost of this one so the c5 is nothing but cost to make the this fifth element modul is equal to x and Yeah, the summation of them is going to be my cost to make cost to make what? uh the odd all elements modulo k is equal to x right and now after this I have all of the uh cost okay so let's say like for all odd elements I have cost to make modulo k is equal to zero then I have cost to make modulo k is equal to 1 till modulo k is equal to k minus one and also for all even elements for all even elements this is same for the cost to make modulo k is equal to zero then modulo k is equal to 1 till modulo k is equal to k minus one right so that's it so now just see here in the you in the root force approach what you can see is that let's say for all of the odd elements you have made their modul equal to zero.

[00:15:27]So now we know that for the even index okay sorry here for even elements so all the even elements so if this is the thing even elements cannot have modulo k is equal to zero right because if this is x and this is y then x and y should be distinct so what I will do is I will take let's say this one then the minimum among this I will pair it with right because I mean let's say for all of the odd elements the modulo k is equal to zero so I will check what is the answer if modulo k is equal to 1 what is the answer if modulo k is equal to 2 till this one right I I will pair it and just brute force way I will get my answer right so if the k is equal to one I will check what if it is the pair of this and this this and this this and this I will just ignore this part when the module okay is equal to one and that's it. So let me see the code here. Okay. So what I have done this is my answer one. So answer one is nothing uh so first of all n is the size of the array. Then I have made the answer one. So what this answer one will store. So this is the pair. So answer one here. Okay. And let me show you the small optimization I have used.

[00:16:57]Although there is no need but let let me just let me show you. Okay.

[00:17:03]So assume that uh you are doing your brute force approach here and in the okay so let's say this is the module K is equal to zero right. So now uh with pairing this what you are going to choose you are going to take the minimum element right from all of this one. So what I thought is why not just sort the elements. Okay. So let's say uh for the all of the even elements for even elements I found something like this one elements.

[00:17:36]Let's say k is equal to 4. So let's say the cost and this is modulo k is equal to x. Okay. So let's say when modulo k is equal to zero the cost was five.

[00:17:49]Let's say when modulo k was one. Okay. I have to make for all of the even elements modulo k is equal to 1 the cost is three. When I have to make the modulo k is equal to two the cost that came is 10 and modulo k is equal to 3 the cost is two. Okay. So now if I sort the element okay so like how do I going to sort it? So let's say this is two and the modulo k is equal to three here then three modulo k is equal to two uh this are my cost then in the I am just writing in the sorted order okay mod is zero for it and sorry it was one and the cost is 10 when mod is equal to two Right. So now for the the observation here was like for any odd element okay for any odd element I am trying to pair it with in in E even I am going to pair among these two okay like how let's say in the odd in the odd modulo k is equal to one so now I'm going to pair it with this one when the mod k is equal to two I am again pairing it with this one right so in the odd modul k is going to be two and in the even modulo k is going to be three with the cost of two right let's say when modul k is equal to three now I cannot pair it now I cannot pair it with this one so nothing I will just pair it with the second one right that's it so that was a slight optimization I have done in this one okay so what we do so this want is the remainder we want okay so it is from 0 to k and I iterate it and find for all of the like odd element what is the cost if I want to make the element module k is equal to one. So this is cost one which is for all of the odd elements and this is cost two which is for all of the even elements. So you can just have two different loops but I have just done it in the one loop only. Okay.

[00:20:04]So like first of all this is the value.

[00:20:06]So the value is numi modulo k. Okay. And if I modulo 2 is equal to zero which means it is at odd position in term of one base indexing. So I add it into the cost one. Okay. So I do cost one. This is the formula we discussed earlier right the difference between them and the k minus difference between them and whichever is smaller we will take it.

[00:20:34]And if I mod 2 is equal to 1 which means that it is the even element. So I will add it into the cost of two which is the cost for even elements. Right? Then in the answer one which is for all odd one I will add the cost is C1 and the modulo is want. And for the even elements the cost is C2 and the modulo is want.

[00:20:57]That's it. I initialize my answer with a pretty big number. I sort the elements for the even element uh even indexes like as we saw here that I only need to care about the first two elements only right so that's I do I it on all of the elements and uh then I find my best pairing okay so this want is I mean what is the modul of answer one okay so the modul of answer one so let's say this zero. So I know that I have made my all of the odd elements as zero module.

[00:21:38]Okay. So now in the answer two it should can it cannot be zero module. Okay.

[00:21:43]That's it. So that's what I check. So if my answer two of zero dot second is equal to one I will take the answer two of one which means the second element else I will take the first element and that's it. D answer. So the what is the cost? So it is first of all the cost to make the odd elements as the module okay is equal to want and this is the cost for the even indexes right so the answer is the summation of these two elements and answer is equal to minimum of answer and the answer and I just return my answer so that's it in this question although what you can do is you can just uh remove all of this stuff and just uh brute force pairing. I mean you can just run a 2D loop and yeah just count the minimum answer.

[00:22:41]Okay, that was it in this question and I hope you understand this question like the main thing here was the key are smaller and also the size is smaller. So you just have to do the brute force approach.

[00:22:54]Okay, that's it. So now we will move to the next question.

[00:22:59]Okay.

[00:23:02]And yeah, this is my favorite question from this contest. Okay. This was better than the D question in my perspective. Okay. So, what we are given? So, we are given a M cross integer matrix grid. Okay. So, we have a 2D grid. Then there are two players. So, the first player starts at the cell top left. So first player starts at here and can move only right or down. Okay.

[00:23:32]And the destination is the bottom right cell. Okay. So the first player starts from here and go from like right down right right down something like this and comes to the this bottom right point.

[00:23:44]And there is the player two who starts from the bottom left cell which is this one can go only right or up. So it can go like right up right right up and something like this and comes to this point uh the right up cell or top right cell. Okay. Now each player must choose a valid path from their respective starting cell to the destination. Okay.

[00:24:11]And a cell is called said if it belongs to both chosen paths. and we have to return an integer denoting the maximum possible sum of the values of the said cell. Okay. So I mean let's see let's see the this example. So for the first player the path is this one and for the second player the path is this one and the elements in this pink one are the cell and yeah the sum of them is four which is our answer here. Okay. uh the m is grid length n is the uh the columns m and n both are till 1,000 which means that their multiplication are till 5 e5 oh sorry 5 e5 so which means that there are five e5 elements so we have to find something like of number of element of o of n login something like that or sorry n cross m log m cross m something like this and each of the grid value are till from like minus 100 to 100. Okay. So this is like I divide this question into two part. First one is finding what is the logic and the second one is how to implement that logic.

[00:25:30]Okay. And both were like a different qu question itself.

[00:25:36]Okay. So let's take some test cases and uh try to find our answer.

[00:25:41]So yeah, let me take a new page.

[00:25:48]Okay, so this is question C.

[00:25:58]So the first thing you should try to uh think of is what can be like sad cell what what will be the geometry of the region of the sad cell right I mean let's say let's just assume that the grid is something like this.

[00:26:23]So this is our grid.

[00:26:29]Okay. So now like ask yourself uh can uh okay like can I the sad cell graph can be like uh this one.

[00:26:43]Okay just a second.

[00:26:52]Okay. So like can it be like this one?

[00:26:55]Can it be this region?

[00:26:59]Uh sorry can it be this region and you will find that yes uh there is a way to okay just give me a moment. Yeah, let's try some different regions and find that how how should be my the region of this uh sad cell can be look like. So let's try to find if it can look like uh this region. Okay. So only only these two cells can it be like this? So yeah when you try to find you can get that yes there is some way.

[00:27:40]Okay and like what what we can do is this first player goes from here comes to here and goes here and the second player our second players starts from here comes to here and yeah goes here. So we can see that only sets are J2. Okay.

[00:28:01]Okay. So this is possible.

[00:28:03]Uh can it be like uh okay let's remove this.

[00:28:14]So now let me ask can it be like uh this region?

[00:28:21]Can it be like this region?

[00:28:24]Okay. So like for that we know that uh the person like for the cell set uh sell the both of the players should go to that visit that cell right so like for this one let's say the player two yeah it can easily move right but for the first player we can see that we can see that it it cannot visit all of these three cells right It is impossible for it like it go here, it comes here. Now it has two choices either to go right or either to go down.

[00:29:03]If he go right, he cannot he cannot come at this point.

[00:29:07]Right? So then from this we get that the our region of the cell can be only in one row or in one column only. Yeah, that's it. So I mean the the region of set cell can be like this column or it can be like this row or it can be like this row but it cannot be like uh this one or it cannot be like uh this region I mean this four cell right it cannot be like that. So that was our first observation.

[00:29:44]Let me write here. So this is observation one that the region of a said cell is only one row or one column. Yeah, that's it.

[00:30:06]Okay. Now let me see can it is there any other constraint on this uh sad cell region like let me try to find this okay like can it be only one cell so let's try to make the set cell region as only this element so can can it be like this and yeah we will find that yes there is one way so like our first player will go to here uh Sorry.

[00:30:39]We'll come to here. Go here. So, this is our in for first pair and out. Out from here. And yeah, just do whatever. And the the other player can come to here.

[00:30:50]Let me change color.

[00:30:53]Other player can come here in from here and out from here and go to this region. Okay. So yeah here you can see that uh the set cell region can be only for of one element but you can see that for that there should be four adjacent elements right so that because for first player it needs in and out and the other players it also need in and out and all of this four should be distinct right so in and out for the first player and in and out for the second player all of these should be distinct So that should be four different things.

[00:31:35]Okay, this is like so what will happen if it is it has uh less than four adjacent cell. Okay, I mean what what about what about this cell or what about this cell, right? I mean this cannot be the uh sorry this cannot be the only region of the set cell. Okay, so let let me give you a test case again.

[00:32:01]And this was another nice observation.

[00:32:03]Okay. So yeah, I like this question because it required a thinking of this two observation.

[00:32:16]I mean okay now you you uh you analyze that uh if you can make uh this element only this element as the sad cell. Okay.

[00:32:29]So let we try. So let's say our first player come here and get out from here.

[00:32:38]And let's say our second player comes to here. And now wherever he go like if he go up then this also is going to be a sad cell. Sorry. And if he go here this is also going to be a sad cell.

[00:32:53]So this cannot be alone a region where it is the like region of sets right.

[00:33:00]So like if it is the uh cell which have less than four adjacent cells then there should be uh minimum two uh region right I mean then the region should be like uh can be like these two elements right because yeah in this it is possible like uh the first player comes here and goes like this and the second players comes here and goes like this. You can see there are only two set cell. Okay.

[00:33:34]So for length two I I mean if it is adjacent one then uh any like it it cannot be alone the region of fat cell this and this two where the observation okay I mean yeah that's it.

[00:33:57]So this is something like a kadanis algorithm right. So first of all like we will just see each column or each row individually right because I mean I first I will come here and see what is the maximum subar sum I can make then I will get the answer. I will go to this row and I will find the maximum subar sum. So first of all all of the rows and columns are independent.

[00:34:24]So yeah and the so this can uh we can find the answer similar to the cadence algorithm there is a little difference what what is the difference only the point was that the adjacent cell oh sorry the cornal cells which have less than four uh sorry the boundary cells cannot be alone.

[00:34:49]This is the only problem. So how you are going to solve this?

[00:34:54]So first of all uh you you can break it into two parts.

[00:34:59]Okay. So into two components, right? Let me rephrase our question again. And now this like our part two of our this problem will come.

[00:35:15]So I mean for this column. Okay. So we are checking the answer for only column only. Okay. So like for all of this rows or these columns the question is nothing but maximum subar sum subarray sum and only condition is where sub array is uh not the end cell. Okay. Not the end cell only. End cell only.

[00:35:54]So I mean we have to consider all the subarrays. I mean we we can consider this subarray or this subarray or this subarray except except only this subarray. I mean or except only this subarray. Yeah. Because this this cannot be possible.

[00:36:14]And for this thing and for this thing it is the max of array of length at least two at least two.

[00:36:38]And these two are different questions.

[00:36:40]Okay.

[00:36:43]Why? Why here? Because you can see that like all of the element of this column have less than four adjacent elements, right? So for each column it it cannot be alone. So it it should be at least paired with any other element, right? So subarray should be at least of size two for any uh subarray of this column. Also same for this column. And for the middle ones you can see that only the boundary elements only the boundary elements have less than four uh less than four adjacent cells.

[00:37:20]So only this cannot be uh the subarray of length one. Okay.

[00:37:27]Now these are the two question and uh if you were stuck in the logic of this thing. Okay. Uh no worries. Now pause this video and try to solve these two question. Okay, let's forget everything.

[00:37:43]Just think I have given you an array and you have to find the maximum subarray sum which has the length of at least two. And another uh question is I have given you the subarray and you have to consider all subarray except except the subarray which has only starting element and the subarray which have only end element except there's two subarrays. You have to find the maximum sum among them.

[00:38:17]And yeah this is the another question.

[00:38:19]So yeah pause and think for this thing.

[00:38:24]Okay. So I hope that you have think for these two questions.

[00:38:29]So now we will consider this question first. The max sub area of length at least two. So for this question you can uh use the DP easily.

[00:38:42]Okay. And what what what should be the states of DP?

[00:38:47]So it should be like uh uh there should be like two states.

[00:38:54]Okay.

[00:38:57]Uh no let me just discuss the cadance algorithm.

[00:39:02]So okay assume that uh uh you have just analyzed our answer.

[00:39:08]So yeah DPN currents are just same thing to be honest and you have analyzed for this and let's say now my current is this one. So I am just using the simple scatterance algorithm. Okay I have analyzed I mean I have used the algorithm till here and now I have sub current which is the maximum subs ending at this position. Okay. uh you can use also use DPA. So dpi will be the maximum subarray sum ending at this position. Right?

[00:39:45]Uh now what you can do? So uh you come here. So okay let's assume uh let's analyze this thing. Uh let's make the DP. So, DP of I is equal to max sub array sum sub array sum ending at I ending at I and yeah of length greater than 1.

[00:40:14]ending at I. So when you come at this I + 1. So this is our I. So when you come at I + 1.

[00:40:22]So let's say the the optimal subarray for this one for the I element. Okay.

[00:40:30]Now if you go this I + 1. So one option is you can just extend this this sub.

[00:40:36]You can extend this one, right?

[00:40:39]Or the another option is you can get this sub area of size two.

[00:40:46]So these are my two options I can have.

[00:40:50]So either I can just extend the previous subarray or this is the new subarray I make.

[00:40:59]So that's it. So DP of I + 1 is nothing but maximum of DP of I plus uh the let's say current element which is I + 1 or it is just a R r of I plus a R of I + 1 that's it. uh so it was a very simple and fundamental question of DP and you can also do it with the cadance algorithm easily. So in the if you want to do it with by the cand algorithm it is nothing you just do the current plus is equal to a r of i as usual.

[00:41:42]You do answer is equal to maximum of uh answer and current as usual.

[00:41:49]But you cannot do this point. You cannot do this thing. You cannot do this.

[00:41:58]I mean yeah we we do the current is equal to maximum of zero and current.

[00:42:01]You cannot do this. You can do current is equal to maximum of uh sorry maximum of current and the ar of I or a r of i minus one.

[00:42:16]That's it. I mean that's just the dp state and as we discussed. So yeah that's it. So this point is clear.

[00:42:26]Okay. So this were two sub problems.

[00:42:29]This problem is clear now.

[00:42:32]Now we have to think of the this point.

[00:42:34]Okay. Maximum subarray sum and except the two subarrays only. Uh the one subarray is the subarray starting at this of length one which is just the starting element and another subarray is just made of the end element.

[00:42:52]So now how we are going to do this point uh this question.

[00:43:10]Okay. So for this thing yeah we don't have to use any like an any algorithm or something. I think we just have to do a slight change in uh our kadans algorithm or DP right I mean you you can just find the answer for DP0 right and you just start counting or you just start cadance algorithm from element one or something you can do something like this so this thing was very easy so what I did is uh here I just uh uh I mean I just uh just a second okay let let's assume that we are making the DP right as usual as we do in the maximum subarray problem so what I did is that I know that there cannot be any subarray starting from zero right so there cannot be any So I I I just forget about DP0. I just initialize it from DP1, right? And DP2.

[00:44:23]So this DP of 0 is zero.

[00:44:29]Yeah. And uh then you can just do the Cadans algorithm as usual. And when you come at this DP of N or let's say N minus one in case of zero base indexing.

[00:44:40]So when you come at the last index here uh here you cannot do the current sorry so this is just the maximum sub area problem okay so you cannot do the uh just a second yeah you cannot do dp of n minus one is equal to so let me write here is equal to maximum of dp of n minus - 2 + current element or only error of five uh sorry this is n minus one this is also a n minus one you cannot do this point because this thing is not possible so yeah when you come at this last element you you uh so if your i is equal to is equal to n minus one you only do that dp of n minus 1 is equal to this one dp of n minus 2 plus the current element that's because the one length subarray here is not possible. Yeah. So that's it. So that's only thing you have to do in the second sub problem. Okay. Uh what in the code what I did I just changed the kadans algorithm algorithm which is maybe slightly tough to understand but I hope that you understood this this point right. So this was like the sub area of length one. So we just ignore this point and like the elements which are ending at the first position. So only one fiber is possible, right? So we also ignore this point. That's it.

[00:46:21]And uh this same changes you can do in the cadance algorithm, right? Yeah. The only change between the DP and the cadance algorithm is you you don't use the DP state. uh instead of it you just use the current and yeah that's it.

[00:46:39]So let's see my code.

[00:46:42]So what I did is so yeah first of all this is going to be my answer and I gave it some dummy value right because it cannot be zero because maybe my optimal answer is in negative.

[00:46:56]So yeah, I just uh initialize it with some value or some dummy value or you can say some region but it is a valid region right. You can you can have this set cell always possible.

[00:47:12]Then n is the size of the grid and m is the number of columns in the grid. This is number of rows. Yeah, be clear that uh there is uh some interchange right here n is different and m is different but forget this thing then what I do uh so for all of the rows I try to count it okay so I go in the all of the rows and I just do my kadans algorithm or like maximum sub error problem individually so that's it uh so this is my dummy answer which is going to be uh the first two elements of my subarray. Okay.

[00:47:51]Now these are two possible cases. If I is equal to zero I mean this is first row or last row and this is elsewhere.

[00:48:01]So let's see this case. What if I have to take the sub array of size at least two.

[00:48:08]So if the size should be at least two I just do my cutans algorithm as usual. I take the current is equal to D answer first or or I have to do the grid of uh sorry because I have to do this thing current should be equal to this point and then I go from Z is equal to two okay I do current is equal to maximum of this thing so this is nothing but current is equal to I just extend the previous segment or I make this new sub area of length two only and the answer is equal to maximum of this thing. Uh this is also like can be done by DP. So like if I do it by DP so DP of I is going to be the maximum of uh DP of I minus 1 plus uh grid of uh so this is going to be J in particularly and grid of I J or I make the new sub which is this one I and J minus one. So, so yeah both are same you can see in case you you have some doubt with the cadance algorithm and I just do the answer is equal to maximum of this thing.

[00:49:33]Okay. So I hope that's very easy.

[00:49:36]Now what's here? So uh you can see here I just uh ignore the state zero. I just start from the state one.

[00:49:47]Right? because I know that I don't have to count the state zero current in this D answer. Right? So that's what I do. I just make the current is equal to this then then start from this I J is equal to 1. Yeah, that's what we talked here, right? We ignore this one and we make the special case when N is I equal to N minus one. Yeah, that's it.

[00:50:13]So then I do current is equal to grid. Yeah, as we do in the cadance algorithm as we do this in the cadance algorithm. That's it. Now what what is this point? If J is not equal to M minus 2 then only I can do this uh this line. Okay, what does that mean? So just think what does algorithm mean? So cadance algorithm is nothing but let's say I analyze till here and if my optimal subarray is positive I extend it else what I do else I just ignore the this sub any sub area I just make this new sub area from this right because any subarrays ending at this point are negative so yeah this are going to be bad for my answer but for the last element like for the last element here. So when I am at here I cannot make the current is equal to zero.

[00:51:17]I I must take some sub some segment right because if the current is equal to zero which mean that I am not taking any sub ending at this one that when I come here the subair is going to be this one only which is not possible. So yeah that's what I do. If J is not equal to M minus 2 then only I do the current is equal to max and the answer is going to be the maximum of answer and the answer.

[00:51:41]That's it.

[00:51:43]Okay. So we have uh so we are done in the code. Okay. So we have found the answer for the rows, right? But what about columns? So yeah, you can just write this code again for the columns.

[00:51:58]But what I did is that I just uh I mean I have just uh make all of the rows as column. I have just interchange rows and columns.

[00:52:18]Just a second. What does it say?

[00:52:22]Yeah, I have just impose of this matrix so that each rows is now column and each column is now my row. That's it. So I make a dummy uh grid and I just iterate and my this like this dummy of JI is going to be grid of J. That's it. And I just do grid is equal to D. So now my each column is the row and each row is the column. Right? That's it. And then I just copy paste this uh thing again here. I copy paste this thing and I just return my answer. So that was it in this question.

[00:52:59]And yeah like it was a two-part question you can say. First was finding the logic and second was applying your DP here.

[00:53:10]So it was like the slight change in the DP states and how you iterate. Okay. And if you cannot solve this question, so please try to solve it again with the DP states.

[00:53:25]Okay. And let me move to the next question which is the last question of this stream.

[00:53:32]And it is again like a very fundamental DP question. It is a yeah simple take non tech question of uh on DP of DP on graph. So let's read what it says.

[00:53:46]So in this question we are given a rooted tree with uh okay let let me pick it. Yeah. So we are given a rooted tree with nodes labeled from 0 to n minus one represented by integer array parent. So yeah the parent array just shows what is the parent of the node. So yeah, parent of zero is going to be minus one because node 0 is the root node and for each other element parent of i shows me the parent of node i. That's it. Okay, I am given an integer as nums of length n where the nums of i shows me the value of node i which is okay and also I have given an integer k. Okay, sorry. This is the DP on tree question and uh I have given an array which gives me what are the value at each node and also an integer k is given then a non- empty subset of nodes is called valid if the sum of values of selected nodes is divisible by k. So we take a subset of some some nodes. Okay, I mean we take set of some nodes then it is that set is called valid. If the sum of the value of selected node is divisible by k and no two selected nodes are adjacent in the tree and I have to find the number of valid subsets modul 9 + 7.

[00:55:22]So try to pause it and uh think and just give me a minute.

[00:56:11]Okay. So like first of all uh we see the constraint here. So the n is the which is the number of nodes is still th00and and the k is still 100. So maybe you have to find our answer in O of N into K or O of N into K² right?

[00:56:39]So first of all we have to think like okay so let me share you one thing.

[00:56:48]So yeah this is our question D.

[00:56:52]Question D.

[00:57:02]Uh so whenever the question of tree is there and a hard question of tree so there are no uh not many concepts are there. Okay.

[00:57:13]So I mean the question can be of uh just simple DFS or it can be of DP or it can be of uh rerooting DP rrooting DP or it can be like uh of uler tour or it can be of uh What it can be of DSU uh which is just small to large merging.

[00:57:57]This is a very nice concept and my personal favorite. Then it can be of like HLD or center decomposition.

[00:58:05]So like there are not many different concepts in the tree. Okay, there are not many algorithms like in graphs there are so many algorithms. So here in the tree question you can try to implement everything right like can this can be solved by rrooting or uler tool or DSU and these two are tough one. Okay, so these two are like 2,000 rating plus questions.

[00:58:31]Okay. So here the first thought I had is uh I tried to uh solve it by DP. So like if I have to try it by DP what I have to think like I have to ask a question that if I know the answer for answer for a answer for a sub tree sub tree of some node let's say sub tree of node uh can I get answer can I find the answer for parent right this is the question you should ask and uh so I tried thinking on this then I tried to solve what can be the different states of the DP okay uh how do you find the different states so I mean you have to ask like what the data you need of the sub tree to find the answer for the current node. That's it. I mean what data you need from all of the child so that you can find the answer for this node.

[00:59:48]So let's see here.

[00:59:51]I mean what I thought here was let's say this is our child. Okay. So this is our child one. This is our current parent.

[01:00:00]This is our child two.

[01:00:04]Okay.

[01:00:05]So now first of all uh you can clearly see that uh if if you take if you take this parent one if you take this parent node you cannot take this CH1 or CH2 and if you not take this thing then only you can take CH1 and or you can take CH2 that's it so yeah this is uh the case of take non-tech But now only thing you have to find is what are the required state. Okay.

[01:00:45]And also like this is a very fundamental question of DP. So in case you have solved a similar question like this you are you can just find the states very easily. So here the states was like uh uh DP of uh DP of uh I or let's say current and let's say X.

[01:01:19]So this is nothing but number of subsets number of subsets in a sub tree sub tree of current node of current node such that such that there some modulo k is equal to x. So yeah this is just n and which current is like vary from number of nodes. So this can be value from 0 to n minus one and this is the modulo. So this can be 0 to k minus one. Right?

[01:02:05]So now let's say if you have the answer for this one and this one how you are going to find the answer for the parent node that you have to think. So I mean just pause here and try to think on yourself if you were not able to solve this in a context.

[01:02:26]Okay. thought.

[01:02:41]Yeah, I hope you think for some time and you got the answer and in case you have not find the way. So it is nothing just the take non take DP. So what you will do is you will consider this value uh you will consider this child.

[01:03:00]Then what we will do? So let's say let's take our let's take a test case. Okay.

[01:03:08]So first of all let's say this is our parent and this is its child and let's say K is equal to five. So for this thing there are going to be five values.

[01:03:23]Let's assume that they are something like this.

[01:03:27]So I mean this thing is nothing. It shows me the number of subset such that such that some modulo k is equal to so it is 0 1 2 3 4 right.

[01:03:44]So some modul k is equal to one for this one right. It shows me this and then I come at parent. Okay. So for parent there are also going to be five values but there should be two states right for take and non- take but let's just ignore that for now.

[01:04:04]So here uh so first of all you have to initialize it right. So you can say that if you take this parent one let's say the value here is uh uh let's say the value is dum.

[01:04:24]So this is just the simple DP. What you will do is you will take this value. You will try to pair it with this one and whatever the sum is you will add it.

[01:04:36]Right? I mean you will take any okay let me take here okay this is CH1 this CH2.

[01:04:44]So you let's say that you have uh you have done the case for this thing. Okay, you have find the case for the CH1 and you have got some uh DP here. Okay, so this is the DP for this one. And now you have to also add the answer for CH2.

[01:05:04]So we know that so what what does this show? So we can see that so this is our P and CH1 combined. Okay. And we have to also combine the answer for CH2. So just listen this carefully. So this shows us that there are three subset such that that modulo k is equal to zero. Right? Now what what does this shows? This shows that there are three subsets such that the mod is equal to one. Okay. So now just see this carefully.

[01:05:41]So there are three ways into there are three ways. Sorry into there are three ways.

[01:05:48]So like if you take any subset of this thing and any subset of this type of thing the what is the modulo going to be? The modulo is going to be 0 + 1. So the modulo is going to be one right. So there are 3 into 3 9 ways.

[01:06:08]Right? I mean okay let let's be let it be uh more clear with some another example let's say you take any subarray of like which have the modulo is equal to two okay so modulo 5 is equal to two right so because this is my indexing so here you take one subarray like from this thing you take one subarray such uh sorry one subset such that modulo k is equal to two and also you you can take any sub subset from this child two right such that the modulo k is equal to 4.

[01:06:53]So if you combine this both subset so it is 2 + 4 modulo 5 which is going to be 1 modulo 5 and there are 5 + 3 there are 15 ways to do this right so that's it you just have to by brute force you just have to add into answer right so that is our uh the fundamental DP concept but now the only catch is The only catch is we cannot take we can't take adjacent elements right adjacent nodes.

[01:07:37]So now we have to consider 2DP 2DP states which is take current one and not take current right not take current one.

[01:07:53]Why? So let's say this is my parent and these are my child.

[01:08:01]This is child one. This is child two.

[01:08:03]Let's say if I am uh taking this current one. Okay. So I am taking the current element. So I know that I I have to only considered the DP of non. I have to only consider the DP of not take right.

[01:08:21]But if I am not taking the this element, if I am not taking the parent, so now there is no restriction of on child one.

[01:08:35]It can be either I can take the child one or not take the child one, right?

[01:08:39]Plus or so like no restriction on child two. I can either take the child two or not take the child code. So I will see both ways and that's it.

[01:08:52]So what I will do is I mean I will make a DFS in the DFS I will I mean let's say this is our tree this is like some big tree so for this I will make the DFS to count the answer for this I will call here and here they will count then I come here I come here and uh for this PA I will calculate its DP DP how I'm going to calculate? So I will consider this uh DP first. Okay. So let's say this is its DP. This is my initial DP. So initially all will be zero.

[01:09:32]And here let's say this is some values.

[01:09:34]Okay. So I will just do brute force all of thing. I will just brute force and then I will have my new DP and I will also take the this child value and I will take this new DP and again I do do my transition and yeah and I return then my answer is going to be what is my answer is going to be so answer is going to be DP of zero. So this is how my uh the node node because zero is the root node. Then take and the modulo modulo is zero right this is the modulo because modulo is zero means that it is divisible by k plus dp of zero not take and zero that's it but there is a slight catch I also was not able to found during the logic but like I tried this method and found that my answer is coming one extra but then I I got the issue I have to do minus one.

[01:10:56]Why? Because during this way I am also counting the empty subset right empty subset because for empty subset the sum is equal to zero which is divisible by K. So yeah you have to do minus one here. So yeah that's it. I mean what that's what you do. So let's see the code.

[01:11:23]So okay so yeah I just do use everything into long long because maybe by multiplying it it it can be problem in int.

[01:11:41]So yeah my module and first of all what I do here uh so n is the number of nodes I make the adjacency list. So like it will have all of the childs I mean like for uh like adjacency of zero will give me the list of all childs of zero. That's it. So I make this adjacency list.

[01:12:07]Right. So I mean for this parent what is the child? So the child is I. So that's what I do like it in this parent array.

[01:12:18]Now comes the main part. I make the two different DPS.

[01:12:22]Uh although you can make a 3D DP but I felt this was easy. So this is DP of zero which shows me not take. Okay. when I don't take the current one and DP of one is nothing but I take the current one I find the I I call this function which will find the answer and the answer is nothing but DP of 000 uh this is the current one okay so let me be more clear here so here like uh the DP of I shows me sorry DP of I is The number of subset in a sub tree of I such that there sum modulo K is equal to J. That's it.

[01:13:26]So this is my DP. Uh so DP of zero will show me this thing and the current one is not taken and DP of one will show me the number of subset in sub tree of I so that that subm module K is equal to J and the current value is taken. Now this is our main function we see here. So it will have a current then the adjacent list this our both DP this is our nums array which shows the element at each node and this is our K.

[01:13:57]Okay. So now here I have to uh I should have the two different sorry this is mistake.

[01:14:08]I have a two different uh uh arrays. Okay. So this is my old and this is my new.

[01:14:18]So why why I cannot just add into DP directly?

[01:14:22]So in case you don't know about this, you can read it online like try to solve CSS problems of DP and let me be more clear. Assume that my DP asks my DP as this value. Okay. So let's say it is 2 3 5 7 and then this is some child. Okay. So the child has this value 3 2 57.

[01:14:56]Now you see here when you are calculating for this three and uh let's say uh this uh three okay so this is zero this is one then sub array is going to be uh sorry the final module is going to be one. So yeah you you will add here okay so 3 + 9 and let's say you just add here only so it is going to be 12 right now let's say you come here and you you count so you are going to recount something many times so yeah that's problem so therefore we have to make a new sub array sorry new dp so you will count from here and add it in the new one so that's it yeah it is a very fundamental Okay.

[01:15:44]Okay. So if I am not taking the thing then old of zero is going to be one because there is one way such that I don't take and in the old one. So it is the DP when I take the current one. So if I take the current element then there is one subset which have the this module right which is num of current module okay is equal to one. So this is my base case. Then I do iterate on all of the child.

[01:16:13]I find the answer for child first. Okay, I have the two new array.

[01:16:20]And what I do? So for my transition, I just iterate on all of the possible pairs. Okay. So this is my first possible pair from 0 to k minus one I mean value and this is my second possible value.

[01:16:35]Okay, we find the case for zero. So here we find the case when current is not taken.

[01:16:49]So if the current is not taken so there are and what is this thing? So let's say from the current uh one I take just a second I take some subset such that uh the some module okay K is equal to I and from the child from the child I take some subset such that such that the sum modulo k is equal to j. So then final modulo will be what? I + J module. Okay. Right.

[01:17:41]And sorry and number of ways to do this is just the num of ways just second.

[01:17:54]number of ways of I into the number of ways of J right the number of ways of J this is also the number of ways to get I so yeah that's it so let's see if I don't take this one then on child there are no constraint right I can either take this child or not take this child.

[01:18:28]So if I take this child and want to get modul.

[01:18:32]So it is dp of 1 chi or dp of zero chi modulo. Then what is in new? I will add.

[01:18:41]So the new final modulo is I + j modulo k. And how many ways are there? So first of all I have to add into this thing right. So this new of this thing is going to be new of this thing plus something. So plus what? So it is old zero of J right. So like from the old thing I have the modulo is equal to J and into V of zero modulo and if I take the current one then from child the only option is that I don't take the child.

[01:19:15]So it is nothing but DP of zi and yeah that's the same as above. So after iterating all of this thing, after iterating all of this thing, I will make the old is equal to new. Right? And after I count for all of the child, after I count for all of the child, uh my DP of current is going to be this one. Yeah, it it can be old zero or new zero. Yeah, it it doesn't matter here, but that's it. And yeah, that was the code. So yeah, I mean this was our state, this were our base case and yeah, this was our fundamental transition and like in case you have any doubt, you can share me into the comment box or you can uh or like if you don't know this type of uh fundamental DP, you can solve the uh you can solve the uh at coder DP contest.

[01:20:18]Or you can see Okay. Yeah. The main thing is you can see the T eliminator DP playlist.

[01:20:28]Yeah. Uh that's from where I learned DP.

[01:20:32]You can solve at quarter DP contest and you can solve the CSCS problem set.

[01:20:38]So yeah that's it on this question. If in case you have any doubts or something, let me know into the comment box. And uh until then, yeah, bye-bye.