Leetcode 3938 | Maximum Path Intersection Sum in a Grid | Leetcode biweekly contest 183

Added: 2026-05-24

[00:00:00]Hello, in this video let's discuss third question of today's contest. You are given an M into an N integer grid or matrix grid. Two players move across the grid. The player one starts at the top left cell 0 comma 0 and can move only right or down. Their destination is the bottom right cell Mus 1, N minus one.

[00:00:19]Player two starts at bottom left cell M - 1, 0, and can move only right or up.

[00:00:24]Their destination is the top right cell which is 0, N - 1. Each player must choose a valid path from the respective starting cell to the destination. SL is called share if it belongs to both chosen paths. A return integer denoting the maximum possible sum of value of all shared cells. So initially we have a grid and then the player one is at 0 comma 0 and second player is at this mus 1 comma 0 and the first user or the first uh first player can go only right or only down like only right or no and then this player can move only right or up and then this player should finally reach Mus 1 - 1 and this player should reach Mus 1 comma 0. So this player one must reach M - 1 - 1 with up and down sorry with right and down and then this player should reach M - 1 comma 0 by using right or up.

[00:01:26]So in this way the both players should reach their destination and if for uh we have to find the maximum sum of shared results. For example, if these these three are common between the both path, right? Because P1 should start from here to here. So there will be some path and then similarly P2 will travel some path and then we'll reach this point. So between these two paths there can be few shared cells or there cannot be. And we have written the maximum sum of shared cells that we can get and the constraints are the length and m and are up to th00and and the number of cells are up to 1 10^ 6 and then the grid values are from - 100 to 100. So let's take an example first. So let's take the small one. So 4 - 2 - 3 the cell values and initially the player one is at it the cell and player two is at the cell.

[00:02:25]Let's uh take some example of path one.

[00:02:28]So player one can come to down and then right and then right and then down and then right. So this is the path for player one and similarly the player can take whole.

[00:02:43]The player can take hole up and then whole right. So these two are valid for both P1 and P2. So what are the shares among this? For the first one, these are the cells. And for second one, these are the cells. So water shed only these two.

[00:02:57]This one and these two. And the maximum sum, the sum is three. And if we try to take all the possible paths, then the maximum sum we can get is only three. So return three.

[00:03:07]And now coming to the first example. So hope you can come up with a solution for that.

[00:03:13]So the path the player one can come down and then this and then the player two can come this and then the maximum I can get is four. So first thing right. So let's try to boil down to find if uh if we can try to find what are the shared cells easily. So let's take a grid again.

[00:03:43]Yeah. So let's take these four are rows and then these six are columns. So player one is at the cell. Player two is at the cell. So let's keep concentration on only on player. Let's keep the whole idea on player one. So how can the player move? He can move only right and down. So let's try to draw some paths.

[00:04:00]So let's say this is possible. This is possible.

[00:04:06]This is possible. Let's let's stick to these three because the first one like any path can be boiled down to the first one. So sum down, sum right, sum down, sum right and so on. And similarly we can take this as well. Right down, write down, write down, write down. And this is the one with the whole the first row, last column. And similarly, this one will be whole, first row and last column. So these four are the ideal paths for the first player which will follow the rules. So the user the first player cannot go like this. Right?

[00:04:39]The first player cannot come like this because he can go only up or right.

[00:04:44]Sorry he can go only down or right. So these four are the only type of valid path that you can get. The length of this can vary. The this can be two steps. This can be three steps. This can be five steps. Anything but the order will not change. It will be it will be just like a step signal. Right? It will be just like this one. or it can be simply like a whole row like this. So these four are the only paths that we can get for player one. Now let's take each of these very uniquely. Now let's stick with this two for now. Now so this let's assume this is the fixed path for P1 first case and then the second case let's assume this is the path for player one itself. Now now let's think about P2. So if you are thinking about P2 what all can be shared cells? Now for example the player two came till here and then he came till let's take a different color.

[00:05:42]Now player one came here and then he came till here and then he can go up.

[00:05:50]He can go up and then he can come like this. Or he can come till here and then he can try to take like this and then something like this. Or the player can take something like this. Or the player can take something like up till here and then like this and like this. So like these are some kind of paths that you can get. So if you observe what are the cells that will that will be shared.

[00:06:17]What are the paths that will be shared?

