2017. Grid Game - Detailed Explanation

Problem Statement

The Grid Game is a two-player game played on a 2xN grid (2 rows and N columns). Each cell (r, c) contains some points grid[r][c]. Both robots start at the top-left cell (0,0) and need to reach the bottom-right cell (1, n-1). They can only move right or down at each step. The game proceeds as follows:

• First Robot's move: It travels from (0,0) to (1, n-1) (top-left to bottom-right), collecting all points on its path. After it passes, all cells on its path are set to 0 (those points are removed from the grid).
• Second Robot's move: After the first robot finishes, the second robot also moves from (0,0) to (1, n-1), collecting points on its path. (The second robot may traverse cells that the first robot already did, but those cells would now have 0 points.)

The first robot wants to minimize the total points the second robot can collect, while the second robot wants to maximize its points. Both play optimally. The problem asks: If both robots play optimally, how many points will the second robot collect?

Example 1

Input: grid = [[2,5,4],
               [1,5,1]]
Output: 4

Explanation: If the first robot chooses its path wisely, it can limit the second robot to collecting 4 points. One optimal strategy is:

• First robot goes right to (0,1) (collecting 2 and 5), then goes down to (1,1) and right to (1,2) (collecting 5 and 1). This path is marked in red in the diagram. All these visited cells are set to 0 after the first robot passes.

• The grid after the first robot’s path would look like: [[0, 0, 4],[1, 0, 0]]. Now the second robot can choose a path. The optimal second path (marked in blue) is to go right, right along the top row, then down at the last column. It collects 0 + 0 + 4 + 0 = 4 points (the only remaining points come from cell (0,2) which had 4).

Example 2

Input: grid = [[3,3,1],
               [8,5,2]]
Output: 4

Explanation: Optimal play yields the second robot collecting 4 points. The first robot will choose a path that leaves the second robot with at most 4 points (e.g. first robot may go all the way right on the top row, then drop down at the end). After the first robot’s move, the second robot’s best path collects 0 + 3 + 1 + 0 = 4.

Example 3

Input: grid = [[1,3,1,15],
               [1,3,3,1]]
Output: 7

Explanation: In this case, the second robot can get 7 points if the first robot plays optimally. For instance, the first robot might go down after a certain column to break the grid’s points, and then the second robot picks up 0 + 1 + 3 + 3 + 0 = 7 on its path.

Constraints

• grid.length == 2 (exactly 2 rows).
• n == grid[r].length (same number of columns in each row).
• 1 <= n <= 5 * 10^4 (up to 50,000 columns).
• 1 <= grid[r][c] <= 10^5 (each cell’s points between 1 and 100,000).

These constraints mean the grid can be very long (50k columns), so an efficient solution is needed (potentially up to millions of points in total, so watch out for integer overflow in languages like Java).

Hints

1. Notice that the first robot’s path is fully determined by the column where it moves down to the second row. Since there are n columns, essentially there are n choices for the first robot’s turning poin. For example, it could move down immediately at column 0, or at column 5, or never move down until the last column.

2. After the first robot’s move, the remaining points for the second robot will be in two regions: some points remain in the top row (to the right of where the first robot went down), and some in the bottom row (to the left of where the first robot came down). The second robot will choose the region with the maximum points (since it wants to maximize its collection).

3. Think about using prefix sums (or cumulative sums) to quickly calculate how many points are in the top row to the right of a certain column, and how many are in the bottom row to the left of a certain column. This can help evaluate each possible turning point efficiently.

Multiple Approaches

Brute-Force Approach

Idea: Try every possible path for the first robot and see how many points the second robot would get, then choose the path that minimizes that. Since any path from top-left to bottom-right in a 2xN grid is determined by the single column where the first robot moves down, we can brute-force by trying each possible “down move” position from column 0 to n-1.

For each choice of turning column:

• Simulate the first robot going right until that column, then going down, then going right to the end. This sets some top-row cells and some bottom-row cells to 0 (the ones the first robot passed).

• Compute the maximum points the second robot can collect given that scenario. The second robot can either stay on the top row as long as possible or drop to the bottom immediately – effectively, it will collect either the remaining points on the top row (to the right of the first robot’s drop) or the remaining points on the bottom row (to the left of that drop), whichever is larger.

Why it’s inefficient: There are n possible turning points for the first robot, and calculating the second robot’s points for each choice could be O(n) if we sum up cells each time. Doing this naively would be O(n^2) in the worst case, which is too slow when n can be 50,000 (50k * 50k = 2.5 billion operations). For large grids, brute force would time out.

However, we can optimize the calculation by using prefix sums to get the sums quickly, which leads to the optimal approach.

Optimal Approach (Prefix Sum Strategy)

Key observation: The first robot’s down-move at column j splits the remaining points into two parts:

• Top row, right side: all points from column j+1 to n-1 in the top row (these are the points the first robot left on the top row after it went down).
• Bottom row, left side: all points from column 0 to j-1 in the bottom row (these are the points the first robot never touched in the bottom row, since it came down at j).

The second robot will choose the path that gives the maximum of these two sums. In other words, if the first robot goes down at column j, the second robot’s score will be:

max( sum(top row from j+1 to end),  sum(bottom row from start to j-1) ).

The first robot knows this, so it will choose the j that minimizes that value. We need to compute this efficiently.

