TC: O(n)
SC: O(n)
class Solution { public long gridGame(int[][] grid) { long prefix1[] = new long[grid[0].length]; long prefix2[] = new long[grid[0].length]; long sum =0; for(int i=0;i<grid[0].length;i++){ sum+=grid[0][i]; prefix1[i]= sum; } sum =0; for(int i=0;i<grid[0].length;i++){ sum+=grid[1][i]; prefix2[i]= sum; } long res = Long.MAX_VALUE; for(int i=0;i<grid[0].length;i++){ //if robot 1 at 2 cross at index i //in this row if the robot 1 and 2 cross then robot 2 will get all the values after the from index i to n-1 th index (in top row) //or values till i from the start 0 to i in the bottom row, as once in bottom row robot 2 can not move up long top = prefix1[grid[0].length-1] - prefix1[i]; long bottom = i>0 ? prefix2[i-1] : 0; long max = Math.max(top,bottom);// robot 2 will try to maximize the values it collects res = Math.min(res,max); //robot 1 will try to minimize the value robot 2 collects } return res; } }
Top comments (0)