LeetCode 2017 - Grid Game

The problem gives us a 2 x n grid where each cell contains some number of points. Two robots move across this grid one after another. Both robots start at the top-left corner (0, 0) and must reach the bottom-right corner (1, n - 1). The movement rules are very restrictive.

leetcodemediumarraymatrixprefix-sum

LeetCode Problem 2017

Difficulty: 🟡 Medium
Topics: Array, Matrix, Prefix Sum

Solution

LeetCode 2017 - Grid Game

Problem Understanding

The problem gives us a 2 x n grid where each cell contains some number of points. Two robots move across this grid one after another. Both robots start at the top-left corner (0, 0) and must reach the bottom-right corner (1, n - 1).

The movement rules are very restrictive. A robot may only move:

  • Right, from (r, c) to (r, c + 1)
  • Down, from (r, c) to (r + 1, c)

Since the grid has only two rows, every valid path has a very important property: each robot moves right several times on the top row, then moves down exactly once, then continues moving right on the bottom row.

The first robot moves first and collects all points along its path. Every cell visited by the first robot is then set to 0. After that, the second robot moves on the modified grid and collects points from the remaining cells.

The objectives of the two robots are opposite:

  • The first robot wants to minimize the second robot’s final score.
  • The second robot wants to maximize its own score.

We must determine the score the second robot obtains if both robots play optimally.

The constraints are important:

  • n can be as large as 5 * 10^4
  • Each cell value can be up to 10^5

This means the total sum can become very large, so we must use 64-bit integers in languages like Go. The constraints also make brute force enumeration of all possible paths impractical.

An important observation is that because the grid has only two rows, the first robot’s path is completely determined by the column where it moves down from the top row to the bottom row.

Several edge cases are important:

  • n = 1, where both robots are forced onto the same single path.
  • Very large values, where integer overflow becomes possible in some languages.
  • Cases where the optimal strategy is not locally obvious, because the first robot is minimizing the second robot’s maximum possible remaining score.

Approaches

Brute Force Approach

A brute force solution would try every possible column where the first robot can move down. For each such choice, we simulate the resulting grid after the first robot clears its path. Then we compute the maximum score the second robot can achieve on that modified grid.

Since the grid has only two rows, there are exactly n possible turning points for the first robot. For each turning point, we could recompute the remaining sums on the grid by scanning the rows again.

This approach works because it explicitly checks every valid strategy for the first robot and computes the resulting best response from the second robot. However, if implemented naively, each simulation costs O(n), and we do this n times, leading to O(n^2) complexity.

With n = 5 * 10^4, quadratic time is too slow.

Optimal Approach

The key insight is that once the first robot chooses a column c where it moves down, the remaining grid has a very predictable structure.

Suppose the first robot:

  • Travels along the top row from column 0 to c
  • Moves down at column c
  • Travels along the bottom row from column c to n - 1

After this happens:

  • The remaining cells in the top row are only the columns to the right of c
  • The remaining cells in the bottom row are only the columns to the left of c

The second robot can collect points from only one of these two regions effectively:

  • Either the remaining top-right section
  • Or the remaining bottom-left section

Therefore, if the first robot turns at column c, the second robot’s score becomes:

max(
    remaining sum in top row after c,
    remaining sum in bottom row before c
)

The first robot wants to minimize this value.

This transforms the problem into a prefix/suffix sum optimization problem.

We maintain:

  • topRemaining, the suffix sum of the top row
  • bottomCollected, the prefix sum of the bottom row

As we iterate through each possible turning column, we compute:

secondRobot = max(topRemaining, bottomCollected)

Then we minimize this over all choices.

This gives an O(n) solution.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Simulates every turning point and rescans rows each time
Optimal O(n) O(1) Uses running prefix and suffix sums

Algorithm Walkthrough

  1. Compute the total sum of the top row.

This represents the points still available on the top row before the first robot starts removing cells. 2. Initialize two running values.

  • topRemaining starts as the total top-row sum.
  • bottomCollected starts as 0.

These represent:

  • The points remaining in the top row to the right of the turning point.
  • The points accumulated in the bottom row to the left of the turning point.
  1. Iterate through each column c.

Treat column c as the point where the first robot moves down. 4. Remove the current top-row cell from topRemaining.

Since the first robot visits (0, c), that cell becomes unavailable to the second robot. 5. Compute the second robot’s best possible score.

The second robot chooses whichever side gives more points:

  • Top-right remaining section
  • Bottom-left accumulated section

So:

secondRobot = max(topRemaining, bottomCollected)
  1. Update the answer.

The first robot wants to minimize the second robot’s score:

answer = min(answer, secondRobot)
  1. Add the current bottom-row cell to bottomCollected.

After considering column c, future turning points will leave this bottom cell available to the second robot. 8. Continue until all columns are processed. 9. Return the minimum value found.

Why it works

For any turning column c, the first robot removes:

  • All top-row cells from 0 through c
  • All bottom-row cells from c through n - 1

This leaves exactly two possible regions with points:

  • Top row after c
  • Bottom row before c

The second robot can only maximize one of these regions, so its optimal score is the maximum of the two sums. Since the first robot chooses the turning point minimizing this value, checking all turning points guarantees the optimal answer.

Python Solution

from typing import List

class Solution:
    def gridGame(self, grid: List[List[int]]) -> int:
        n = len(grid[0])

        top_remaining = sum(grid[0])
        bottom_collected = 0

        answer = float("inf")

        for col in range(n):
            top_remaining -= grid[0][col]

            second_robot = max(top_remaining, bottom_collected)

            answer = min(answer, second_robot)

            bottom_collected += grid[1][col]

        return answer

The implementation begins by computing the total sum of the top row. This allows us to track the remaining top-row points dynamically as we move from left to right.

