# Grid Game
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/grid-game)
Canonical: https://scaleengineer.com/dsa/problems/grid-game
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array, Matrix
---
## Problem
You are given a **0-indexed** 2D array `grid` of size `2 x n`, where `grid[r][c]` represents the number of points at position `(r, c)` on the matrix. Two robots are playing a game on this matrix.

Both robots initially start at `(0, 0)` and want to reach `(1, n-1)`. Each robot may only move to the **right** (`(r, c)` to `(r, c + 1)`) or **down** (`(r, c)` to `(r + 1, c)`).

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

The **first** robot wants to **minimize** the number of points collected by the **second** robot. In contrast, the **second** robot wants to **maximize** the number of points it collects. If both robots play **optimally**, return _the **number of points** collected by the **second** robot._

**Example 1:**

![](https://assets.glich.co/dsa/grid-game/image0.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.glich.co/dsa/grid-game/image1.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.glich.co/dsa/grid-game/image2.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 * 104`
* `1 <= grid[r][c] <= 105`

# Approaches
## Brute Force Simulation
This approach directly simulates the game based on our understanding of the optimal strategies. The first robot can choose `n` different paths, each defined by the column `i` where it moves from the top row to the bottom row. For each of these `n` choices, we calculate the maximum score the second robot can achieve and then find the minimum among these scores.
**Time:** O(n^2), where n is the number of columns. The outer loop runs `n` times. Inside the loop, we have two more loops to calculate the sums, each taking up to O(n) time. · **Space:** O(1), as we only use a few variables to store the sums and the result, regardless of the input size.
**Pros:** Simple to understand and implement directly from the problem's logic.; It correctly models the game's minimax nature.
**Cons:** This approach is inefficient due to the nested loops, leading to a quadratic time complexity.; For the given constraints (n up to 5 * 10^4), this solution will be too slow and result in a 'Time Limit Exceeded' error on most platforms.
### Explanation
The core idea is to iterate through every possible path for the first robot. A path is uniquely determined by the column `i` (from `0` to `n-1`) where the robot switches from row 0 to row 1.

For a fixed `i`, the first robot clears the path `(0,0) -> ... -> (0,i) -> (1,i) -> ... -> (1,n-1)`. After this, the grid is effectively split into two sections of available points for the second robot:
1.  The points in the top row to the right of column `i`: `grid[0][i+1]` to `grid[0][n-1]`.
2.  The points in the bottom row to the left of column `i`: `grid[1][0]` to `grid[1][i-1]`.

The second robot, to maximize its score, will choose a path that collects all points from one of these two sections. Its score will be the maximum of the sum of points in these two sections.

We can iterate through each possible `i` from `0` to `n-1`. In each iteration, we calculate the sum of the top-right part and the bottom-left part. We take the maximum of these two sums, which is the score the second robot gets for this `i`. We keep track of the minimum of these maximum scores over all `i`. This minimum value is the answer, as the first robot will choose the `i` that leads to this outcome.

```java
class Solution {
    public long gridGame(int[][] grid) {
        int n = grid[0].length;
        long minMaxScore = Long.MAX_VALUE;

        for (int i = 0; i < n; i++) {
            // Simulate Robot 1's path switching at column i
            
            // Calculate score for Robot 2's top path option
            long topPathScore = 0;
            for (int j = i + 1; j < n; j++) {
                topPathScore += grid[0][j];
            }

            // Calculate score for Robot 2's bottom path option
            long bottomPathScore = 0;
            for (int j = 0; j < i; j++) {
                bottomPathScore += grid[1][j];
            }

            // Robot 2 chooses the path with the maximum score
            long secondRobotScore = Math.max(topPathScore, bottomPathScore);

            // Robot 1 chooses i to minimize Robot 2's score
            minMaxScore = Math.min(minMaxScore, secondRobotScore);
        }

        return minMaxScore;
    }
}
```
### Algorithm
*   Initialize `minResult` to a very large number (e.g., `Long.MAX_VALUE`).
*   Iterate `i` from `0` to `n-1`, where `n` is the number of columns. This `i` represents the column where the first robot switches from the top row to the bottom row.
*   Inside the loop, for each `i`:
    *   Initialize `topSum = 0` and `bottomSum = 0`.
    *   Calculate `topSum` by iterating from `j = i + 1` to `n-1` and summing up `grid[0][j]`.
    *   Calculate `bottomSum` by iterating from `j = 0` to `i-1` and summing up `grid[1][j]`.
    *   The second robot will choose the path that yields the maximum score, which is `max(topSum, bottomSum)`.
    *   The first robot wants to minimize this score, so we update our overall result: `minResult = min(minResult, max(topSum, bottomSum))`.
*   After the loop finishes, `minResult` will hold the score of the second robot when both play optimally. Return `minResult`.

## Using Prefix Sums
The brute-force approach is slow because we repeatedly calculate sums over subarrays. This can be optimized by pre-calculating prefix sums for both rows. With prefix sums, we can find the sum of any subarray in O(1) time, which reduces the overall time complexity significantly.
**Time:** O(n). We have one pass to build the prefix sum arrays (O(n)) and another pass to iterate through `i` (O(n)). This gives a total of O(n). · **Space:** O(n), as we use two extra arrays of size `n+1` to store the prefix sums.
**Pros:** Significantly faster than the brute-force approach, with a linear time complexity.; Efficient enough to pass the given constraints.
**Cons:** Uses extra space proportional to the input size, which might be a concern for very large inputs under strict memory constraints.
### Explanation
We can create two prefix sum arrays, one for each row of the grid. `prefixSumTop[i]` will store the sum of elements from `grid[0][0]` to `grid[0][i-1]`, and `prefixSumBottom[i]` will store the cumulative sum for `grid[1]`. Building these arrays takes O(n) time.

After building these arrays, we can revisit the main loop from the brute-force approach. For each possible switch column `i` for the first robot:
*   The sum of the top row from `i+1` to `n-1` (the first choice for robot 2) can be calculated in O(1) as `totalSumTop - prefixSumTop[i+1]`. `totalSumTop` is simply `prefixSumTop[n]`.
*   The sum of the bottom row from `0` to `i-1` (the second choice for robot 2) is directly available as `prefixSumBottom[i]`.

The rest of the logic remains the same: find the maximum of these two sums for each `i`, and then find the minimum of these maximums over all `i`. This brings the time complexity down to a linear scan.

```java
class Solution {
    public long gridGame(int[][] grid) {
        int n = grid[0].length;
        long[] prefixSumTop = new long[n + 1];
        long[] prefixSumBottom = new long[n + 1];

        for (int i = 0; i < n; i++) {
            prefixSumTop[i + 1] = prefixSumTop[i] + grid[0][i];
            prefixSumBottom[i + 1] = prefixSumBottom[i] + grid[1][i];
        }

        long minMaxScore = Long.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            // Sum of points in top row to the right of i
            long topPathScore = prefixSumTop[n] - prefixSumTop[i + 1];
            
            // Sum of points in bottom row to the left of i
            long bottomPathScore = prefixSumBottom[i];

            long secondRobotScore = Math.max(topPathScore, bottomPathScore);
            minMaxScore = Math.min(minMaxScore, secondRobotScore);
        }

        return minMaxScore;
    }
}
```
### Algorithm
*   Get `n`, the number of columns.
*   Create two prefix sum arrays, `prefixSumTop` and `prefixSumBottom`, each of size `n+1`.
*   Populate `prefixSumTop`: `prefixSumTop[i] = prefixSumTop[i-1] + grid[0][i-1]` for `i` from 1 to `n`.
*   Populate `prefixSumBottom`: `prefixSumBottom[i] = prefixSumBottom[i-1] + grid[1][i-1]` for `i` from 1 to `n`.
*   Initialize `minResult` to `Long.MAX_VALUE`.
*   Iterate `i` from `0` to `n-1`.
    *   Calculate the sum of the top row from `i+1` to `n-1` as `topSum = prefixSumTop[n] - prefixSumTop[i+1]`.
    *   The sum of the bottom row from `0` to `i-1` is directly `bottomSum = prefixSumBottom[i]`.
    *   The second robot's score for this `i` is `secondRobotScore = max(topSum, bottomSum)`.
    *   Update `minResult = min(minResult, secondRobotScore)`.
*   Return `minResult`.

## Optimized Single Pass with Running Sums
We can further optimize the prefix sum approach to use constant extra space. Instead of pre-calculating and storing all prefix sums in arrays, we can maintain the two required sums (`topSum` and `bottomSum`) and update them dynamically as we iterate through the columns in a single pass.
**Time:** O(n). We have an initial pass to sum the top row (O(n)) and a second pass to iterate through the columns (O(n)). This is O(n) in total. · **Space:** O(1), as we only use a few variables to store the running sums and the result, independent of the input size `n`.
**Pros:** Most efficient solution in both time (O(n)) and space (O(1)).; It's a clean, single-pass solution after an initial sum calculation.
**Cons:** The logic for updating the running sums might be slightly less intuitive at first glance compared to the explicit prefix sum array approach.
### Explanation
This approach avoids creating separate prefix sum arrays. We can achieve the same result in a single pass.

First, calculate the total sum of the top row. Let's call this `topSum`. Initialize `bottomSum` to 0.

Now, iterate `i` from `0` to `n-1`. In each step, `i` represents the current switch-down column for the first robot.
1.  Subtract `grid[0][i]` from `topSum`. Now `topSum` represents the sum of points to the right of column `i` in the top row.
2.  At this point, `topSum` is the score from the top path option for Robot 2, and `bottomSum` is the score from the bottom path option (which represents the sum of points in `grid[1]` from `0` to `i-1`).
3.  Calculate `max(topSum, bottomSum)` and update our overall minimum result.
4.  Add `grid[1][i]` to `bottomSum`. This prepares `bottomSum` for the next iteration, where it will represent the sum of points to the left of column `i+1`.

This way, we correctly calculate the two competing scores for Robot 2 at each possible switch point `i` for Robot 1, all within a single loop and with constant extra space.

```java
class Solution {
    public long gridGame(int[][] grid) {
        int n = grid[0].length;
        long topSum = 0;
        for (int point : grid[0]) {
            topSum += point;
        }

        long bottomSum = 0;
        long minMaxScore = Long.MAX_VALUE;

        for (int i = 0; i < n; i++) {
            // Robot 1 moves along top row, taking grid[0][i] at this step.
            topSum -= grid[0][i];

            // At this point:
            // topSum is the sum of points in grid[0] from i+1 to n-1.
            // bottomSum is the sum of points in grid[1] from 0 to i-1.
            // These are the two choices for Robot 2.
            
            long secondRobotScore = Math.max(topSum, bottomSum);
            minMaxScore = Math.min(minMaxScore, secondRobotScore);

            // Robot 1 also clears grid[1][i] on its path. For the next iteration (i+1),
            // this point becomes available for Robot 2's bottom path choice.
            bottomSum += grid[1][i];
        }

        return minMaxScore;
    }
}
```
### Algorithm
*   Get `n`, the number of columns.
*   Calculate `topSum` as the total sum of `grid[0]`.
*   Initialize `bottomSum = 0`.
*   Initialize `minResult = Long.MAX_VALUE`.
*   Iterate `i` from `0` to `n-1`.
    *   Update `topSum` by subtracting `grid[0][i]`. This represents the remaining points on the top row if robot 1 switches at `i`.
    *   The second robot's score for this `i` is `max(topSum, bottomSum)`.
    *   Update `minResult = min(minResult, max(topSum, bottomSum))`.
    *   Update `bottomSum` by adding `grid[1][i]`. This prepares `bottomSum` for the next iteration (`i+1`).
*   Return `minResult`.

# Solutions
### Java

```java
class Solution {
public
  long gridGame(int[][] grid) {
    long ans = Long.MAX_VALUE;
    long s1 = 0, s2 = 0;
    for (int v : grid[0]) {
      s1 += v;
    }
    int n = grid[0].length;
    for (int j = 0; j < n; ++j) {
      s1 -= grid[0][j];
      ans = Math.min(ans, Math.max(s1, s2));
      s2 += grid[1][j];
    }
    return ans;
  }
}

```

### CPP

```cpp
using ll = long long ; class Solution { public: long long gridGame ( vector < vector < int >>& grid ) { ll ans = LONG_MAX ; int n = grid [ 0 ]. size (); ll s1 = 0 , s2 = 0 ; for ( int & v : grid [ 0 ]) s1 += v ; for ( int j = 0 ; j < n ; ++ j ) { s1 -= grid [ 0 ][ j ]; ans = min ( ans , max ( s1 , s2 )); s2 += grid [ 1 ][ j ]; } return ans ; } };
```

### Python

```python
class Solution:
    def gridGame(self, grid: List[List[int]]) -> int: ans = inf s1, s2 = sum(grid[0]), 0 for j, v in enumerate(grid[0]): s1 -= v ans = min(ans, max(s1, s2)) s2 += grid[1][j] return ans

```