Grid Game

Medium
1147.

Grid Game

Grid Game is a medium coding problem on arrays, matrix and prefix sum, asked in Amazon and Google interviews.

grid has exactly 2 rows and n columns; grid[r][c] is the number of points on cell (r, c). Two robots both start at (0, 0) and must reach (1, n - 1), each moving only right or down.

The first robot moves first and collects every point on its path; those cells then hold 0. The second robot then moves and collects the points remaining on its path.

The first robot wants to minimise what the second robot collects, and the second robot wants to maximise it. Return the number of points the second robot collects when both play optimally.

CodeKairo bounds: n is smaller than in the original problem so that the answer fits in a 32-bit integer.

Example 1

Input
grid = [[3,1,2],[4,1,1]]
Output
3
Explanation
If the first robot goes down at column 0, the second can take the top row's remaining `1 + 2`.

Example 2

Input
grid = [[1,9],[9,1]]
Output
9

Example 3

Input
grid = [[5],[7]]
Output
0
Explanation
The first robot takes both cells.

Constraints

  • grid.length == 2
  • n == grid[r].length
  • 1 <= n <= 2 * 10^4
  • 1 <= grid[r][c] <= 10^5
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} grid
 * @return {number}
 */
var gridGame = function(grid) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Grid Game — Solution in Python, Java & C++

Grid Game solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Amazon and Google.

Grid Game is a medium coding problem on arrays, matrix and prefix sum, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Arrays, Matrix, Prefix Sum
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

grid has exactly 2 rows and n columns; grid[r][c] is the number of points on cell (r, c). Two robots both start at (0, 0) and must reach (1, n - 1), each moving only right or down.

The first robot moves first and collects every point on its path; those cells then hold 0. The second robot then moves and collects the points remaining on its path.

The first robot wants to minimise what the second robot collects, and the second robot wants to maximise it. Return the number of points the second robot collects when both play optimally.

CodeKairo bounds: n is smaller than in the original problem so that the answer fits in a 32-bit integer.

Example 1

Input: grid = [[3,1,2],[4,1,1]]
Output: 3
Explanation: If the first robot goes down at column 0, the second can take the top row's remaining `1 + 2`.

Example 2

Input: grid = [[1,9],[9,1]]
Output: 9

Example 3

Input: grid = [[5],[7]]
Output: 0
Explanation: The first robot takes both cells.

Constraints

  • grid.length == 2
  • n == grid[r].length
  • 1 <= n <= 2 * 10^4
  • 1 <= grid[r][c] <= 10^5

Hints for Grid Game

  1. Hint 1

    Each robot's path is fixed by the single column where it moves down.

  2. Hint 2

    If the first robot turns down at column i, what is left is the top row to the right of i and the bottom row to the left of i.

  3. Hint 3

    The second robot can take only one of those two pieces, so it gets their maximum. Try every i with prefix sums and take the minimum.

How to solve Grid Game

After the first robot turns at column i, only two disjoint pieces remain — the top row right of i and the bottom row left of i — and the second robot can collect one of them in full.

Approach

  1. Let top be the sum of the whole top row and bottom = 0.
  2. For each column i from left to right: subtract grid[0][i] from top (now top is the top row right of i).
  3. The second robot's best is max(top, bottom); keep the minimum over all i.
  4. Then add grid[1][i] to bottom (the bottom row left of the next column).

Why it works

The second robot's path also goes down once: if it turns at column j > i it collects part of the top piece, if j < i part of the bottom piece, and turning exactly at the ends gathers one whole piece. Since all values are positive, the best it can do is the larger piece. The first robot picks the turn that minimises that maximum.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Minimising the first robot's own score is not the goal — maximising its score can leave the second robot more.
  • The two remaining pieces cannot both be collected, so the answer is a max of two sums, not their total.
  • With the original bounds (n up to 5 * 10^4) the sums need 64 bits.

Reference solution

Python

from typing import List

def gridGame(grid: List[List[int]]) -> int:
    top = sum(grid[0])
    bottom = 0
    best = None
    for i in range(len(grid[0])):
        top -= grid[0][i]
        second = max(top, bottom)
        if best is None or second < best:
            best = second
        bottom += grid[1][i]
    return best

Java

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

C++

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

JavaScript

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

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Matrix and Grid Traversal