Grid Game | Detailed Explanation | Complete Ry Run | Leetcode 2017 | codestorywithMIK

[@codestorywithMIK]

If you are wondering why maximising Robot-1’s points doesn’t ultimately give the least score for Robot-2 : Let’s take this example, if grid = [[2, 4, 6], [8, 9, 10]], the first robot could take the path 2 -> 8 -> 9 -> 10 to maximize its points, leaving 4 and 6 for the second robot. But the better strategy is for the first robot to turn down at index 1, leaving either 6 or 8 for the second robot, which would then get max(6, 8) = 8 points instead of 10. You can clearly see that here the point of Robot2 is prioritised instead of maximising the points of Robot1

[@Letstudy-p7y]

yes now i got it. i was trying to solve this problem by maximising the robot1 points and got wrong asnwer. Now i clearly understand . Thankyou for your awesome explanation and test case.

[@shreysaxena738]

Thank you, this is the explanation was looking for.

[@chinmaygupta2277]

amazing explanation bhaiya !! wait for leetcode contest solutions 🤞🏻🤞🏻

[@bhuppidhamii]

no way, that I could come up with this solution, I was thinink of dp.

[@Zoro_tao]

I tried solving with dp as well but failed Did you find out how it cannot be solved by dp?

[@bhuppidhamii]

@Zoro_tao no

[@entertainmentWithCoder]

great explaination

[@RajManish-b8m]

itne easy way me samjh Aaaa gya

[@cse080chandrasekhar9]

i feel that its nice problem we cant say hard and cant say medium ,but its the defination of problem!

[@nishantdehariya5769]

nice soln, but I think this problem should be marked hard as its really difficult to get into the intuition of moving around dfs, bfs, greedy and finally concluding prefix sum and solving it in 40 mins

[@krishna-kaushall]

all my college friends are like robot1.💀

[@unknown__899]

😢Same

[@pickled8262]

🤣

[@rahulsihara8946]

i did DP approach as that was most intuitive, this problem seems a specific case where row count is 2. If its not, then i assume DP is only way to solve it in exponential time. I got TLE with my DP solution.

[@aizad786iqbal]

one doubt, why robot 1 taking max for himself will not result in min for robot 2, ideally same hi baat hui na ? can you give any example ? jisme robot 1 max take kare but robot2 ko min points na mile..

[@codestorywithMIK]

Glad someone asked. Let’s take this example, if grid = [[2, 4, 6], [8, 9, 10]], the first robot could take the path 2 -> 8 -> 9 -> 10 to maximize its points, leaving 4 and 6 for the second robot. But the better strategy is for the first robot to turn down at index 1, leaving either 6 or 8 for the second robot, which would then get max(6, 8) = 8 points instead of 10. You can clearly see that here the point of Robot2 is prioritised instead of maximising the points of Robot1

[@sahilgupta-dv9zb]

agr robot1 max take krega .. toh i think jo points bche hua h unme se hee robot 2 ko max lene honge ... this is what i think

[@VikasMishra-q9w]

