Problem Description

You have a 2x n grid where each cell contains points. Two robots will traverse this grid in sequence, both starting at position (0, 0) and ending at position (1, n-1).

The movement rules are:

• Each robot can only move right (from (r, c) to (r, c+1)) or down (from (r, c) to (r+1, c))
• Since the grid has only 2 rows, each robot must move down exactly once at some position

The game proceeds as follows:

1. The first robot goes from (0, 0) to (1, n-1), collecting all points on its path
2. All cells visited by the first robot have their points set to 0
3. The second robot then goes from (0, 0) to (1, n-1), collecting points from the remaining cells

The key insight is that the first robot's path will always look like: moving right along row 0 for some distance, moving down to row 1, then continuing right to the end. This creates a division where the second robot can only collect points from either:

• The remaining cells in row 0 (to the right of where robot 1 went down)
• The remaining cells in row 1 (to the left of where robot 1 went down)

The first robot wants to minimize the second robot's score, while the second robot wants to maximize its score. Both robots play optimally.

The solution uses prefix sums to efficiently calculate the maximum points the second robot can collect for each possible turning point of the first robot. Variable s1 tracks the sum of remaining points in row 0 (initially all points, then decreased as we move right), and s2 tracks the sum of points in row 1 up to the current position (initially 0, then increased as we move right). For each position j where robot 1 might turn down, the second robot's optimal score is max(s1, s2). The answer is the minimum of all these maximum values.

Intuition

Since the grid has only 2 rows, the first robot's path has a very specific structure - it must move right along the top row for some number of steps, then move down exactly once, and continue right along the bottom row until reaching the end. This creates a "turning point" that divides the grid into two regions.

Once the first robot chooses where to turn down (say at column j), it collects all points from cells (0,0) to (0,j) in the top row, and cells (1,j) to (1,n-1) in the bottom row. These cells become 0.

The second robot, playing optimally, now has two choices:

1. Stay on the top row as long as possible to collect points from cells (0,j+1) to (0,n-1)
2. Drop down immediately to collect points from cells (1,0) to (1,j-1)

The second robot will choose whichever option gives more points. So for any turning point j chosen by the first robot, the second robot scores max(top_remaining, bottom_remaining).

The first robot, knowing this, wants to choose the turning point j that minimizes this maximum. This leads to a minimax problem: min over all j of max(top_remaining, bottom_remaining).

To implement this efficiently, we can maintain running sums:

• s1 starts as the sum of all top row values, and we subtract grid[0][j] as we consider each turning point moving right
• s2 starts at 0 and accumulates grid[1][j] as we move right

For each position j, s1 represents points available in the top row after position j, and s2 represents points available in the bottom row before position j. The second robot's best score at this configuration is max(s1, s2), and we track the minimum across all positions.

Learn more about Prefix Sum patterns.

Solution Approach

The solution uses a prefix sum technique to efficiently calculate the optimal result for the minimax problem.

Initialization:

• ans = inf: Initialize the answer to infinity since we're looking for the minimum value
• s1 = sum(grid[0]): Calculate the total sum of all points in the first row
• s2 = 0: Initialize the prefix sum of the second row to 0

Main Algorithm:

We iterate through each column j from 0 to n-1, considering it as the potential turning point where the first robot moves down:

1. Update suffix sum for row 0: s1 -= v where v = grid[0][j]

   • After this subtraction, s1 represents the sum of points in row 0 from column j+1 to n-1
   • These are the points the second robot could collect if it stays on row 0 longer

2. Calculate the second robot's maximum score: max(s1, s2)

   • The second robot will choose the better of two options:
     • Collect remaining points in row 0: value is s1
     • Drop down early and collect points in row 1 before column j: value is s2

3. Update the answer: ans = min(ans, max(s1, s2))

   • The first robot wants to minimize the second robot's maximum possible score

4. Update prefix sum for row 1: s2 += grid[1][j]

   • Add the current cell's value to the prefix sum
   • This prepares s2 for the next iteration where it will represent points from column 0 to j

Why this works:

The key insight is that we process the turning points from left to right. At each position j:

• s1 has already excluded points that the first robot collected from row 0 (columns 0 to j)
• s2 contains exactly the points available in row 1 before column j

This allows us to compute the second robot's optimal score for each possible first robot strategy in O(1) time per position, resulting in an overall O(n) time complexity with O(1) extra space.

Example Walkthrough

Let's walk through a small example with a 2×3 grid:

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

Initial Setup:

• ans = infinity
• s1 = sum(grid[0]) = 2 + 5 + 4 = 11 (sum of entire top row)
• s2 = 0 (no bottom row cells counted yet)

Iteration 1: j = 0 (robot 1 turns down at column 0)

