Grid Game - Leetcode 2017 - Python

0:00 - Read the problem
1:40 - Drawing Explanation
9:13 - Coding Explanation

leetcode 2017

#neetcode #leetcode #python

[NeetCodeIO]

The reason the UI looks different is I solved this 3 years ago during a leetcode contest

[spitfire]

two prefix sums is overkill. here is my solution:
bot, top = 0, sum(grid[0]) - grid[0][0]
maxx = top
for i in range(1, len(grid[0])):
top -= grid[0][i]
bot += grid[1][i-1]
maxx = min(maxx, max(bot, top))
return maxx

[sivatejaysn]

Getting the intuition is one challenge and realizing it is not greedy is other thing I failed with greedy approach

[divyarajsinhrana]

Hey NeetCode, reallyy amazing explanation on this!
Although I understood, I just had one query that why will DP not work here?
My intuition was to take the max score achieved by robot 1 from right and down direction.
for(int i=(n-2);i>=0;i--)
{
temp[1][i] = grid[1][i] + temp[1][i+1];
temp[0][i] = grid[0][i] + max(temp[1][i], temp[0][i+1]);
}

Any responses are most welcome!

Keep it up <3

[Mahidhar-wp]

class Solution:
def gridGame(self, grid: List[List[int]]) -> int:

top_sum = sum(grid[0])
bottom_sum = 0
N = len(grid[0])
res = float("inf")
for i in range(N):
top_sum -= grid[0][i]
res = min(res, max(top_sum, bottom_sum))
bottom_sum += grid[1][i]
return res

[_chaitanyagadkari]

@12:16, the result is infinity, right? then, we're taking the minimum between them, right?

[myyfstz]

thanks champ, absolutely brilliant 🐻‍❄🐻‍❄🐻‍❄

[NeetCodeIO]

As some people already mentioned, there are other solutions to this problem as well that are covered above.

[MP-nyep]

Beautifully explained. Thank you for the daily.

[TheSmashten]

I've done almost 600 problems and this one stumped me.. Feeling dumb

[morrischung]

I find the maximum sum robot1 can get, I wipe all the cells on that path int the grid to 0.
I calculate the maximum sum robot2 can get within the modified grid.
I Run and get Accepted,
I Submit and get WA
And then I come here.

What a sad story.

[JamesBond-mqpd]

thank you. super clean explanation. i tried to solve it trough DFS. but was defeated

[yoganandareddy]

Is there any chance that we could do this problem by using any graph algorithm.

[shibambiswas]

The video is also looking like 2017 : -)

[dev_avi]

My approach was this:
first maximize the sum the first robot can make. and make those cells 0. after that return next max possible as answer.
it is giving wrong answer. can u guide please!?

[InquisitiveLittleSteps]

The total collection of robot 2 can NEVER be greater than that of robot 1. Is this correct??

[anonanon]

Why is the problem number on the screen 5882? Did leetcode got rid of a bunch of problems in those 3 years?

[akshatpandey]

shouldn’t we find postfix of first and prefix of second??

[OlinOlivieri]

The video content is worth seeing!There are some things I don't understand:I have a wallet address with usdt in it and I have a recovery phrase.:(laugh nominee buzz game expose field wash shoe world sadness bicycle grain).:How should I transfer them into my own wallet?

[DassVeryGood]

This is so weird… of course i was lost until i saw that this was a prefix sum situation and I knew i was done. I get what to do with a prefix sum and why you should use it, but i just get tripped up in the second loop im just lost