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 == 2n == grid[r].length1 <= n <= 2 * 10^41 <= grid[r][c] <= 10^5
Hints for Grid Game
Hint 1
Each robot's path is fixed by the single column where it moves down.
Hint 2
If the first robot turns down at column
i, what is left is the top row to the right ofiand the bottom row to the left ofi.Hint 3
The second robot can take only one of those two pieces, so it gets their maximum. Try every
iwith 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
- Let
topbe the sum of the whole top row andbottom = 0. - For each column
ifrom left to right: subtractgrid[0][i]fromtop(nowtopis the top row right ofi). - The second robot's best is
max(top, bottom); keep the minimum over alli. - Then add
grid[1][i]tobottom(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 (
nup 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 bestJava
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