2017. Grid Game

[mah-shamim]

Discussed in #1191

^{Originally posted by mah-shamim January 21, 2025}
Topics: Array, Matrix, Prefix Sum

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

Hint:

1. There are n choices for when the first robot moves to the second row.
2. Can we use prefix sums to help solve this problem?

[mah-shamim]

We'll use the following approach:

1. Prefix Sum Calculation: We'll compute the prefix sums for both rows of the grid to efficiently calculate the sum of points for any subarray.

2. Simulating Optimal Movement:

   • The first robot determines its path to minimize the points left for the second robot.
   • At each column transition, the first robot can choose to move down, splitting the grid into two segments:
     • Upper remaining points: Points in the top row after the transition column.
     • Lower remaining points: Points in the bottom row before the transition column.

3. Minimizing the Maximum Points for the Second Robot:

   • At each transition, calculate the maximum points the second robot can collect after the first robot's path.
   • Track the minimum of these maximums across all transitions.

Let's implement this solution in PHP: 2017. Grid Game

<?php
function gridGame($grid) {
    $n = count($grid[0]);
    
    // Calculate prefix sums for both rows
    $prefixTop = array_fill(0, $n + 1, 0);
    $prefixBottom = array_fill(0, $n + 1, 0);
    
    for ($i = 0; $i < $n; $i++) {
        $prefixTop[$i + 1] = $prefixTop[$i] + $grid[0][$i];
        $prefixBottom[$i + 1] = $prefixBottom[$i] + $grid[1][$i];
    }
    
    $minPointsForSecond = PHP_INT_MAX;
    
    // Iterate over all possible transition points
    for ($i = 0; $i < $n; $i++) {
        // Points remaining in the top row after $i
        $topRemaining = $prefixTop[$n] - $prefixTop[$i + 1];
        // Points remaining in the bottom row before $i
        $bottomRemaining = $prefixBottom[$i];
        
        // Maximum points the second robot can collect
        $secondRobotPoints = max($topRemaining, $bottomRemaining);
        
        // Minimize the maximum points for the second robot
        $minPointsForSecond = min($minPointsForSecond, $secondRobotPoints);
    }
    
    return $minPointsForSecond;
}

// Example usage
$grid1 = [[2, 5, 4], [1, 5, 1]];
$grid2 = [[3, 3, 1], [8, 5, 2]];
$grid3 = [[1, 3, 1, 15], [1, 3, 3, 1]];

echo gridGame($grid1) . "\n"; // Output: 4
echo gridGame($grid2) . "\n"; // Output: 4
echo gridGame($grid3) . "\n"; // Output: 7
?>

Explanation:

1. Prefix Sum Calculation:

   • prefixTop and prefixBottom store cumulative sums for the top and bottom rows, respectively.
   • These allow efficient range sum calculations.

2. Simulating the First Robot's Path:

   • At each column i, the first robot can decide to move down after column i.
   • This splits the grid into two regions:
     • Top row after column i (collected points: prefixTop[n] - prefixTop[i + 1]).
     • Bottom row before column i (collected points: prefixBottom[i]).

3. Second Robot's Optimal Points:

   • The second robot will take the maximum of the two remaining regions.
   • We track the minimum of these maximums for all possible transitions.

4. Complexity:

   • Time Complexity: O(n), as we compute prefix sums and loop through the grid once.
   • Space Complexity: O(n), due to prefix sum arrays.

Example Walkthrough

Input: grid = [[2, 5, 4], [1, 5, 1]]

• Prefix Sums:
  • prefixTop = [0, 2, 7, 11]
  • prefixBottom = [0, 1, 6, 7]
• Transition Points:
  • i = 0: Top Remaining = 11 - 7 = 9, Bottom Remaining = 0 → Second Robot = 9.
  • i = 1: Top Remaining = 11 - 11 = 4, Bottom Remaining = 1 → Second Robot = 4.
  • i = 2: Top Remaining = 0, Bottom Remaining = 6 → Second Robot = 6.
• Minimum Points for Second Robot: min(9, 4, 6) = 4.

This matches the expected output.