Hi Mik, Thanks for explaining it. I have a small doubt here. When we approach this problem and it tell us that we want to go either in right or bottom, the first thing came to my mind was recursion. What I implemented is recursively iterate all the possible path for the first robo and keep track of the maximum sum and its path. Once you have the path, set all the indexes of the path to 0 and implement the same logic for second robo and you will get the pathSum for the second Robo. NOTE: MY CODE IS NOT ABLE TO PASS ALL THE TESTCASE EXCEPT THE ONE MENTIONED IN THE EXAMPLE. I would love to know your point on this, why its not working. Here is my submitted code class Solution { int[][] directions = {{1, 0}, {0, 1}}; long roboSum; List roboPath; public long gridGame(int[][] grid) { roboPath = new ArrayList(); // check path for first robo solve(grid, 0, 0, new ArrayList(), 0); // mark the first robo path to 0; for (int[] location : roboPath) grid[location[0]][location[1]] = 0; // resetting sum roboSum = 0; // check path for second robo solve(grid, 0, 0, new ArrayList(), 0); return roboSum; } public void solve(int[][] grid, int row, int col, List path, long pathSum) { int m = grid.length; int n = grid[0].length; // out of index if (row >= m || col >= n) return; // update path and sum pathSum += grid[row][col]; path.add(new int[]{row, col}); // target cell if (row == m - 1 && col == n - 1) { if (pathSum > roboSum) { roboSum = pathSum; roboPath = new ArrayList(path); } path.remove(path.size() - 1); pathSum -= grid[row][col]; return; } for (int[] dir : directions) { int newRow = row + dir[0]; int newCol = col + dir[1]; solve(grid, newRow, newCol, path, pathSum); } path.remove(path.size() - 1); pathSum -= grid[row][col]; } }

[@EkanshVerma-dg1jq]

This approach won't work maximizing robot 1 path sum will not minimize robot2 path sum try this example [5, 12, 14], [20, 7, 17]

[@amanpatel8575]

Hint + Quote: There is difference between maximizing one's gain and minimizing other's gains. Iykyk.

[@Afif-d7n]

bhai can u kindly make a separate playlist solving the porblems at neetcode150?? most of them are already done by u but some r left so it'd be great for us if u could make a separate playlist containing only neetcode150

[@janaSdj]

Thanks...

[@utkarshsinghchouhan8819]

Motivation : "किस्मत के भरोसे रहने वालों को वो हर चीज़ मिलती है, जो मेहनत करने वाले थूक जाते हैं।"

[@shaundabre5552]

Pressure make Diamond, Simple as that

[@Amanbiragi17]

Motivation for Tomorrow -- "Perfection will come, through Practice".

[@navamsharma1888]

First time I got confused from your video.

[@codestorywithMIK]

Let’s get it. What part was confusing ? Kindly let me know, i will try to explain ❤️🙏

[@souravRawat-mr7zk]

my noob arse was thinking of using BFS, like maximizing the robot1 points and then making the path cost 0, and then again BFS the robot2 for his maximum path.... hth anyone could come up with the solution like this...

[@hemantvishwakarma8751]

Java code:- class Solution { public long gridGame(int[][] grid) { int m=grid[0].length; long min = Long.MAX_VALUE; long firstRowScore = 0; for(int num:grid[0]){ firstRowScore+=num; } long secondRowScore = 0; for(int i=0;i0) secondRowScore+=grid[1][i-1]; long r2MaxScore = Math.max(firstRowScore,secondRowScore); min=Math.min(min,r2MaxScore); } return min; } }

[@gauravmundhada1647]

No way i would have thought of prefix sum

[@viratkohli4863]

JAVA CODE ---> class Solution { public long gridGame(int[][] grid) { long firstrow=0; long secondrow=0; for(int i=0;i

[@YT_LUCKY-444]

I think about a dp solution but that not work How prefix sum approach get correct I don't think about prefix sum method 😢😢😢

[@_Aryan_Chandel]

Bhaiya dsa ka course laao na

[@indianengineer5802]

What is wrong in this solution ? I just found the turningPoint of prefixSum and does calculation accordingly. What is wrong with logic? class Solution { public long gridGame(int[][] grid) { int n = grid[0].length; int[][] prefix = new int[2][n]; prefix[0][n - 1] = grid[0][n - 1]; prefix[1][n - 1] = grid[1][n - 1]; for (int i = n - 2; i >= 0; i--) { prefix[0][i] = grid[0][i] + prefix[0][i + 1]; prefix[1][i] = grid[1][i] + prefix[1][i + 1]; } int turningPoint = -1; for (int i = 0; i < n; i++) { long top = i + 1 < n ? prefix[0][i + 1] : 0; // Remaining sum in the top row after the turning point long bottom = i > 0 ? prefix[1][i - 1] : 0; // Sum in the bottom row before the turning point if (top < bottom) { turningPoint = i; break; } } // Handle turning points if (turningPoint == -1) { long sum = 0; for (int i = 0; i < n - 1; i++) { sum += grid[1][i]; } return sum; } else if (turningPoint == 0) { long sum = 0; for (int i = 1; i < n; i++) { sum += grid[0][i]; } return sum; } else { long leftHalf = 0; long rightHalf = 0; for (int i = 0; i < turningPoint; i++) leftHalf += grid[1][i]; for (int i = turningPoint + 1; i < n; i++) rightHalf += grid[0][i]; return Math.max(leftHalf, rightHalf); } } }

[@Mahidhar-w8p]

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

[@lavisharma3603]

🎉🎉🎉🎉

[@madmaxgaming5864]

Bhai Maine toh DP soncha tha, i could not come with this solution.

[@himanshuyadav0600]

same

[@Anime-ub7vs]

i was thinking dp