I began by analyzing the rules of the game and the constraints involving two robots navigating a 2xN grid. The key observation was that the first robot, by setting all cells on its path to zero, directly influences the points available for the second robot to collect. Therefore, the first robot's primary goal is to strategically block high-value paths to minimize the points left for the second robot. On the other hand, the second robot will always choose its path to maximize the points it collects from the remaining grid.
I used prefix sums. This allow for fast computation of the total points along any subpath in the grid. With prefix sums, it becomes straightforward to determine the points remaining in the top and bottom rows for any split point where the first robot might switch from the top row to the bottom row. This avoids the need for recalculating sums repeatedly, which is critical given the constraints of up to (5 \times 10^4) columns.
The first robot evaluates all possible paths by considering every column as a potential switch point from the top to the bottom row. For each split column (i), I calculated the points remaining in both the top and bottom rows after the first robot’s traversal. Using this, I determined the maximum points the second robot could collect if it followed its optimal strategy. The first robot then aims to minimize this maximum score, effectively forcing the second robot into the least favorable outcome.
Finally, I iterated through all possible paths for the first robot and computed the corresponding maximum scores for the second robot. Among all these scenarios, the one that minimized the second robot’s score was selected as the solution.
class Solution:
def gridGame(self, grid: List[List[int]]) -> int:
n = len(grid[0])
# Compute prefix sums for both rows
top_prefix = [0] * n
bottom_prefix = [0] * n
top_prefix[0] = grid[0][0]
bottom_prefix[0] = grid[1][0]
for i in range(1, n):
top_prefix[i] = top_prefix[i - 1] + grid[0][i]
bottom_prefix[i] = bottom_prefix[i - 1] + grid[1][i]
result = float('inf')
for i in range(n):
top_remaining = top_prefix[n - 1] - top_prefix[i]
bottom_remaining = bottom_prefix[i - 1] if i > 0 else 0
second_robot_score = max(top_remaining, bottom_remaining)
result = min(result, second_robot_score)
return result- Time: O(n)
- Space: O(n)
