---
id: 2017
title: Grid Game
difficulty: Medium
tags:
  - array
  - matrix
  - prefix-sum
status: Solved
date_solved: 2026-06-05
leetcode_url: https://leetcode.com/problems/grid-game/
review_needed: false
---

# 2017. Grid Game

> [!info] **Problem Link**: [LeetCode - Grid Game](https://leetcode.com/problems/grid-game/)

## 📝 Problem Description

You are given a **0-indexed** 2D array `grid` of size `2 x n`, where `grid[r][c]` represents the number of points at cell `(r, c)`. Two robots are playing a game on this grid.

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

1.  **Robot 1** moves first. It collects all points on its path, and those cells are set to `0`.
2.  **Robot 2** moves second. It collects points from the remaining cells on its path.
3.  **Goal:** Robot 1 wants to **minimize** the points Robot 2 collects. Robot 2 wants to **maximize** its own points.

Return *the number of points collected by the second robot* assuming both play optimally.

---

### 📥 Example 1
> **Input:** `grid = [[2,5,4],[1,5,1]]`
> **Output:** `4`
> **Explanation:** 
> Robot 1 takes path (0,0) -> (0,1) -> (1,1) -> (1,2). The cells (0,0), (0,1), (1,1), and (1,2) become 0.
> Robot 2 can then take path (0,0) -> (0,1) -> (0,2) -> (1,2) to collect 4 points (only grid[0][2] remains).

### 📥 Example 2
> **Input:** `grid = [[3,3,1],[8,5,2]]`
> **Output:** `4`

---

## 💡 Approaches & Explanations

### Approach 1: Prefix Sums — *Optimal*
Since there are only 2 rows, each robot must transition from the top row to the bottom row exactly once. If Robot 1 "drops" to the second row at column `i`, then:
-   The only points left in the **top row** are from column `i + 1` to `n - 1`.
-   The only points left in the **bottom row** are from column `0` to `i - 1`.

Robot 2 will optimally choose the maximum of these two remaining segments. Robot 1, knowing this, will choose the "drop" column `i` that minimizes Robot 2's maximum possible score.

1. Calculate the total sum of the top row.
2. Iterate through each column `i` (representing Robot 1's drop point):
    - Keep track of the points remaining in the top row (sum of `grid[0][i+1:]`).
    - Keep track of the points remaining in the bottom row (sum of `grid[1][:i]`).
    - For each `i`, Robot 2's score is `max(top_remaining, bottom_remaining)`.
    - Minimize this score across all `i`.

#### 📊 Complexity Analysis
- **Time Complexity:** $O(N)$ where $N$ is the number of columns. We traverse the grid twice (once for the total sum and once to find the optimal column).
- **Space Complexity:** $O(1)$ if we calculate sums on the fly (ignoring input space).

---

## 💻 Code Implementations

### Python3
```python
class Solution:
    def gridGame(self, grid: List[List[int]]) -> int:
        n = len(grid[0])
        top_sum = sum(grid[0])
        bottom_sum = 0
        res = float("inf")
        
        for i in range(n):
            # If Robot 1 drops at column i:
            # Robot 2 can either take the remaining top part...
            top_sum -= grid[0][i]
            
            # ...or the remaining bottom part.
            # (bottom_sum here represents grid[1][0...i-1])
            
            robot2_score = max(top_sum, bottom_sum)
            res = min(res, robot2_score)
            
            # Prepare bottom_sum for the next iteration (i + 1)
            bottom_sum += grid[1][i]
            
        return res
```

---

## 🧠 Key Takeaways & Lessons
- **Game Theory Simplification:** In problems where Robot 1 wants to minimize Robot 2's maximum, look for the bottleneck. Here, the bottleneck is Robot 1's single vertical move.
- **Prefix/Suffix Sum Strategy:** When dealing with split ranges (e.g., everything before `i` and everything after `i`), prefix and suffix sums are the most efficient way to compute segment totals in $O(1)$.