> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Grid Game Python Solution with Tests

> Tested Python solution for LeetCode 2017 with 18 pytest cases. Generate a practice environment with lcpy.

LeetCode 2017, [Medium](/catalog/medium). Topics: [Array](/catalog/topics/array), [Matrix](/catalog/topics/matrix), [Prefix Sum](/catalog/topics/prefix-sum). [View on LeetCode](https://leetcode.com/problems/grid-game/description/).

Generate this problem as a practice environment: tested reference solution, 18 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 2017   # by problem number
lcpy gen -s grid_game   # by problem name
```

## Problem

You are given a \<strong>0-indexed\</strong> 2D array \<code>grid\</code> of size \<code>2 x n\</code>, where \<code>grid\[r]\[c]\</code> represents the number of points at position \<code>(r, c)\</code> on the matrix. Two robots are playing a game on this matrix.

Both robots initially start at \<code>(0, 0)\</code> and want to reach \<code>(1, n-1)\</code>. Each robot may only move to the \<strong>right\</strong> (\<code>(r, c)\</code> to \<code>(r, c + 1)\</code>) or \<strong>down\</strong> (\<code>(r, c)\</code> to \<code>(r + 1, c)\</code>).

At the start of the game, the \<strong>first\</strong> robot moves from \<code>(0, 0)\</code> to \<code>(1, n-1)\</code>, collecting all the points from the cells on its path. For all cells \<code>(r, c)\</code> traversed on the path, \<code>grid\[r]\[c]\</code> is set to \<code>0\</code>. Then, the \<strong>second\</strong> robot moves from \<code>(0, 0)\</code> to \<code>(1, n-1)\</code>, collecting the points on its path. Note that their paths may intersect with one another.

The \<strong>first\</strong> robot wants to \<strong>minimize\</strong> the number of points collected by the \<strong>second\</strong> robot. In contrast, the \<strong>second\</strong> robot wants to \<strong>maximize\</strong> the number of points it collects. If both robots play \<strong>optimally\</strong>, return the \<em>number of points\</em> collected by the \<strong>second\</strong> robot.

### Examples

![Example 1](https://assets.leetcode.com/uploads/2021/09/08/a1.png)

```
Input: grid = [[2,5,4],[1,5,1]]
Output: 4
Explanation: The optimal path taken by the first robot is shown in red, and the optimal path taken by the second robot is shown in blue.
The cells visited by the first robot are set to 0.
The second robot will collect 0 + 0 + 4 + 0 = 4 points.
```

![Example 2](https://assets.leetcode.com/uploads/2021/09/08/a2.png)

```
Input: grid = [[3,3,1],[8,5,2]]
Output: 4
Explanation: The optimal path taken by the first robot is shown in red, and the optimal path taken by the second robot is shown in blue.
The cells visited by the first robot are set to 0.
The second robot will collect 0 + 3 + 1 + 0 = 4 points.
```

![Example 3](https://assets.leetcode.com/uploads/2021/09/08/a3.png)

```
Input: grid = [[1,3,1,15],[1,3,3,1]]
Output: 7
Explanation: The optimal path taken by the first robot is shown in red, and the optimal path taken by the second robot is shown in blue.
The cells visited by the first robot are set to 0.
The second robot will collect 0 + 1 + 3 + 3 + 0 = 7 points.
```

### Constraints

* grid.length == 2
* n == grid\[r].length
* 1 \<= n \<= 5 \* 10^4
* 1 \<= grid\[r]\[c] \<= 10^5

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/grid_game/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/grid_game/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(n)
    # Space: O(1)
    def grid_game(self, grid: list[list[int]]) -> int:
        top = sum(grid[0])
        bottom = 0
        best = None
        for t, b in zip(grid[0], grid[1], strict=True):
            top -= t
            second = max(top, bottom)
            if best is None or second < best:
                best = second
            bottom += b
        return best if best is not None else 0
```

## Complexity

| Time | Space |
| - | - |
| O(n) | O(1) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.