Arrays - Grid Game

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.

Input: grid = [[2,5,4],[1,5,1]]
Output: 4
Explanation: The optimal path taken by the first robot is shown in orange, 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.

Input: grid = [[3,3,1],[8,5,2]]
Output: 4
Explanation: The optimal path taken by the first robot is shown in orange, 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.

Input: grid = [[1,3,1,15],[1,3,3,1]]
Output: 7
Explanation: The optimal path taken by the first robot is shown in orange, 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

Solution 1 - Using prefix/postfix, calculate the sum left for second robot to collect

As per the problem statement, one of the key point to remember is that the each robot may move right or down, that means if the robot comes down it has to continue in the same row.

In this approach, we will track the minimum value that the first robot should aim for at each step when it is moving, this minimum value when tracked by first robot, it will ensure that the maximum can be achieved by second robot is as small as possible.

Implementation steps:

We will first compute the total sum of 1^st row, call it totalSum.
Next, at each column i, from the first row compute what would be left for second robot if that celll is taken by first robot. that is totalSum - cell value.
Then compute the maximum between the accumulated sum of the second row and the remaining sum of the first row and store it in a variable, call it result.
In each step, track minimum value among result variable computed in each iteration, that will be the maximum that second robot can collect, after first robot tried its best to minimize second robot's score.

Example:

Lets look at an example with input array grid = [[1, 3, 3, 15], [1, 3, 3, 1]].

First, let's compute the total of 1^st row, which will be 1 + 3 + 3 + 15 = 22.
Next, for every column i do the following:
- For column 1, compute how much left for second robot if its comes down at this column, total - cell value => 22 -1 = 21, and accumulated sum for second row is 0 bottomRowAccumulated = 0(because if first robot comes down to bottom row, at this column this cell at bottom row will not be collected by second robot), then compute the max (total - cell value, bottomRowAccumulated) => max(21, 0) = 21. Now update bottomRowAccumulated with bottom row value for next iteration bottomRowAccumulated = 1.
- For column 1, compute how much left for second robot if its comes down at this column, total - cell value => 21 -3 = 18, and accumulated sum for second row is bottomRowAccumulated = 1, then compute the max (total - cell value, bottomRowAccumulated) => max(18, 1) = 18. Now update bottomRowAccumulated with bottom row value for next iteration bottomRowAccumulated = 1+3 = 4.
- For column 2, compute how much left for second robot if its comes down at this column, total - cell value => 18 -3 = 15, and accumulated sum for second row is bottomRowAccumulated = 4, then compute the max (total - cell value, bottomRowAccumulated) => max(15, 4) = 15. Now update bottomRowAccumulated with bottom row value for next iteration bottomRowAccumulated = 4+3 = 7.
- For column 3, compute how much left for second robot if its comes down at this column, total - cell value => 15 -15 = 0, and accumulated sum for second row is bottomRowAccumulated = 7, then compute the max (total - cell value, bottomRowAccumulated) => max(0, 7) = 7. Now update bottomRowAccumulated with bottom row value for next iteration bottomRowAccumulated = 7+1 = 8.
At each step above, if we track the minimum of max (total - cell value, bottomRowAccumulated), it will be 7 and that is our answer for second robot.

public class GridGame { static long gridGame(int[][] grid) { long topRowSum = 0; for(int i=0; i<grid[0].length; i++) { topRowSum += grid[0][i]; } long bottomSum = 0; long result = Long.MAX_VALUE; for(int i=0; i<grid[0].length; i++) { topRowSum = topRowSum - grid[0][i]; // remaining sum, what is left for second robot to collect // after current element is taken by first robot // Idea here is, once the robot is moved to second row, it cannot go back. // So, if first robot come down to second row at i(th) position, // sum left for second row is [total sum of 1st row] - current element result = Math.min(result, Math.max(bottomSum, topRowSum)); // bottomSum += grid[1][i]; } return result; } public static void main(String[] args) { int[][] grid = {{1,3,1,15}, {1,3,3,1}}; System.out.println(gridGame(grid)); } }

Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the length of grid array.
Space complexity: O(1)

Above implementations source code can be found at GitHub link for Java code

Contents

Implementation steps:

Example:

Complexity Analysis: