2017. Grid Game | Prefix & Suffix Sums

[@rsKayiira]

Excellent solution and explanation I was quite confused by this.

[@mukulkhanna5071]

Aryan bhai you r a genius hence proved today i was actually this problem's solution from last year but didn't get a single video that explained in such great depth i just watched half of your video directly wrote the solution in 4 minutes thanks a lot bro for your efforts

[@indianengineer5802]

Hey Aryan, please avoid writing topics names or hints in daily question solution. It gives me unnecessary hint while I am not solving problem currently. Please just keep the problem name for daily problem solutions, just like codeStoryWithMIK

[@ramukaka108]

Yes, when the video comes in recommendation and I don't want to see solution it gives hint to me, although I don't want it. Please don't put topic name or hint in thumbnail or description.

[@nikhilneela]

yes, my feed shows the thumbnail which reveals the topic and I can't think beyond. Please sincere request

[@sauravchaudhary4211]

agreed

[@ARYANMITTAL]

My Uber Interview Experience - ua-cam.com/video/VGYJIX5yl74/v-deo.html
My Coinbase Interview Experience - ua-cam.com/video/IjOC18b_dCw/v-deo.html
My American Express Inteview Experience - ua-cam.com/video/c3UhYefhnqk/v-deo.html
My JP Morgan & Chase Interview Experience - ua-cam.com/video/-jacTpY57no/v-deo.html
..... more coming soon (along with LLD course on Second Channel)

[@growmoreyt4192]

I though of apply backtracking and getting the maximum point from any path and if through any way i could be able to make them 0 then i supposed that answer could come but i was wrong.

[@rachitthakur9454]

Bhaiya any tips for 3rd year cse for placement please what they ask in interview for freshers like me

[@dxcfvg456hkjtyujk]

also add
if(preSumUp < preSumDown){
break;
}
in the for loop as it will have less complexity.

[@godFather-123-b8g]

bhai kya race lagi h sab logi hi itna jaldi sol dall rhe h kiska dekhu lol

[@alfykerolous1869]

i have run dp maximum path sum 2 times first one get path and make the all cells in that grid is 0s and then max path again to get the maximum the second get but it failed in some test cases. why is that ?

[@KnowledgeIsDivine404]

Understand that first robot wants to minimize second robot's points not maximize it's own points

[@staywithmeforever]

[[1,2,31],[32,44,45]]
The max for robot 2 is 32 not 33.
The optimal path for robo1 is 1,2,44,45

[@alfykerolous1869]

@ thx man i got u

[@kgjr.6224]

why the dfs approach is not working ?
class Solution {
long max = -1;
List fp = new ArrayList();
void dfs(int r, int c, int[][] grid, long sum, List path) {
if (r == grid.length - 1 && c == grid[0].length - 1) {
if (max < sum) {
max = sum;
fp = new ArrayList(path);
}
return;
}
// Move forward
if (c + 1 < grid[0].length) {
path.add(new int[]{r, c + 1});
dfs(r, c + 1, grid, sum + grid[r][c + 1], path);
path.remove(path.size() - 1);
}
// Move down
if (r + 1 < grid.length) {
path.add(new int[]{r + 1, c});
dfs(r + 1, c, grid, sum + grid[r + 1][c], path);
path.remove(path.size() - 1);
}
}
void dfs2(int r, int c, int[][] grid, long sum) {
if (r == grid.length - 1 && c == grid[0].length - 1) {
if (max < sum) {
max = sum;
}
return;
}
// Move forward
if (c + 1 < grid[0].length) {
dfs2(r, c + 1, grid, sum + grid[r][c + 1]);
}
// Move down
if (r + 1 < grid.length) {
dfs2(r + 1, c, grid, sum + grid[r + 1][c]);
}
}
public long gridGame(int[][] grid) {
List path = new ArrayList();
path.add(new int[]{0, 0});
dfs(0, 0, grid, grid[0][0], path);
for (int[] ele : fp) {
grid[ele[0]][ele[1]] = 0;
}
max = -1;
dfs2(0, 0, grid, grid[0][0]);
return max;
}
}

[@Engineering.Wallah]

class Solution {
public:
long long gridGame(vector& grid) {
int m=grid.size(),n=grid[0].size();
long long first=0;
for(int j=0;j=temp){
j++;
first-=grid[i][j];
}
else{
temp-=grid[i+1][j];
break;
}
}
return max(first,temp);
}
};
Intuitive❤

[@helloim7705]

why my answer is wrong:
class Solution:
def gridGame(self, grid: List[List[int]]) -> int:
i=0
j=0
m=2
n=len(grid[0])
arr=[[0 for p in range(n)] for i in range(2)]
arr[0][0]=grid[0][0]
for i in range(m):
for j in range(n):
if(i==0 and j>0):
arr[i][j]=grid[i][j]+arr[i][j-1]
if(i==1):
if(j==0):
arr[i][j]=grid[i][j]+arr[i-1][j]
else:
arr[i][j]=max(grid[i][j]+arr[i-1][j],grid[i][j]+arr[i][j-1])
for i in range(m):
print(arr[i])
i=m-1
j=n-1
while i>=0 and j>=0:
arr[i][j]=0
if(i>0 and j>0 and arr[i][j-1]>arr[i-1][j]):
j-=1
elif(i==0):
j-=1
else:
i-=1
sum=0
i=m-1
j=n-1
while i>=0 and j>=0:
sum+=grid[i][j] if arr[i][j]!=0 else 0
if(i>0 and j>0 and arr[i][j-1]>arr[i-1][j]):
j-=1
elif(i==0):
j-=1
else:
i-=1
for i in range(m):
print(arr[i])

return sum