2017. Grid Game - Explanation

1. Brute Force

Intuition

Robot 1 must go right along row 0, drop down to row 1 at some column, then continue right. After Robot 1 collects its points (setting those cells to 0), Robot 2 follows optimally. Robot 1 wants to minimize Robot 2's maximum possible score. We try every possible column where Robot 1 drops down and simulate Robot 2's best response.

Algorithm

For each column i where Robot 1 drops down:
- Calculate the points Robot 1 collects along the top row until column i, then the bottom row from column i onward.
- Simulate Robot 2's optimal path through the remaining grid (top row after i, bottom row before i).
- Track Robot 2's maximum score for this configuration.
Return the minimum of Robot 2's maximum scores across all choices of i.

class Solution:
    def gridGame(self, grid: List[List[int]]) -> int:
        cols = len(grid[0])
        res = float('inf')

        top1 = 0
        for i in range(cols):
            top1 += grid[0][i]
            bottom1 = 0
            for j in range(i, cols):
                bottom1 += grid[1][j]

            top2 = robot2 = 0
            for j in range(cols):
                if j > i:
                    top2 += grid[0][j]

                bottom2 = 0
                for k in range(j, i):
                    bottom2 += grid[1][k]
                robot2 = max(robot2, top2 + bottom2)

            res = min(res, robot2)

        return res

Time & Space Complexity

Time complexity: $O(n ^ 3)$
Space complexity: $O(1)$

2. Prefix Sum

Intuition

After Robot 1 drops at column i, Robot 2 can only collect from two disjoint regions: the top row after column i, or the bottom row before column i. Robot 2 will choose whichever region has more points. Using prefix sums, we can compute these region totals in O(1) per column.

Algorithm

Build prefix sums for both rows.
For each column i where Robot 1 drops:
- top = preRow1[N-1] - preRow1[i] (sum of top row after column i).
- bottom = preRow2[i-1] if i > 0, else 0 (sum of bottom row before column i).
- Robot 2's score is max(top, bottom).
Return the minimum of these scores across all i.

class Solution:
    def gridGame(self, grid: List[List[int]]) -> int:
        N = len(grid[0])
        preRow1, preRow2 = grid[0].copy(), grid[1].copy()

        for i in range(1, N):
            preRow1[i] += preRow1[i - 1]
            preRow2[i] += preRow2[i - 1]

        res = float("inf")
        for i in range(N):
            top = preRow1[-1] - preRow1[i]
            bottom = preRow2[i - 1] if i > 0 else 0
            secondRobot = max(top, bottom)
            res = min(res, secondRobot)
        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

3. Prefix Sum (Space Optimized)

Intuition

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).

Algorithm

Initialize topSum as the sum of the entire top row, and bottomSum as 0.
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).
Return the minimum result.

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

Time & Space Complexity

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

Common Pitfalls

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.