• s1 = 11 - 2 = 9 (remaining top row: columns 1-2 have sum 5+4=9)
• Second robot's best score: max(s1, s2) = max(9, 0) = 9
  • Option 1: Stay top and collect columns 1-2 of row 0 → score = 9
  • Option 2: Drop immediately (no cells available in row 1) → score = 0
• Update ans = min(infinity, 9) = 9
• Update s2 = 0 + 1 = 1 (add grid[1][0] for next iteration)

Iteration 2: j = 1 (robot 1 turns down at column 1)

• s1 = 9 - 5 = 4 (remaining top row: column 2 has value 4)
• Second robot's best score: max(s1, s2) = max(4, 1) = 4
  • Option 1: Stay top and collect column 2 of row 0 → score = 4
  • Option 2: Drop early and collect column 0 of row 1 → score = 1
• Update ans = min(9, 4) = 4
• Update s2 = 1 + 5 = 6 (add grid[1][1] for next iteration)

Iteration 3: j = 2 (robot 1 turns down at column 2)

• s1 = 4 - 4 = 0 (no remaining cells in top row)
• Second robot's best score: max(s1, s2) = max(0, 6) = 6
  • Option 1: No cells left in row 0 → score = 0
  • Option 2: Drop early and collect columns 0-1 of row 1 → score = 6
• Update ans = min(4, 6) = 4
• Update s2 = 6 + 1 = 7 (not used further)

Result: The answer is 4. This happens when robot 1 moves right once (collecting 2, 5), then moves down at column 1, and continues right (collecting 5, 1). Robot 2 can then optimally collect the cell at position (0,2) with value 4.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the number of columns in the grid. The algorithm iterates through each column exactly once using a single for loop that goes through grid[0]. In each iteration, it performs constant time operations: subtracting v from s1, computing the minimum and maximum, and adding grid[1][j] to s2.

The space complexity is O(1). The algorithm only uses a fixed number of variables (ans, s1, s2, j, v) regardless of the input size. No additional data structures that scale with the input are created.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Initial Values for Prefix/Suffix Sums

A common mistake is initializing s1 or s2 incorrectly, such as including or excluding cells that shouldn't be counted at the start.

Incorrect approach:

# Wrong: Including the first cell of row 0 in both robot paths
s1 = sum(grid[0][1:])  # Missing grid[0][0]
s2 = grid[1][0]  # Including a cell that might not be collected

Correct approach:

s1 = sum(grid[0])  # Initially all of row 0
s2 = 0  # Initially none of row 1

2. Wrong Order of Operations in the Loop

The order of updating s1, calculating the maximum, updating the answer, and updating s2 is crucial. Changing this order leads to incorrect results.

Incorrect approach:

for j in range(n):
    s2 += grid[1][j]  # Wrong: Adding before calculating max
    s1 -= grid[0][j]
    ans = min(ans, max(s1, s2))

Correct approach:

for j in range(n):
    s1 -= grid[0][j]  # First: remove from top
    ans = min(ans, max(s1, s2))  # Second: calculate minimax
    s2 += grid[1][j]  # Last: add to bottom for next iteration

3. Misunderstanding the Game Theory Aspect

Some might think both robots cooperate or that the first robot tries to maximize its own score. The key is understanding that robot 1 plays adversarially to minimize robot 2's score.

Incorrect interpretation:

# Wrong: Trying to maximize robot 1's score
max_robot1_score = 0
for j in range(n):
    robot1_score = sum(grid[0][:j+1]) + sum(grid[1][j:])
    max_robot1_score = max(max_robot1_score, robot1_score)

Correct interpretation: The solution correctly implements the minimax strategy where robot 1 minimizes the maximum score robot 2 can achieve.

4. Edge Case: Single Column Grid (n=1)

When the grid has only one column, both robots must take the same path, and robot 2 gets nothing. Some implementations might not handle this correctly.

Potential issue:

# If n=1, the loop runs once with j=0
# After s1 -= grid[0][0], s1 becomes 0
# s2 is still 0
# max(s1, s2) = 0, which is correct

The provided solution handles this correctly, but it's worth verifying edge cases explicitly.

5. Off-by-One Errors in Understanding Cell Collections

A common confusion is about which cells each robot collects. When robot 1 turns down at column j:

• Robot 1 collects: grid[0][0...j] and grid[1][j...n-1]
• Robot 2 can collect either: grid[0][j+1...n-1] OR grid[1][0...j-1]

Incorrect mental model: Thinking robot 2 can collect grid[1][0...j] (including column j in row 1), which would be wrong since robot 1 already took grid[1][j].

Solution: The code correctly handles this by updating s2 after calculating the maximum, ensuring grid[1][j] is only available for the next iteration's calculation.