Grid Game - Leetcode Weekly Contest Problem 2017 - Python
Vložit
- čas přidán 24. 07. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 CODING SOLUTIONS: • Coding Interview Solut...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
🌲 TREE PLAYLIST: • Invert Binary Tree - D...
💡 GRAPH PLAYLIST: • Course Schedule - Grap...
💡 BACKTRACKING PLAYLIST: • Word Search - Backtrac...
💡 LINKED LIST PLAYLIST: • Reverse Linked List - ...
💡 BINARY SEARCH PLAYLIST: • Binary Search
📚 STACK PLAYLIST: • Stack Problems
Problem Link: leetcode.com/problems/grid-game/
0:00 - Read the problem
1:40 - Drawing Explanation
9:13 - Coding Explanation
leetcode weekly contest problem 2017
#coding #interview #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission. - Věda a technologie
For those who like me thought oh this is a repeat DP problem i.e. I use DP to find the path maximizing robot 1's score and then use DP to help find robot 2's maximum score path. Then I'm done. Well not exactly... I found a comment on LC why this approach fails spectacularly that I'd like to share here:
Can consider this testcase:
10 50 50 30
50 50 10 10
If you find the maximum path for Robot 1 and set those cells into 0, then the path became:
00 00 00 00
50 50 10 00
The Robot 2 can get a maximum of 110 points
But if Robot 1 goes by:
00 00 50 30
50 00 00 00
Then Robot 2 can get a maximum of 80 points.
this observation marks that minimum robot2 score is not dependent upon what score robot1 makes (can be either max or min or mid).
How about we traverse all possible paths from robot1 and then at end of each path we find score of robot2 using maxpath DFS technique and record it.
But it's exponentially increasing the Time complexity. I tried it but failed.
Can we somehow improve this recursive approach?
Thank you for the edge case. Now I'm really glad that I didn't go ahead and code it up this way
This was a very interesting problem, and it took me about 40 minutes to solve it by myself. Just like you, I also initially thought about just letting bot 1 greedily get the best score, and then let bot 2 greedily get the best score. The important realisation is that maximising own score ≠ minimising the other's score in this case. However, that would work if the grid were nxn.
I'm not sure if I'd be able to figure this out in an interview setting.
yeah that gave initial strategy seems correct at first but let to wrong answer
Why does the greedy approach work on nxn and not on 2xn? Is there any proof/intuition behind this?
can u prove that it will work for nxn ?
greedy approach will only work if u remove the constraint where robots cannot go up(ithink
@@mukeshchugani8582 I think it won't work on n*n. That's nonsense.
Lol I was trying BFS DFS 😅🤣🤣.
So was I bro
you can do it in O(n) time and O(1) memory like this. No need for the prefix sums and extra for loop.
top = 0
bottom = sum(grid[1])-grid[1][-1]
res = float('inf')
for i in range(len(grid[0])):
res = min(max(top,bottom),res)
bottom -= grid[1][len(grid[0])-i-2]
top += grid[0][len(grid[0])-i-1]
return res
Since you used copies of the grid for the prefix lists, you can simply code your last for loop as: result = min(result, max(prefix1[-1] - prefix1[i], prefix2[i] - grid[1][i])) this takes care when the index i = 0
thanks neetcode, your approach is genius!
man please make all contest question solutions you are really good at this u will surely get many views
absolutely superb explanation ,good job keep doing🎈🎈🎈
Thanks for this beautiful explanation !
I guess I would've never come up with this approach where you start figuring out the points for the second robot. Is part of game theory? Or just a makeshift greedy algorithm?
I did the exactly same approch... and it took me approx 1 hour ... I came here because people solve this problem by other approche too ...
The corner case(for second robot) is what , even I forgot to in to account
nice explanation
No need to store preRow1, preRow2 lists.
You can instead calculate the values directly inside the loop. For row 0, just keep adding the values, for row 1, sum the row first then keep decrementing values from it.
The first approach of greedy obviously fails. But does it have a proof of why it fails, as at the first look this is the first approach I would think of.
Hey, It was a tricky question. I was wondering, why this solution is incorrect:
e.g., grid = [[20,3,20,17,2,12,15,17,4,15],[20,10,13,14,15,5,2,3,14,3]]
Output = 96
Expected = 63
I'm trying to approach it in something like the "largest increasing subsequence" problem.
```
from pprint import pprint
class Solution:
def gridGame(self, grid: List[List[int]]) -> int:
N = len(grid[0])
def util():
dp = [[0] * N for _ in range(2)]
for i in range(2):
for j in range(N):
if i == 0:
if j == 0:
dp[i][j] = grid[i][j]
else:
dp[i][j] = grid[i][j] + dp[i][j-1]
else:
if j == 0:
dp[i][j] = grid[i][j] + dp[i-1][j]
else:
dp[i][j] = grid[i][j] + max(dp[i-1][j], dp[i][j-1])
# pprint(dp)
return dp
def traverse():
r, c = 1, N-1
path = []
while r >= 0 and c >= 0:
path.append((r, c))
if r > 0 and (dp[r-1][c] >= dp[r][c-1] or c == 0):
r -= 1
else:
c -= 1
# print(path)
return path
dp = util()
path = traverse()
for r, c in path:
grid[r][c] = 0
# pprint(grid)
dp = util()
ans = dp[-1][-1]
return ans
```
I tried the same approach and the same test case got failed with the same answer you got. The reason it fails is because we are focusing on maximizing the sum of robot 1 in a hope that, doing so will actually minimize the sum of robot 2, which is greedy method. But greedy method doesn't work for this problem.
Take a look at this video where he explains why greedy method fails. czcams.com/video/Ho3ZDKK3UYE/video.html
Thanks bruh
Thanks Alot
Great intution...
bring vdo on q3 crossword also
you're a beast
woah ... amazing.
was thinking about using dijkstra along with a max heap…
Me too
@@aritralahiri8321 That would basically be like DP twice, which anyways fails
Request: Solve Squid Game. 🦑
Dope
Java Solution:
class Solution {
public long gridGame(int[][] grid) {
int c=grid[0].length;
long [] prefixsum_r1 = new long[c];long [] prefixsum_r2 = new long[c];
prefixsum_r1[0]=grid[0][0];prefixsum_r2[0]=grid[1][0];
for(int i=1;i
Solution in Java
public long gridGame(int[][] grid) {
int [] t=Arrays.copyOf(grid[0],grid[0].length);
int [] b=Arrays.copyOf(grid[1],grid[1].length);
long [] top=Arrays.stream(t)
.mapToLong((i) -> (long) i)
.toArray();
long [] bottom=Arrays.stream(b)
.mapToLong((i) -> (long) i)
.toArray();
long upSum=0l;
long downSum=0l;
long result=Long.MAX_VALUE;
for(int i=1;i
i think 1st robot is mean