[00:06:19]For example, let's assume that this is the path one, right? This is the player one path. Now, if the player two reaches till here, if the player two reaches till here, then what are the choices that he have? What are the choices that he can take? The player reached here.

[00:06:32]Then what are the what is the path that he can take? The first thing is he can try to take till here and then he can try to go up and then once he goes up is there a way that this player will reach the path one again of player one? No.

[00:06:47]Because let's say the user the player two came till here and then he he came to here and then he came up top and then he can take only right uh or up right he can take only or up. So once he crosses this one is there away will he come to here ever? No because from this he can go to up or only right. So he can be like this only or he can go like this he can never come to this he can never come to this or he can never come to this. So from this are we able to see anything?

[00:07:16]So if the player one uh if the player one or player two let's uh let's check P2. So if P2 is crossing some cell for P1 path then after that path if he goes up then there is no other way that there are other future shared cells. So the path can be only till here. The shared cells are only here.

[00:07:38]So if we take this path again let's assume this is the path P1 has. And now let's take different cases again. So the player two came till here. Now what are all the options that he have? He can uh he can go up. He can go one cell up, right? He can go one cell up and then he can take right and then and then we don't care because once he reaches any cell so if he's re if he's a if he is crossing player one path at this cell then there is no other way that this this P2's future path will coincide with any of the P1 path because once this is changed he can go only right or up but the player one already went down right because what does the shared cell means it is coincided with both. So the player one the path is this but the player two reached this cell but after this he moved to right right he moved to right.

[00:08:31]So from then there is no other possibility that there will be any future here because these will be completely independent and there is no way that he can come to down again because he can go only up or only right.

[00:08:43]Now let's take the other case again. Now yeah now he took two steps so he came one and then he came two. So now there are two shared cells. Now even then let's assume the same path. So he came to here and then the user try the player tried to take right. So now even if you try to take at least one right. So now let's assume the player is at the player two this position. Now if the player two is at this position is there a way that the P2 will meet the P1 path again?

[00:09:10]Never. Because from this he can go only up or only right. But the player already crossed this right. The player can went down. So there is no way that we can come to down again. So we are coming to same conclusion here as well. Now the same with three as well. So even if the player took three shared cells even then the he will come here because we assumed that there are only three shared cells.

[00:09:34]So he took the three common cells from the vertical line and then he came to right. So even now there is no other way that the path of the player two will coincide with any of the other cell in path one because he can go only right or up. So we are sure about the top path.

[00:09:50]So if the player came here then if he is taking upper path we are sure that once he crosses any shared cell then like crosses means he came till here and then if he cross this then there is no other way that it is coinciding with the path one. Now let's come to rightward again.

[00:10:06]Now the player two came here and then let's assume the player two took one right path. It means only one shared cell is there. Now the player one is here. Player two is here. Now let's assume the player one is taking up. So now he went to up. Now even now same because now he went to up right now he can go only up or only right. So even now there is no possibility ever that the player one path will coincide with player two path only this one is a shared cell. Now this is clear again.

[00:10:32]Now let's take two cells again. Now the player one is here. So we took one and then we took one. So there are two shared cells. Now now let's assume the player one is the player two is coming up. Now he came up even now there is no possibility that there are any future shared cells. So this is also done. So from this are we able to get anything?

[00:10:52]So we can come up to a very easy conclusion. The easy conclusion is the shared result will be only a horizontal horizontal path or a vertical path. Do you agree? Yes. Because so if the player so for example let's assume this is the player one path. Now so by somehow the player two came till here right? Let's assume the player two came till here somehow. We don't know the before path but from now let's assume. So the player came till here. So player two is it here. Now player two what all he can take? He can go only right or he can go only up.

[00:11:31][cough] So he can take only right or up right now they use it here. So if he try to go up. So he trying to go up and then he reached the cell. Now if he reached this cell he can try to go up or he can try to take right. Now let's assume he's taking top. So now if he's taking top then even now same there is no other way that there will be any shared cell. So the only shared cell is this single cell. No.

[00:12:01]So he came till here and then he tried to take this one. So he took this one and he took this one and now he came up.

[00:12:08]So even now there is no possibility of coordinating cell. So if you observe so only a contiguous block will be shared between those because once so for example this is the contiguous block. So if the player to try to take these consecutive shells sorry cells and then he can try to take right or he can go up. Now if he takes up then that's it.

