Grid Game

medium array matrix prefix sum

Problem

Two robots travel a 2 × n grid from (0,0) to (1,n−1), only moving right or down. Robot one moves first and zeroes every cell it visits; robot two then collects the rest. Robot one wants to minimize, robot two to maximize, the second robot's score.

Inputgrid = [[2,5,4],[1,5,1]]

Output4

Robot one drops down at column 1; robot two collects 4.

row 0 (comma)

row 1 (comma)

def grid_game(grid):
    n = len(grid[0])
    top = sum(grid[0]) - grid[0][0]
    bottom = 0
    best = float('inf')
    for k in range(n):
        top -= 0 if k == 0 else grid[0][k]
        cand = max(top, bottom)
        best = min(best, cand)
        bottom += grid[1][k]
    return best

function gridGame(grid) {
  const n = grid[0].length;
  let top = 0;
  for (let i = 1; i < n; i++) top += grid[0][i];
  let bottom = 0;
  let best = Infinity;
  for (let k = 0; k < n; k++) {
    if (k > 0) top -= grid[0][k];
    best = Math.min(best, Math.max(top, bottom));
    bottom += grid[1][k];
  }
  return best;
}

class Solution {
    public long gridGame(int[][] grid) {
        int n = grid[0].length;
        long top = 0;
        for (int i = 1; i < n; i++) top += grid[0][i];
        long bottom = 0;
        long best = Long.MAX_VALUE;
        for (int k = 0; k < n; k++) {
            if (k > 0) top -= grid[0][k];
            best = Math.min(best, Math.max(top, bottom));
            bottom += grid[1][k];
        }
        return best;
    }
}

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

Explanation

Robot one only chooses where to drop down from the top row to the bottom row, say at column k. Once that choice is made, robot two's best score is fixed: it grabs the top cells to the right of k or the bottom cells to the left of k, whichever is larger.

So for each possible drop column k, robot two earns max(top, bottom), where top is the sum of the top row after column k and bottom is the sum of the bottom row before column k. Robot one, minimizing, picks the k that makes this max as small as possible.

We track top and bottom as running prefix/suffix sums while sweeping k left to right: subtract the current top cell from top first, evaluate, then add the current bottom cell to bottom. We keep the smallest max(top, bottom) seen.

Example: grid = [[2,5,4],[1,5,1]]. Dropping at column 1 leaves robot two with top-right 4 and bottom-left 1, so it collects 4, which is the minimized maximum. The answer is 4.

Maintaining the two running sums lets us test every drop column in a single linear pass, giving O(n) time and O(1) extra space.

Time: O(n) Space: O(1)