Grid Game

Grid Game

What is this problem about?

The Grid Game coding problem features a $2 imes N$ grid with points in each cell. Two robots play a game. Robot 1 starts at (0,0) and moves to (1, N-1) (only moving right or down). It collects all points on its path, setting those cells to 0. Robot 2 then makes the exact same journey, collecting the remaining points. Robot 1 wants to minimize Robot 2's score, while Robot 2 wants to maximize its own score. You need to return the score Robot 2 will achieve assuming both play optimally.

Why is this asked in interviews?

Microsoft and Amazon use this Prefix Sum and Array pattern problem to test your ability to model adversarial games. Because the grid only has 2 rows, Robot 1 can only move down exactly once. This drastically reduces the search space. It evaluates if you can identify that Robot 1's choice splits the remaining points for Robot 2 into two distinct, non-overlapping segments.

Algorithmic pattern used

This problem relies on Prefix Sums and Min-Max Logic.

1. Calculate the prefix sum of the top row and the suffix sum of the bottom row.
2. If Robot 1 moves down at column i, it leaves two segments of points for Robot 2:
   • The remaining points in the top row from i + 1 to N - 1.
   • The preceding points in the bottom row from 0 to i - 1.
3. Robot 2 will greedily pick the segment with the larger sum. So, Robot 2's score for a given i is max(top_remaining, bottom_preceding).
4. Robot 1 will choose the column i that minimizes this maximum score.

Example explanation

Grid: [2, 5, 4] [1, 5, 1]

• If R1 drops at col 0: R2 gets max([5, 4], []) = max(9, 0) = 9.
• If R1 drops at col 1: R2 gets max([4], [1]) = max(4, 1) = 4.
• If R1 drops at col 2: R2 gets max([], [1, 5]) = max(0, 6) = 6. Robot 1 wants to minimize R2's score, so R1 chooses column 1. Robot 2's score is 4.

Common mistakes candidates make

• Dynamic Programming Overkill: Trying to use a standard pathfinding DP. This doesn't work because Robot 1's goal isn't just to maximize its own score, but to minimize Robot 2's.
• Assuming R1 Maximizes Own Score: Robot 1 might sacrifice its own points to force Robot 2 into a worse path. The objective function is purely based on Robot 2's outcome.
• Integer Overflow: The sums can be large, so 64-bit integers are required for the prefix/suffix accumulators.

Interview preparation tip

In 2-row grid pathfinding problems, the key insight is always that a path can only move "down" exactly once. This turns the problem into a 1D array search where you just need to pick the optimal "drop point."