[00:12:29]These are the only shared cells that he can get because once he crosses up then he will go only top but he cannot come to P1 again.

[00:12:36]And if we come side then it is simply a more horizontal row. So from this we are able to get to a conclusion that the shared cells are a contiguous block of horizontal elements or a contiguous block of vertical elements or a single cell as well because we we we checked here right for example if this is the something like this and then the player two came till here. Now he can take only top and then he can come to here and then he can take up. So a single cell is also possible like that is individually a subarray. So yeah let's check other conclusion. So from this we are able to easily extract that the answer the the shared cells will be some contiguous block of horizontal of any length or more than equal to one because we are able to see that we are able to get a single length also we can get to obviously we can get any number.

[00:13:26]So the number of shared cells will be contiguous block of horizontal cells or some contiguous block of vertical cells.

[00:13:34]Both can be of length one or many. So this is the first conclusion that we can come up to. Now now given a grid now given a grid and let's let's stick to a single row. Now let's take this row as our main reference. Now coming to this row let's broaden up this. So this is the single subarray that we're discussing about.

[00:13:55]Now given the subarray um how to find the maximum subarray length in this like so we know that this can be a part of our final answer because this is single cell. So there can be this can be only the single shared cell. So this cell can be our answer. This cell can be our answer. This this this or any contiguous sub subarrays of this also can be our answer. So maybe this three length subarray can be our maximum sum. For example, let's say this is - 1 - 2 3 1 2 - 3. Let's assume this is the subarray that we have. And coming to the subarray. So we know that any of this any of this subarray can be our answer.

[00:14:36]So only this can be our answer. Only this can be our answer because we we got that there can be any number of shared cells. But the only restriction is the shared cells should be horizontal or should be vertical. There cannot be something like these three are shared.

[00:14:49]No, this is not possible. We already discussed right? So that can be only sing that can be only horizontal or they can be only vertical. So let's assume that we are coming to the subarray. So in this subarray the answer can be any length subarray from this that can be a single subarray or this can be whole of this or this can be whole of this anything. The only restriction is it should be a horizontal subarray and that we are already taking care of. So in this how to find the maximum subarray length the brute force will be we will traverse through each and every subarray with the time complexity n square because every row every subarray the the number of subarrays will be n square. So for every subarray we will find the maximum we'll find the sum and then for every row and for every column we will try to find the maximum value of all so that it will give answer. But what is the time complexity of it? It will be we have to traverse the number of rows and total number of columns and for every each of this we have to loop n square again because for every row there will be n square subarrays and for every column there will be m square subarrays.

[00:15:48]So it will be n cube which is not possible because n cube will be around 10^ 15.

[00:15:54]So how to remove this now? So now our goal is let's stick with array like let's stick with the horizontal array.

[00:16:00]Now given this subarray how to find the maximum sum subarray in this that is what we want right. So this is one this is minus2 this is three this is minus one this is 7 this is zero this is minus 3.

[00:16:14]Now let's assume this is the subarray and our main goal is to find maximum sum subarray in this subarray in less than n square. It means indirectly in of because if we if we are able to find the answer in offend. So we can traverse through every row we can traverse every column and then for every of this we can try to use this of an algorithm to give the answer in n square which is the total number of cells which will be 10^ 6.

[00:16:44]So this is what we can do. So now our main goal is to given a subarray. We have to find the maximum sum subarray from all of these subarrays in of. So how to do that? Now let's take again let's try to take the same array again.

[00:16:58]Now let's say we are at this index. So we are at this index. So let's think ourself.

[00:17:05]Let's let's think ourself. We are at this element. So what is the maximum subarray length? Sorry. What is the maximum sum of subarray that we can get with subarray ending at this element? Let's try to figure out that first. So what firstly what are all the subarrays that are ending at this index? The first thing is this one. The second is two length subarray. The third is third length subarray. Fourth is fourth length. Five is fifth length. So these are the only five subarrays that are ending at this index.

