Grid Game

How it works

We can avoid storing prefix arrays by maintaining running sums. Start with topSum as the total of the top row and bottomSum as 0. As we iterate, subtract from topSum (simulating Robot 1 taking cells from the top) and add to bottomSum (accumulating what Robot 2 could take from below).

Steps

1. Initialize topSum as the sum of the entire top row, and bottomSum as 0.
2. For each column i:
   • Subtract grid[0][i] from topSum (Robot 1 takes this cell).
   • Compute Robot 2's best score as max(topSum, bottomSum).
   • Update the result with the minimum seen so far.
   • Add grid[1][i] to bottomSum (this cell is now unavailable to Robot 2).
3. Return the minimum result.

Complexity

• Time complexity: O(n)
• Space complexity: O(1)

Things to watch for

Trying to Maximize Robot 1's Score

A common misunderstanding is thinking Robot 1 should maximize its own score. The problem asks to minimize the score of Robot 2, which is a different objective. Robot 1 must strategically choose where to drop down to leave the least valuable remaining cells for Robot 2, not just greedily collect the most points.

Missing That Robot 2 Has Only Two Disjoint Choices

After Robot 1 drops at column i, Robot 2 can only collect from either the top row after column i OR the bottom row before column i, never both. These regions are mutually exclusive because Robot 2 cannot move left. Failing to recognize this leads to overcounting what Robot 2 can collect.

Integer Overflow with Large Grid Values

The grid values can be up to 10^5 and the grid can have up to 5 * 10^4 columns. The sum of all values can exceed the 32-bit integer limit. Use long or 64-bit integers for the prefix sums and running totals to avoid overflow errors that produce incorrect results.

from typing import List

class Solution:
    def gridGame(self, grid: List[List[int]]) -> int:
        res = float("inf")
        topSum = sum(grid[0])
        bottomSum = 0

        for i in range(len(grid[0])):
            topSum -= grid[0][i]
            res = min(res, max(topSum, bottomSum))
            bottomSum += grid[1][i]

        return res

class Solution {
public:
    long long gridGame(vector<vector<int>>& grid) {
        long long res = LLONG_MAX;
        long long topSum = accumulate(grid[0].begin(), grid[0].end(), 0LL);
        long long bottomSum = 0;

        for (int i = 0; i < grid[0].size(); i++) {
            topSum -= grid[0][i];
            res = min(res, max(topSum, bottomSum));
            bottomSum += grid[1][i];
        }

        return res;
    }
};