Inside the loop, we first subtract the current top-row value because the first robot consumes that cell when turning at the current column.

Next, we compute the second robot’s best possible score. The second robot chooses whichever remaining region contains more points, so we take the maximum of:

  • top_remaining
  • bottom_collected

We then minimize the overall answer because the first robot is trying to reduce the second robot’s maximum achievable score.

Finally, we add the current bottom-row value into bottom_collected, preparing for the next iteration.

The algorithm uses only a few variables and processes each column exactly once.

Go Solution

func gridGame(grid [][]int) int64 {
    n := len(grid[0])

    var topRemaining int64
    for _, value := range grid[0] {
        topRemaining += int64(value)
    }

    var bottomCollected int64
    answer := topRemaining

    for col := 0; col < n; col++ {
        topRemaining -= int64(grid[0][col])

        secondRobot := max(topRemaining, bottomCollected)

        answer = min(answer, secondRobot)

        bottomCollected += int64(grid[1][col])
    }

    return answer
}

func max(a, b int64) int64 {
    if a > b {
        return a
    }
    return b
}

func min(a, b int64) int64 {
    if a < b {
        return a
    }
    return b
}

The Go implementation follows exactly the same logic as the Python version. The most important difference is integer handling.

Since grid values may be large and the total sum can exceed 32-bit integer limits, all running sums are stored as int64.

Go does not provide built-in generic min and max functions for integers, so helper functions are implemented explicitly.

Worked Examples

Example 1

grid = [[2,5,4],
        [1,5,1]]

Initial values:

topRemaining = 11
bottomCollected = 0
answer = inf
Column topRemaining after subtraction bottomCollected secondRobot = max(...) answer
0 9 0 9 9
1 4 1 4 4
2 0 6 6 4

Final answer:

4

Example 2

grid = [[3,3,1],
        [8,5,2]]

Initial values:

topRemaining = 7
bottomCollected = 0
Column topRemaining after subtraction bottomCollected secondRobot answer
0 4 0 4 4
1 1 8 8 4
2 0 13 13 4

Final answer:

4

Example 3

grid = [[1,3,1,15],
        [1,3,3,1]]

Initial values:

topRemaining = 20
bottomCollected = 0
Column topRemaining after subtraction bottomCollected secondRobot answer
0 19 0 19 19
1 16 1 16 16
2 15 4 15 15
3 0 7 7 7

Final answer:

7

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each column is processed exactly once
Space O(1) Only a few running variables are used

The algorithm is linear because it scans the grid columns one time while maintaining running prefix and suffix sums. No additional arrays or data structures proportional to n are required.

Test Cases

from typing import List

class Solution:
    def gridGame(self, grid: List[List[int]]) -> int:
        n = len(grid[0])

        top_remaining = sum(grid[0])
        bottom_collected = 0

        answer = float("inf")

        for col in range(n):
            top_remaining -= grid[0][col]

            second_robot = max(top_remaining, bottom_collected)

            answer = min(answer, second_robot)

            bottom_collected += grid[1][col]

        return answer

solution = Solution()

assert solution.gridGame([[2,5,4],[1,5,1]]) == 4  # Example 1
assert solution.gridGame([[3,3,1],[8,5,2]]) == 4  # Example 2
assert solution.gridGame([[1,3,1,15],[1,3,3,1]]) == 7  # Example 3

assert solution.gridGame([[1],[1]]) == 0  # Single column edge case

assert solution.gridGame([[1,2],[3,4]]) == 2  # Small grid

assert solution.gridGame([[10,1,1],[1,10,10]]) == 2  # Optimal early turn

assert solution.gridGame([[1,1,100],[50,50,1]]) == 100  # Large top suffix

assert solution.gridGame([[100000,100000],[100000,100000]]) == 100000  # Large values

assert solution.gridGame([[5,5,5,5],[5,5,5,5]]) == 10  # Uniform values

assert solution.gridGame([[20,3,20,17],[9,1,1,19]]) == 20  # Mixed values

Test Summary

Test Why
[[2,5,4],[1,5,1]] Validates example 1
[[3,3,1],[8,5,2]] Validates example 2
[[1,3,1,15],[1,3,3,1]] Validates example 3
[[1],[1]] Tests minimum possible grid width
[[1,2],[3,4]] Tests small basic scenario
[[10,1,1],[1,10,10]] Tests optimal early turning point
[[1,1,100],[50,50,1]] Tests dominance of top suffix
[[100000,100000],[100000,100000]] Tests large integer handling
[[5,5,5,5],[5,5,5,5]] Tests symmetric grid
[[20,3,20,17],[9,1,1,19]] Tests irregular distribution

Edge Cases

One important edge case is when n = 1. In this scenario, there is only a single column, so both robots are forced to follow exactly the same path. The first robot collects every cell immediately, leaving nothing for the second robot. The implementation handles this naturally because topRemaining becomes 0 before any comparison is made.

Another important edge case involves very large grid values. Since each cell may contain up to 10^5 points and there may be 5 * 10^4 columns, the total sum can become extremely large. Languages with fixed-width integers, such as Go, must use int64 to avoid overflow. The provided Go solution explicitly converts all values to int64.

A third important edge case occurs when the optimal turning point is near the beginning or near the end of the grid. Naive greedy reasoning may incorrectly assume the robot should balance both sides evenly. However, some grids are highly skewed, making an extreme turning point optimal. The algorithm correctly checks every possible turning column, ensuring the true minimum is always found.

A fourth subtle edge case appears when both remaining regions contain equal sums. In such situations, the second robot can achieve either value, but the result remains the same because we only care about the maximum obtainable score. The algorithm handles this automatically through the max(topRemaining, bottomCollected) computation.