[00:17:35]Now what is the maximum sum among all these subarrays? Again the brute force is traverse through each and every of this and find the answer. But this is not possible because this is indirectly brute force which will take off n square time. So for every cell for every of the sub array we can't loop through every of this and we can't find a sum. So how to find this smartly? Now if we observe if we observe then we can try to maintain maintain something for example let's assume what is the maximum subarray some ending at this index so we are fixing that there should be this element so so we consider this right it means we are considering this element as our final answer like we are now so what is the main goal the first main goal is to find the max array now we filtered that and we are assuming at this index the maximum sub subarray will be existing. So now that's why we took an index I and then we assumed that the maximum sub will end this index I and now after assuming this then we are finding how that will maximum like we are finding we are trying to find how to find the maximum sum ending at index a now how to do that now so v of i will always be there so this element is common now if you observe what is the next thing that we want this is indirectly equal to the v of i plus right because this element is fixed. So v of i plus what is the value that we can get?

[00:19:04]We want the maximum sum among all the subarrays. So from this we can easily see that the value is equal to simply V of I because this is common to each and every subarray plus plus max of all subarrays of all subarrays ending at IUS 1 like sum maximum sum of all subarrays ending at I minus one. Do you agree?

[00:19:30]Yes. Right. Because the sum of this like the maximum sum of this will be max of this comma max of this max of this max of this car max of this. And now we try to separate V of I because this is in every separate. So we try to bifurcate this. So the maximum sum of of all this will be equal to this element V of I plus max of max of all this because let's assume that the maximum subarray is 10 out of this. So if you have some information like this then the answer will be very easy. It will be the maximum answer till here plus this value right. This will be off one because at current subarray these are all like at this subarray these these five are the subarray ending at current value. Now this is equal to simply this value plus max of among all these indirectly. Right? So the maximum out of this let's assume that maximum out of these is three. It means the maximum sum till before index is three and hence we know what is the maximum sub length till three. So we know the maximum sub ending at three. Now we can try to find the answer at index i right because at i.

[00:20:43]So at i we can try to take this index or we can try to skip index. Now if we are trying to take this index. So if we are trying to take this index then what will be the maximum sum?

[00:20:56]It will be this value plus the maximum value of the before index answer like max of v of i minus one. Now if we are not taking this value then what?

[00:21:13]So you are able to understand right? So this is simply like a modification of dp. So given a vector at every index we will try to find what is the maximum subarray sum ending at this index. Now we if you are trying to find the answer for this then it will be easy to find the answer for next I + 1.

[00:21:30]So hope you got this till now. So till now what we reached we reached that the answer can be the answer can be of few horizontal cells or few vertical cells. Now is this always correct? Let's try to take the initial example again.

[00:21:46]Now let us take this one again. So, so what are all the cells? So we have 4 - 2 - 3 -1 3 - 1 - 4 2 - 1. So this is the grid. Right? Now as per our solution what should be the answer? It should be three because this is the maximum value that we can get.

[00:22:15]Right? Because we can take a single sub of this and then the answer will be four. But that is wrong because the answer is three. So what is the wrong?

[00:22:23]What was the wrong that we assumed?

[00:22:25]So we took a path, right? We took a path where the answer can be single cell. But here even now we are trying to take a single cell. But this is not the answer.

[00:22:33]Why this is not the answer? Now let's check more clearly. Now so let's assume that this is the only cell. Let's assume that this is the only cell that is shared. Is that possible ever? Is that possible? No. So for the player two, for player two when this will be only the when 0 comma 0 will be the only shared cell.

[00:22:58]So firstly the player two should reach this cell to make the shed. So the player two must come here like this only because he can come only right or up. So the player two must take here and must come here. So this is the exact path that he must take to reach 0 now and then he must come here. So this is the only path that is possible if we are assuming that the maximum the shared cell is only 0. Now player one is here right? Player one is here. Now player one is here. So what can be the path of player one to make sure that this is the only cell that is shared with P2. Now the player one must come down or must come right.

[00:23:37]Right. the player two, the player one must come right or must come down. But if we see then if the player is coming right, if the player is coming right then the shared cells will be these two.

[00:23:49]And similarly if the player one is taking down the shared cells will be these two.

[00:23:54]Oh. So now we are able to see that single 0 comma 0 will not be a shared cell ever. It will be shared with either continuous element. But why it is not true before like are you able to understand right? Because if this is the only share to sell that is not possible because player two must reach this and the player two can reach 0 only by taking this path and now the player one is here and how can this be only shared cell because player one must take right or must take ground. So the player two took this and this as well. So there is no combination such that this is the only cell that is shared among both.

[00:24:31]So our whole our whole solution is wrong. No, our whole is not wrong. So why this cell is not wrong? Like why the answer is not only this cell? That is the question for now.

