Today’s Problem

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

Solution Approach

This is a special case — the grid has only two rows.
Additionally, we need to consider the properties of all numbers in the grid.

Since the robots cannot turn around once they move downward, each robot has only one chance to switch to the second row.

What happens if Robot 1 switches to the second row at index $k$?

At this point, only two non-zero numbers remain: those in the second row with an index less than $k$, and those in the first row with an index greater than $k$.

Therefore, Robot 2 can only choose one option to maximize its score: either take the remaining numbers in the first row or the remaining numbers in the second row — because once it switches to the second row, it cannot return to the first row.

Solution

We need to compute the sum of all numbers after index $k$ in the first row and the sum of all numbers before index $k$ in the second row.

Technique

A prefix sum technique is used to solve this problem:

  1. The sum of numbers after index $k$ in the first row can be obtained by subtracting $grid[k][0]$ from the previous sum (after index $k-1$).
  2. The sum of numbers before index $k$ in the second row can be obtained by adding $grid[k][1]$ to the previous sum.
  3. The cumulative sum required for the first row always decreases, while that for the second row always increases.

Thus, when $max(sum1, sum2) > presentAns$, we can directly exit the loop — at this point, since sum2 > sum1 and continues to increase, the answer will not decrease anymore. (Here, sum1 is the current candidate sum for the first row, sum2 is the current candidate sum for the second row, and presentAns is the current optimal answer when iterating to index $k$.)

Complexity

  • Time complexity: $O(N)$, where N is the number of columns in the grid.

  • Space complexity: $O(1)$, using only a constant number of 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