Question

2017. Grid Game

中文文档

Description

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

Solutions

Solution 1: Prefix Sum

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.

class Solution:
  def gridGame(self, grid: List[List[int]]) -> int:
    ans = inf
    s1, s2 = sum(grid[0]), 0
    for j, v in enumerate(grid[0]):
      s1 -= v
      ans = min(ans, max(s1, s2))
      s2 += grid[1][j]
    return ans

class Solution {
  public long gridGame(int[][] grid) {
    long ans = Long.MAX_VALUE;
    long s1 = 0, s2 = 0;
    for (int v : grid[0]) {
      s1 += v;
    }
    int n = grid[0].length;
    for (int j = 0; j < n; ++j) {
      s1 -= grid[0][j];
      ans = Math.min(ans, Math.max(s1, s2));
      s2 += grid[1][j];
    }
    return ans;
  }
}

using ll = long long;

class Solution {
public:
  long long gridGame(vector<vector<int>>& grid) {
    ll ans = LONG_MAX;
    int n = grid[0].size();
    ll s1 = 0, s2 = 0;
    for (int& v : grid[0]) s1 += v;
    for (int j = 0; j < n; ++j) {
      s1 -= grid[0][j];
      ans = min(ans, max(s1, s2));
      s2 += grid[1][j];
    }
    return ans;
  }
};

func gridGame(grid [][]int) int64 {
  ans := math.MaxInt64
  s1, s2 := 0, 0
  for _, v := range grid[0] {
    s1 += v
  }
  for j, v := range grid[0] {
    s1 -= v
    ans = min(ans, max(s1, s2))
    s2 += grid[1][j]
  }
  return int64(ans)
}

function gridGame(grid: number[][]): number {
  let ans = Number.MAX_SAFE_INTEGER;
  let s1 = grid[0].reduce((a, b) => a + b, 0);
  let s2 = 0;
  for (let j = 0; j < grid[0].length; ++j) {
    s1 -= grid[0][j];
    ans = Math.min(ans, Math.max(s1, s2));
    s2 += grid[1][j];
  }
  return ans;
}