Using prefix/suffix sums: We can preprocess:

• A suffix sum for the top row: suffixTop[c] = sum of top row points from column c to n-1 (end). This lets us quickly get the sum of the top row to the right of any given column.

• A prefix sum for the bottom row: prefixBottom[c] = sum of bottom row points from column 0 to c (beginning up to c). This lets us quickly get the sum of the bottom row to the left of any given column.

(We can also do this without storing full arrays by just keeping running totals.)

Steps for the optimal solution:

1. Calculate total points in the top row (this is effectively suffixTop[0] before any moves) and set a running sum for the bottom row to 0 (since initially the first robot has not touched the bottom row).

2. Try each column j as the turning point:

   • When considering column j for the turn, reduce the top-row running sum by grid[0][j] (as if the first robot collected the points in top cell (0,j) and is about to leave the top row after this column). Now the top running sum represents the points remaining in the top row to the right of column j (columns j+1...n-1).
   • The bottom running sum represents the points the first robot left in the bottom row to the left of column j (columns 0...j-1) – because we add bottom points as the first robot passes them by staying on the top.
   • Compute second_points = max(top_running_sum, bottom_running_sum). This is how many points the second robot could get if the first goes down at j.
   • Track the minimum second_points over all choices of j. This minimum is the outcome when both play optimally (first robot will choose the j that yields this minimum).

3. Return the minimum found.

Using this method, we only loop through the grid once (O(n)) and do O(1) work for each column, which is efficient even for n = 50,000.

Why this works: The first robot’s choice at column j completely determines the second robot’s optimal response (go where the points are). By evaluating each possible turning column, we ensure we’re considering all strategies. We take the min of the second robot’s max points, implementing the first robot’s goal of minimizing the second’s score.

Step-by-Step Walkthrough (Example)

Let’s walk through Example 1 (grid = [[2,5,4],[1,5,1]]) step by step using the optimal approach:

Grid layout for reference:

• Top row: 2, 5, 4
• Bottom row: 1, 5, 1

First, compute the total of the top row and bottom row:

• Total top = 2 + 5 + 4 = 11
• Total bottom = 1 + 5 + 1 = 7

Now consider each possible column where the first robot could move down:

• If the first robot moves down at column 0 (immediately):

  • The first robot would go down right away, so it does not travel right on the top row at all. This means it leaves all other top row points untouched. The remaining points on the top row (columns 1 through end) = 5 + 4 = 9.

  • Since the first robot went down at the start, it starts collecting on the bottom from column 0 onward. But it will collect everything on the bottom row from column 0 to the end as it moves right, except it can’t collect anything to the left of its drop (there is nothing to the left in this case). The points left on the bottom row to the left of column 0 = 0 (there are no columns before 0).

  • Second robot’s best choice: it can either take the remaining top-row points (9) or the remaining bottom-row points (0). Obviously it will take 9 (by going right along the top row).

  • Second robot collects 9 points in this scenario.

• If the first robot moves down at column 1:

  • The first robot travels one step on the top (through column 0) then moves down at column 1. It collects the top-row points from column 0 (2 points). After dropping to the bottom at column 1, it will continue to move right from (1,1) onward, collecting some bottom points.

  • Remaining top-row points (columns 2 to end): now the first robot left everything from column 2 onward on the top row. That sum = 4 (only column 2 remains on top, since it went down at col1).

  • Remaining bottom-row points (columns 0 to 0, i.e., left of col1): the first robot didn’t touch bottom row column 0. That sum = 1.

  • Second robot’s best choice: it can collect max(4, 1) = 4 points. In fact, it will choose to go along the top row (skipping the now-zeroed cells) to get that 4.

  • Second robot collects 4 points in this scenario.

• If the first robot moves down at column 2 (waits until the last column to drop):

  • The first robot stays on the top row through columns 0, 1, 2 (collecting 2+5+4), then drops down at the end to (1,2) and finishes. Essentially it went right all the way and then down at the last cell. It collected all top-row points.

  • Remaining top-row points (to the right of col2): none, because it traveled to the end of the top row. Sum = 0.

  • Remaining bottom-row points (columns 0 to 1): the first robot only went down at the very end, so it didn’t touch bottom row columns 0 and 1. Those remain: 1 + 5 = 6.

  • Second robot’s best choice: max(0, 6) = 6 points, by going down immediately and then right along the bottom row to collect those 6.

  • Second robot collects 6 points in this scenario.

Now, the first robot will choose the scenario that minimizes the second robot’s points. From the above outcomes, the second robot would get 9, 4, or 6 points. The minimum of those is 4 (achieved when the first robot goes down at column 1). So the first robot’s optimal strategy is to drop at column 1, limiting the second robot to 4 points.

This matches the expected output. In terms of actual paths:

• First robot’s path for this optimal strategy: (0,0) -> (0,1) -> down to (1,1) -> (1,2). (It collected points [2, 5] on the top and [5, 1] on the bottom.)
• Second robot’s path: (0,0) -> (0,1) -> (0,2) -> (1,2). By the time it moves, the cells (0,0), (0,1), (1,1), (1,2) are zero, so it only picks up the points at (0,2) which is 4.

Code Implementations

Below are implementations in Python and Java following the optimal approach. Both solutions run in O(n) time and use O(1) extra space (not counting input storage). We use 64-bit integers to handle large sums safely.

Python Solution