Grid Game

Leetcode Problem:

• Grid Game

Summary

• The problem is to find the minimum number of points collected by the second robot in a game where two robots play on a 2xN grid.

Approach

• The solution uses a two-pointer approach, keeping track of the sum of points in the first and second rows
• It iterates over the grid, updating the sums and finding the minimum maximum value at each step.

Complexity

• O(n)

Explanation

• The solution works by maintaining two variables, `firstRowSum` and `secondRowSum`, which represent the sum of points in the first and second rows, respectively
• Initially, `firstRowSum` is set to the sum of the first row, and `secondRowSum` is set to 0
• Then, it iterates over the grid, updating `firstRowSum` by subtracting the current element and `secondRowSum` by adding the current element
• At each step, it finds the minimum maximum value between `firstRowSum` and `secondRowSum` and updates `minimumSum` accordingly
• Finally, it returns `minimumSum` as the minimum number of points collected by the second robot.

Solution Code:

class Solution {
public:
    long long gridGame(vector>& grid) {
        long long firstRowSum = accumulate(begin(grid[0]), end(grid[0]), 0LL),
                  secondRowSum = 0;
        long long minimumSum = LONG_LONG_MAX;
        for (int turnIndex = 0; turnIndex < grid[0].size(); ++turnIndex) {
            firstRowSum -= grid[0][turnIndex];
            // Find the minimum maximum value out of firstRowSum and
            // secondRowSum.
            minimumSum = min(minimumSum, max(firstRowSum, secondRowSum));
            secondRowSum += grid[1][turnIndex];
        }
        return minimumSum;
    }
};