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 == 2n == grid[r].length1 <= n <= 5 * 1041 <= grid[r][c] <= 105The key idea in Grid Game is to minimize the score that the second robot can collect after the first robot chooses its path. The grid contains only two rows, so the first robot effectively decides the column where it moves down from the top row to the bottom row.
A useful observation is that once the first robot moves down, all cells to the right of that column in the top row and all cells to the left in the bottom row remain available for the second robot. The second robot will always choose the larger of these two remaining sums.
To evaluate each possible turning column efficiently, use prefix sums (or running sums) for both rows. This allows quick computation of the remaining points in the top-right and bottom-left sections. The first robot should choose the column that minimizes the maximum score the second robot can obtain.
This approach scans the columns once, leading to O(n) time complexity with O(1) extra space when using running sums.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Prefix Sum / Greedy Column Evaluation | O(n) | O(1) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
There are n choices for when the first robot moves to the second row.
Can we use prefix sums to help solve this problem?
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Grid Game is a common medium-level interview problem that tests prefix sums, greedy reasoning, and matrix traversal. Variations of this problem can appear in interviews at large tech companies.
Prefix sums allow quick calculation of the remaining values in different sections of the grid after the first robot chooses its turning point. This avoids recalculating sums repeatedly and keeps the solution linear in time.
The optimal approach uses prefix sums with a greedy observation. By evaluating every column where the first robot could move down, we compute the remaining top-right and bottom-left sums and minimize the maximum score the second robot could collect.
Arrays with prefix sums or running sums are sufficient. Since the grid has only two rows, complex data structures are unnecessary and the problem can be solved with simple arithmetic updates.