Grid Game

Photo by Sigmund on Unsplash

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:

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:

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:

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

Intuition

1. Focus on the First Robot’s Decision:

• The key to this problem lies in understanding how the first robot’s path significantly impacts the second robot’s score.
• The first robot’s decision essentially boils down to choosing a column ‘j’ where it transitions from the top row (row 0) to the bottom row (row 1).

2. Calculate Prefix Sums:

• Precompute prefix sums for both rows: This will allow you to efficiently calculate the sum of points in any subarray of a row.

3. Determine the Second Robot’s Optimal Path:

• Given the first robot’s transition point ‘j’:
• The second robot will always choose the row with the higher sum of remaining points from its current position.

4. Minimize the Second Robot’s Score:

• The first robot’s optimal strategy is to choose the transition point ‘j’ that minimizes the maximum possible score the second robot can achieve.

5. Implement the Solution:

• Iterate through all possible transition points ‘j’.
• For each ‘j’, calculate the maximum score the second robot can achieve.
• Keep track of the minimum of these maximum scores.

Code

class Solution:
    def gridGame(self, grid: List[List[int]]) -> int:
        length = len(grid[0])
        prefix1, prefix2 = grid[0].copy(), grid[1].copy()
        for i in range(1, length):
            prefix1[i] += prefix1[i - 1]
            prefix2[i] += prefix2[i - 1]
        ans = float("inf")
        for i in range(length):
            top = prefix1[-1] - prefix1[i]
            bottom = prefix2[i - 1] if i > 0 else 0
            secondRobot = max(top, bottom)
            ans = min(ans, secondRobot)
        return ans

Code Explanation

1. Prefix Sum Arrays

prefix1, prefix2 = grid[0].copy(), grid[1].copy()
for i in range(1, length):
    prefix1[i] += prefix1[i - 1]
    prefix2[i] += prefix2[i - 1]

• prefix1 and prefix2 store the cumulative sum of the points in the top and bottom rows, respectively.
• After this step:
• prefix1[i] gives the total points in the top row from column 0 to i.
• prefix2[i] gives the total points in the bottom row from column 0 to i.

2. Iterate Over Each Column as a Breakpoin

for i in range(length):
    top = prefix1[-1] - prefix1[i]
    bottom = prefix2[i - 1] if i > 0 else 0
    secondRobot = max(top, bottom)
    ans = min(ans, secondRobot)

Column i is treated as the breakpoint where the first robot switches from the top row to the bottom row:

1. top: Points left in the top row after column i. This is the total top row points minus the points collected up to column i.
2. bottom: Points collected in the bottom row before column i. This is the cumulative sum of the bottom row up to column i - 1. If i = 0, there are no points collected yet, so it's 0.
3. secondRobot: The second robot will maximize its score by taking the larger of the two values (top or bottom).
4. ans: The first robot minimizes the second robot's points by selecting the breakpoint that results in the smallest secondRobot.

Key Idea

• The first robot tries to split the grid into two parts such that the maximum points available for the second robot is minimized.
• The second robot will always choose the path that gives it the most points in the remaining grid.

Complexity

1. Time Complexity: O(n), where n is the number of columns in the grid. This is due to the prefix sum calculation and the single loop over the columns.
2. Space Complexity: O(n), for the prefix1 and prefix2 arrays.