Problem

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.

Examples

Example 1:

$$ \begin{array}{|c|c|c|} \hline \colorbox{red}2 & \colorbox{red}5 & 4 \\ \hline 1 & \colorbox{red}5 & \colorbox{red}1 \\ \hline \end{array} \text{ }\text{ }\text{ }\text{ }\text{ } \begin{array}{|c|c|c|} \hline \colorbox{blue}0 & \colorbox{blue}0 & \colorbox{blue}4 \\ \hline 1 & 0 & \colorbox{blue}0 \\ \hline \end{array} $$

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:

$$ \begin{array}{|c|c|c|} \hline \colorbox{red}3 & 3 & 1 \\ \hline \colorbox{red}8 & \colorbox{red}5 & \colorbox{red}2 \\ \hline \end{array} \text{ }\text{ }\text{ }\text{ }\text{ } \begin{array}{|c|c|c|} \hline \colorbox{blue}0 & \colorbox{blue}3 & \colorbox{blue}1 \\ \hline 0 & 0 & \colorbox{blue}0 \\ \hline \end{array} $$

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:

$$ \begin{array}{|c|c|c|c|} \hline \colorbox{red}1 & \colorbox{red}3 & \colorbox{red}1 & \colorbox{red}15 \\ \hline 1 & 3 & 3 & \colorbox{red}1 \\ \hline \end{array} \text{ }\text{ }\text{ }\text{ }\text{ } \begin{array}{|c|c|c|c|} \hline \colorbox{blue}0 & 0 & 0 & 0 \\ \hline \colorbox{blue}1 & \colorbox{blue}3 & \colorbox{blue}3 & \colorbox{blue}0 \\ \hline \end{array} $$

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 == 2
  • n == grid[r].length
  • 1 <= n <= 5 * 104
  • 1 <= grid[r][c] <= 105

Solution

Method 1 - Using Prefix Sum

Note that both robots can move down only once. There are n possible paths for Robot 1. For each path taken by Robot 1, Robot 2 can collect points in two ways:

  • Collects topSum if it stays on the top row.
  • Collects bottomSum if it moves to the bottom row.

Thus, the points Robot 2 can collect is the maximum of topSum and bottomSum. To minimize Robot 2’s points, select the optimal path from the n paths available to Robot 1.

Why Greedy will not work?

Suppose, we try to find the max points for Robot 1, and it chooses path: (0,0) -> (0,1) -> (0,2) -> (0,3) -> (1,3).

$$ \begin{array}{|c|c|c|c|} \hline \colorbox{red}1 & \colorbox{red}5 & \colorbox{red}5 & \colorbox{red}4 \\ \hline 5 & 5 & 1 & \colorbox{red}1 \\ \hline \end{array} \text{ }\text{ }\text{ }\text{ }\text{ } \begin{array}{|c|c|c|c|} \hline \colorbox{blue}0 & 0 & 0 & 0 \\ \hline \colorbox{blue}5 & \colorbox{blue}5 & \colorbox{blue}1 & \colorbox{blue}0 \\ \hline \end{array} $$ But this will give 11 points to Robot 2.

But if Robot 1 has to minimize the points for Robot 2, then it should choose the path:

$$ \begin{array}{|c|c|c|c|} \hline \colorbox{red}1 & \colorbox{red}5 & 5 & 4 \\ \hline 5 & \colorbox{red} 5 & \colorbox{red} 1 & \colorbox{red}1 \\ \hline \end{array} \text{ }\text{ }\text{ }\text{ }\text{ } \begin{array}{|c|c|c|c|} \hline \colorbox{blue}0 & \colorbox{blue}0 & \colorbox{blue}5 & \colorbox{blue}4 \\ \hline 5 & 0 & 0 & \colorbox{blue}0 \\ \hline \end{array} $$

Robot 2 can then only choose from the top row for maximum points: (0,1) -> (0,2) -> (0,3), collecting 5 + 4 = 9

Video explanation

Here is the video explaining this method in detail. Please check it out:

Code

Java
class Solution {
    public long gridGame(int[][] grid) {
        long topSum = Arrays.stream(grid[0]).asLongStream().sum();
        long bottomSum = 0;
        long ans = Long.MAX_VALUE;
        for (int i = 0; i < grid[0].length; ++i) {
            topSum -= grid[0][i];
            long robot2Points = Math.max(topSum, bottomSum);
            ans = Math.min(ans, robot2Points);
            bottomSum += grid[1][i];
        }
        return ans;
    }
}
class Solution {
    public long gridGame(int[][] grid) {
        // Calculate the total points on the top row.
        long topSum = Arrays.stream(grid[0]).asLongStream().sum();
        long bottomSum = 0;
        long ans = Long.MAX_VALUE;
        for (int i = 0; i < grid[0].length; ++i) {
            // Robot 1 collects points from the top row up to the current column.
            topSum -= grid[0][i];
            // Determine the maximum points that Robot 2 can collect based on the current position of Robot 1.
            long robot2Points = Math.max(topSum, bottomSum);
            ans = Math.min(ans, robot2Points);
            // Accumulate points for Robot 1 on the bottom row.
            bottomSum += grid[1][i];
        }
        return ans;
    }
}
Python
class Solution:
    def gridGame(self, grid: List[List[int]]) -> int:
        # Calculate the total points on the top row.
        top_sum = sum(grid[0])
        bottom_sum = 0
        ans = float('inf')
        
        for i in range(len(grid[0])):
            # Robot 1 collects points from the top row up to the current column.
            top_sum -= grid[0][i]
            # Determine the maximum points that Robot 2 can collect based on the current position of Robot 1.
            robot2_points = max(top_sum, bottom_sum)
            ans = min(ans, robot2_points)
            # Accumulate points for Robot 1 on the bottom row.
            bottom_sum += grid[1][i]
        
        return ans

Complexity

  • ⏰ Time complexity:  O(n) for iterating through columns.
  • 🧺 Space complexity: O(1) since we use a few variables.