Today’s problem

https://leetcode.com/problems/grid-game/description/

Intuition

This is a special case where there are only two rows. Moreover, it is also important to note that all number in the grid.

Since the robot cannot go back whenever we choose to go down, this means that for both robots, there is only one chance to go to the second row.

If robot one goes to the second row at index $k$, what will happen?

Now, in this case, the only numbers not 0 are the numbers that has index less than k in the second row and the numbers that has index more than k in the first row.

Therefore, to maximize the result for robot 2, it gets to choose to get the numbers in the first row or in the second row because it cannot get back to the first row when it choose to get to the second row.

Approach

Now, all we have to calculate is the sum of all the numbers after index k in the first row, and the sum of all the numbers before index k in the second row.

Trick

Now we have a trick of prefix sum to solve this problem.

  1. The sum of all numbers after index in the first row k can be calculated by the sum of all numbers after index k - 1, by subtracting $grid[k][0]$.
  2. The sum of all numbers before index in the second row k can be calculated by the sum of all numbers after index k - 1, by adding $grid[k][1]$.
  3. The required sum of the first row is always decreasing, while the required sum of the second row is always increasing.

Therefore, when $max(sum1, sum2) > presentAns$, we can break the loop as now sum2 > sum1 and will continue increase. Therefore, the answer will not decrease anymore. (Here sum1 means the required sum of row1, sum2 means the required sum of row2, and presentAns means the answer we get at present point when we iterate to index k).

Complexity

  • Time complexity: $O(N)$, N is the length of the gird.

  • Space complexity: $O(1)$, we only store a few variables.

Code

class Solution:
    def gridGame(self, grid: List[List[int]]) -> int:
        x,y = sum(grid[0][1:]), 0
        ans = x
        for i in range(1, len(grid[0])):
            x -= grid[0][i]
            y += grid[1][i - 1]

            if ans >= max(x,y):
                ans = max(x,y)
            else:
                return ans
        
        return ans

image.png