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] <= 105Problem Overview: You are given a 2 x n grid where two robots move from the leftmost column to the rightmost column. The first robot moves first and collects points, then the second robot collects from the remaining cells. The goal is to choose the first robot’s path so the second robot’s final score is minimized.
Approach 1: Using a Brute Force Method (O(n^2) time, O(1) space)
The first robot can move right across the top row and switch to the bottom row at any column. For every possible switch column, simulate what cells remain for the second robot. The second robot will take the path that maximizes its collected score, so compute the sum of the remaining cells on the top-right segment and the bottom-left segment. Iterate over all possible switch points and calculate these sums repeatedly. This straightforward simulation demonstrates the core idea but recomputing sums each time leads to quadratic time complexity.
Approach 2: Using Sorting and Two-Pointer Technique (Prefix Sum Optimization) (O(n) time, O(1) space)
The key observation: once the first robot drops from the top row to the bottom row, the grid splits into two regions the second robot can exploit. One region is the remaining cells on the top row to the right, and the other is the collected prefix of the bottom row to the left. Precompute row totals using prefix sums and scan the grid from left to right while maintaining two running values: remaining top-row points and accumulated bottom-row points. At each column, compute the second robot’s best option as max(topRemaining, bottomCollected). The first robot chooses the column that minimizes this value. This single pass behaves like a two-pointer scan across the grid and avoids recomputing sums, reducing the runtime to linear.
Because the grid has only two rows, the decision reduces to evaluating every possible transition column while maintaining prefix sums of the rows. The algorithm relies on efficient cumulative calculations over an array and reasoning about segments in a matrix.
Recommended for interviews: The prefix-sum based linear scan (Approach 2) is what interviewers expect. The brute force approach shows you understand the game mechanics, but the optimized approach demonstrates the ability to convert repeated range-sum calculations into constant-time operations using prefix sums.
This approach involves iterating over all possible pairs or combinations to find the solution. Although simplistic, it's often not the most efficient in terms of time complexity. However, if the input size is small, it could be feasible.
This C code iterates over all pairs in the array using a nested loop. The function `findSolution` prints all pairs which is a fundamental brute force exploration.
Time Complexity: O(n2)
Space Complexity: O(1)
This approach leverages sorting the array and then using the two-pointer technique to efficiently identify necessary pairs. This optimization can reduce unnecessary comparisons made in the brute force approach by taking advantage of the sorted order.
This C solution first sorts the array using `qsort`, then iterates with two pointers on the left and right ends of the array. For each pair, it processes based on specific criteria.
Time Complexity: O(n log n) due to sorting
Space Complexity: O(1)
We notice that if we determine the position j where the first robot turns down, then the optimal path of the second robot is also determined. The optimal path of the second robot is the prefix sum of the first row from j+1 to n-1, or the prefix sum of the second row from 0 to j-1, taking the maximum of the two.
First, we calculate the suffix sum of the points in the first row, denoted as s_1, and the prefix sum of the points in the second row, denoted as s_2. Initially, s_1 = sum_{j=0}^{n-1} grid[0][j], s_2 = 0.
Then we enumerate the position j where the first robot turns down. At this time, we update s_1 = s_1 - grid[0][j]. Then the sum of the optimal path of the second robot is max(s_1, s_2). We take the minimum of max(s_1, s_2) for all j. Then we update s_2 = s_2 + grid[1][j].
After the enumeration, we return the answer.
The time complexity is O(n), and the space complexity is O(1). Here, n is the number of columns in the grid.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Using a Brute Force Method | Time Complexity: O(n2) |
| Approach 2: Using Sorting and Two-Pointer Technique | Time Complexity: O(n log n) due to sorting |
| Prefix Sum | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Simulation | O(n^2) | O(1) | Useful for understanding the mechanics of the game and verifying logic on small inputs. |
| Prefix Sum + Two-Pointer Scan | O(n) | O(1) | Best approach for interviews and large inputs where repeated range sums must be computed efficiently. |
Grid Game - Leetcode Weekly Contest Problem 2017 - Python • NeetCode • 20,809 views views
Watch 9 more video solutions →Practice Grid Game with our built-in code editor and test cases.
Practice on FleetCode