Leetcode 2017: Grid Game

Input: The input consists of a 2D array grid of size 2 x n, where each element grid[r][c] represents the number of points at position (r, c) in the grid.

Example: [[2, 5, 4], [1, 5, 1]]

Constraints:

• grid.length == 2

• n == grid[r].length

• 1 <= n <= 5 * 10^4

• 1 <= grid[r][c] <= 10^5

Output: Return the number of points collected by the second robot after both robots have moved optimally.

Example: 4

Constraints:

• The output should be the total number of points collected by the second robot.

Goal: The goal is to simulate the movement of both robots while ensuring that the first robot minimizes the points collected by the second robot and the second robot maximizes its own points.

Steps:

• Initialize variables to track the points collected by the first and second robots.

• Iterate through each column and update the points for both robots.

• For each robot, calculate the optimal path by updating the number of points in the grid after each robot’s move.

• Return the result of the second robot’s collected points.

Goal: The grid has two rows and n columns, and n can be as large as 50,000.

Steps:

• grid.length == 2

• n == grid[r].length

• 1 <= n <= 5 * 10^4

• 1 <= grid[r][c] <= 10^5

Assumptions:

• The grid will always have two rows and at least one column.

• Both robots will move optimally to achieve their respective goals.

• Input: [[2, 5, 4], [1, 5, 1]]

• Explanation: The first robot moves optimally to minimize the points collected by the second robot. After its path, the second robot collects 4 points.

• Input: [[3, 3, 1], [8, 5, 2]]

• Explanation: After the first robot moves, the second robot is left with 4 points on its path, as it maximizes its collection.

• Input: [[1, 3, 1, 15], [1, 3, 3, 1]]

• Explanation: The second robot collects 7 points after the first robot moves optimally.

Approach: The approach involves simulating both robots’ moves while keeping track of the points collected by each robot and updating the grid after the first robot's movement.

Observations:

• The grid has two rows, and each robot moves from the start to the end while collecting points.

• The first robot should minimize the points for the second robot by picking a path with fewer points, and the second robot should aim to maximize its own collection.

Steps:

• Calculate the total points in the first row before the first robot moves.

• For each column, update the points for both robots based on their moves.

• Track the maximum points collected by the second robot after the first robot’s path is set to 0.

Empty Inputs:

• The grid will always have two rows and at least one column, so there will be no empty inputs.

Large Inputs:

• Ensure the solution handles the upper limit of grid size (n = 50,000) efficiently.

Special Values:

• Handle cases where the grid has very small values (e.g., 1) or large values (e.g., 100,000).

Constraints:

• Ensure the algorithm runs within the time limits for large inputs (up to 50,000 columns).

long long gridGame(vector<vector<int>>& grid) {
    long long top = accumulate(grid[0].begin(), grid[0].end(), 0LL);
    long long bottom = 0;
    int n = grid[0].size();
    long long ans = LLONG_MAX;
    for(int i = 0; i < n; i++) {
        top -= grid[0][i];
        ans = min(ans, max(top, bottom));
        bottom+= grid[1][i];
  }
    return ans;
}

1 : Function Definition

long long gridGame(vector<vector<int>>& grid) {

This defines the function `gridGame`, which takes a 2D vector `grid` representing the game grid and returns a `long long` value as the result.

2 : Variable Initialization

    long long top = accumulate(grid[0].begin(), grid[0].end(), 0LL);

This initializes the `top` variable by summing all elements of the first row of the grid using the `accumulate` function, starting with an initial value of 0.

3 : Variable Initialization

    long long bottom = 0;

This initializes the `bottom` variable to 0, which will accumulate values from the second row of the grid.

4 : Grid Size Calculation

    int n = grid[0].size();

This determines the number of columns in the grid (the size of the first row), which will be used as the upper bound for the loop.

5 : Variable Initialization

    long long ans = LLONG_MAX;

This initializes the `ans` variable to the maximum possible long long value, which will store the result of the minimum maximum score during the game.

6 : Loop Initialization

    for(int i = 0; i < n; i++) {

This starts a loop that iterates over each column of the grid.

7 : Top Row Update

        top -= grid[0][i];

This subtracts the value of the current column from the `top` variable, effectively removing the score for that column from the top row.

8 : Score Calculation

        ans = min(ans, max(top, bottom));

This calculates the current maximum of `top` and `bottom` and updates the result `ans` with the minimum value of `ans` and this new maximum.

9 : Bottom Row Update

        bottom+= grid[1][i];

This adds the value of the current column from the second row of the grid to the `bottom` variable.

10 : Return Statement

    return ans;

This returns the calculated result `ans`, which is the minimum of the maximum scores across all the iterations.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The algorithm iterates through the columns of the grid once, so the time complexity is linear in terms of n.

Best Case: O(1)

Worst Case: O(1)

Description: The space complexity is constant since we only need a few variables to track the robots' movements and points.

Leetcode 2017: Grid Game

Explore →