[00:24:45]Now let's take this cell again. Let's take other cell. So now we got that this cell can never be existing. So So it means that there can be no single cell ever. No, that is also wrong. Now let's check this one. Let's check this cell to check if there can be a single this shared cell. Now the player two is here.

[00:25:04]So how can player two come here? He must take this path and then and then he must take this. He must take this because if he come here and then if he take here then this will be shared cell because this is the player one initial path. So the player one must take this path only. Now coming to player one. Now coming to player one. The player one came till here. Now he came to here. Now what is the path that he can follow? He can take right or he can go down. But even now this cannot be shared cell because this is also by P2. This is also traveled by V2. So this cannot be the single shared cell among these both because either these two or these two but single is not possible because this is also traversed by P2. This is also traversed by P2. So there cannot be only this shared cell. So this is also wrong.

[00:25:55]Now let's take any other cell.

[00:25:59]Now let's take this cell. Let's assume let's check to find if this can be our shared cell or not. So how to do that first.

[00:26:08]Now initially player two is here. So how can player two come till here? The player two can come up and then take this and then um and then take up and then like this and then like this. Now coming to no let's take a now let's come to let's assume that this cell so can we find a path with only this shared cell now he came here he came here he came here and then he came here and then he came here yeah now it is perfect now the player two came via this now player one can come he can come to this he can come to this he can come to this he can come to this he can come to this so if you're able to observe this is the only shared cell among these both so now this is possible because like if we are able to find a single cell then the player the player one can come to here and then the player two can come till here and then he can go like this and similarly player one can come till here and then he can take this and then he can Like swastik symbol right? Hope you do you know hope you know this. So if this is the single shared cell then this is possible like this like this like this like this like like this. So this is the only shared cell but why 0 and other cells failed because they are on the boundary. Why boundary is failing? The boundary is failing because if we are assuming this then the both players must come must use this only right because if that is boundary then he must come till here. He must come to layer and hence there will be at least one common cell other than this because he like if he comes down this will be shed. If he comes right and then if he comes this will be shared cell. So if only it is boundary then the both P1 here P2 here and then there will be at least one extra shared cell. But if that is in the middle then we can see something like this.

[00:28:20]If this is the cell he can come till here and then till here till here till here and generally P1 P2. So now what is our algorithm? Our algorithm is very simply we will find we will find the maximum length of we will try to find the maximum length of subarray of at least length two right at least length two because we don't want the boundary cells. So for example if you are taking the length one then what if this is the maximum cell that will be wrong answer.

[00:28:50]So firstly consider every length to subarray maximum subarray among all rows and columns and then take the maximum single value cell among the inner grid except the boundary. So if this is the boundary skip the last skip the boundary rows and columns. So skip this, skip this, skip this and then loop through the inner boundary inner 2D matrix and then find the maximum value in this and hence this will satisfy answer. So we are able to get all the horizontal and all the vertical and then single shared results which are not at the boundary. So let's check the code first. Now so I think you know this is very standard cadence algorithm which will give the maximum sum subarray. Now how to do the solution? Now let's start with this. So firstly loop through each and every column and then find the maximum length subarray sum in every column and similarly in every row. So loop through every row and then if there are less than two it means we can't find length two so break and then add like find the column vector in the column vector do the cence of this. So after doing this both we will get the maximum length like maximum sum with length at least two that will not suffice we want the single value in among the inner grid. So loop till the inner grid and then find the maximum single cell among all these. Now how to find kion it is very easy. So firstly so caden will be we want length at least two. So firstly initialize the answer with this two sum and then we can try to take or not take from the next index. So take a comma 0 + 1 and then let's assume best is equal to current till now and then loop till second index. So start from second index and then what are the choices we have? The choices we have is if we are taking the current index, right? If you're taking the current index then take the before index or take the maximum value the maximum sum we got till I minus one.

[00:30:51]So if we are at this index we are trying to add the before value or we are trying to get the maximum sum that we able to get till before value and hence the best will be simply the max of best comma current.

[00:31:05]So this can be solved in many other ways. So we can try to take a very 2D dp vector as well. DP of I comma 0 and then and DP of I comma 1. So DP of I comma 0 will return what is the maximum sum ending at index I without taking index I and DP of I comma 1 will give what is the maximum sum ending at index I by taking I. So having this information it is very easy to find answer. So this is also a way. So hope you know this. If you have any doubts comment below. See you in the next video.